算法导论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\)个节点，不失一般性，设其为\(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\rightarrow l_i\rightarrow r_{i+1}\rightarrow t\)，那么这\(m-1\)轮后，残余网络\(G_f\)包含了如下这些边：\(\{(r_{i+1},l_i)\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\)是所求满足条件的最长路径。