算法导论24.3 Exercises 答案

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$个节点，不失一般性，设其为$l1,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\rightarrow li\rightarrow r{i+1}\rightarrow t$，那么这$m-1$轮后，残余网络$Gf$包含了如下这些边：${(r{i+1},li)\mid i\in[1,m-1]}$，那么第$m$轮所构造的增广路径$p$可以如下构造：$s\rightarrow l_m\rightarrow r_m\rightarrow l{m-1}\rightarrow r_{m-1}\rightarrow\dots\rightarrow r_2\rightarrow l_1\rightarrow r_1\rightarrow t$。

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