算法导论 24.3 Exercises 答案

发表于 2023-06-23 更新于 2023-07-03 分类于算法导论阅读次数： 185 本文字数： 1.5k 阅读时长 ≈ 1 分钟

24.3-1

接下里将使用残余网络来表示这个流网络，并且由于边容量都是 $1$ ，因此忽略容量标记值。一开始残余网络如下：

随后运行 BFS，找到了一条增广路径 $(s, 1, 6, t)$ 。由此可以对残余网络进行更新：

随后找到了一条增广路径 $(s, 2, 8, t)$ 。由此可以对残余网络进行更新：

最后找到了一条增广路径 $(s, 3, 7, t)$ ，由此可以对残余网络进行更新：

此后，再也不存在增广路径，因此最大流 $| f | = 3$ 。，从而得到最大匹配 $| M | = 3$ 。

24.3-2

考虑算法 FORD-FULKERSON 的第 3 行的 while 循环，定义循环不变量：对于 $\forall (u, v) \in E, c_{f} (u, v)$ 和 $(u, v) . f$ 总是为整数。接下来证明这个循环变量成立。

初始化：一开始，所有的流 $f$ 都为 $0$ ，由于容量只取整数值，因此所有容量 $c_{f} (u, v)$ 都是整数，循环不变量得以成立。

保持：假设循环执行前，循环不变量保持成立，此时找到了一条增广路径 $p$ 。由于 $\forall (u, v) \in E, c_{f} (u, v)$ 都是整数，因此从第 4 行计算出来的 $c_{f} (p)$ 是整数。由于对于所有边 $(u, v)$ 的 $f$ 属性都是整数，因此对 $(u, v) . f$ 都减去一个整数 $c_{f} (p)$ ，仍然是整数。按照方程 24.2 更新残余网络的每条边的容量 $c_{f}$ ，得到的仍然是整数。

终止：最终 while 循环停止后，所有边上的流 $f$ 和残余容量 $c_{f}$ 都是整数。

因此，最终计算出来的最大流的值 $| f |$ 一定是一个整数。

24.3-3

这条增广路径的最大值为： $2 min {| L |, | R |} + 1$ 。令 $m = min {| L |, | R |}$ 。接下来介绍如何构造达到这个上界的增广路径。

首先构造出图 $G = (V, E)$ 。从 $L$ 中取出 $m$ 个节点，不失一般性，设其为 $l_{1}, l_{2}, \dots, l_{m}$ ，从 $R$ 中也取出 $m$ 个节点，设其为 $r_{1}, r_{2}, \dots, r_{m}$ 。那么 $\forall i \in [1, m], (l_{i}, r_{i}) \in E; \forall j \in [1, m - 1], (l_{j}, r_{j + 1}) \in E$ 。对于其它节点 $u \in V - {l_{1}, l_{2}, \dots, l_{m}, r_{1}, r_{2}, \dots, r_{m}}$ ，只需要保证它们在另一部分的节点和 $u$ 相连即可。最终如此构造出图 $G$ 。

在前 $m - 1$ 轮迭代中，假设算法 FORD-FULKERSON 在第 $i$ 轮的增广路径是 $s \to l_{i} \to r_{i + 1} \to t$ ，那么这 $m - 1$ 轮后，残余网络 $G_{f}$ 包含了如下这些边： ${(r_{i + 1}, l_{i}) ∣ i \in [1, m - 1]}$ ，那么第 $m$ 轮所构造的增广路径 $p$ 可以如下构造： $s \to l_{m} \to r_{m} \to l_{m - 1} \to r_{m - 1} \to \dots \to r_{2} \to l_{1} \to r_{1} \to t$ 。

可见，上述所构造的增广路径 $p$ 达到了长度 $2 m + 1 = 2 min {| L |, | R |} + 1$ 。由于增广路径 $p$ 是一条简单路径， $L, R$ 中总有一部分节点已经被使用完了，无法再找到一对节点 $(l, r)$ 再延长路径长度，因此只能走向节点 $t$ 。最终， $p$ 是所求满足条件的最长路径。