算法导论24.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 5.1k 阅读时长 ≈ 5 分钟

24.1-1

令\(f'\)是\(G'=(V',E')\)中的一个流，\(f\)是\(G=(V,E)\)中的一个流，容易知道，\(V\subseteq V'\)。我们将证明，对于所有在图\(G'\)中的流\(f'\)，都在\(G\)中存在对应的流\(f\)，使得\(|f'|=|f|\)；类似的，对于所有在图\(G\)中的流\(f\)，都在\(G'\)中存在对应的流\(f'\)，使得\(|f|=|f'|\)，从而证明两个图中的流具有对应关系，因此\(G'\)中的最大流就对应了\(G\)中的最大流。不失一般性，假设\(G\)中存在一对节点\((u,v)\)，满足\(c(u,v)>0,c(v,u)>0\)，并且在图\(G'\)中，边\((u,v)\)被拆分成两条边\((u,x),(x,v)\)，并且有\(c'(u,x)=c'(x,v)=c(u,v),c'(v,u)=c(v,u)\)。

接下来先证明：对于所有在图\(G'\)中的流\(f'\)，都在\(G\)中存在对应的流\(f\)，使得\(|f'|=|f|\)。假设\(f'\)是图\(G'\)的某一个流，那么根据流量守恒可知\(f'(u,x)=f'(x,v)\)，令\(f(u,v)=f'(u,x),f(v,u)=f'(v,u)\)。那么这对反平行边在图\(G\)中的\(u\)节点看来，它们使其释放了\(f(u,v)-f(v,u)\)的流量；在\(v\)节点看来，它们使其接受了\(f(u,v)-f(v,u)\)的流量，这个情况在图\(G'\)中的节点\(u\)和\(v\)看来是一样的，因此节点\(u,v\)的流量守恒仍然保持成立。因此按照\(f,f'\)的定义式，可以计算出\(|f'|-|f|\)的值：

\(\begin{aligned} |f'|-|f|&=\left(\sum_{v\in V'} f'(s,v)-\sum_{v\in V'} f'(v,s)\right)-\left(\sum_{v\in V} f(s,v)-\sum_{v\in V} f(v,s)\right)\\ &=\left(\sum_{v\in V'} f'(s,v)-\sum_{v\in V} f(s,v)\right)-\left(\sum_{v\in V'} f'(v,s)-\sum_{v\in V} f(v,s)\right)\\ &=\left(\sum_{v\in V'} f'(s,v)-\sum_{v\in V} f(s,v)\right)-\left(\sum_{v\in V'} f'(v,s)-\sum_{v\in V} f(v,s)\right)\\ &=0-0&\qquad(A)\\ &=0 \end{aligned}\)

其中步骤\((A)\)的得出，是因为图\(G\)中\(s\)的出边/入边和\(G'\)中的出边/入边一一对应，因此构造出来的流\(f\)满足\(|f'|=|f|\)。

接下来证明：对于所有在图\(G\)中的流\(f\)，都在\(G'\)中存在对应的流\(f'\)，使得\(|f|=|f'|\)。假设\(f\)是图\(G\)的某一个流，那么令\(f'(u,x)=f'(x,v)=f(u,v),f'(v,u)=f(v,u)\)。由新构造出的\(x\)节点可以知道，\(x\)满足流量守恒，此外对于\(u\)节点和\(v\)节点，按照之前的论证，它们对节点\(u\)和\(v\)的流入流量和流出流量的贡献是相同的，因此按照类似的论证方式，可以得出\(|f'|=|f|\)。

因此最终，从\(G'\)构造出来的最大流可以推导出图\(G\)的最大流。原结论成立。

24.1-2

定义源点集合\(S=\{s_1,s_2,\dots,s_n\}\)，汇点集合\(T=\{t_1,t_2,\dots,t_m\}\)。那么容量限制的定义依旧不变，流量守恒的定义转变成，对于所有的节点\(u\in V-S-T\)，有\(\displaystyle{\sum_{v\in V} f(u,v)=\sum_{v\in V} f(v,u)}\)成立。

那么最大流\(f\)的值定义为：

\[|f|=\sum_{s\in S}\left(\sum_{v\in V} f(s,v)-\sum_{v\in V}f(v,s)\right) \]

令新增超级源点\(s'\)和超级汇点\(t'\)后所得到的图\(G'=(V',E')\)，其中\(V=V\cup\{s,t\}\)。那么\(\forall (u,v)\in E,f'(u,v)=f(u,v)\)，并且对于\(\displaystyle{\forall s\in S,f'(s',s)=\sum_{v\in V}f(s,v)-\sum_{v\in V} f(v,s)}\)，以及\(\displaystyle{\forall t\in T,f(t,t')=\sum_{v\in V}f(v,t)-\sum_{v\in V}f(t,v)}\)，那么对于节点\(s\in S,t\in T\)，在图\(G'\)中都满足了流量守恒。因此\(f\)所对应的\(f'\)是在\(G'\)中的一个流。其流量值相等，均为\(|f|\)。从\(f'\)中去除和\(s',t'\)关联的所有边后，就得到了\(G\)中的一个流\(f\)。

24.1-3

我们将证明比题目更强的一个结论：如果图\(G\)中存在节点\(u\)，使得路径\(s\rightsquigarrow u\rightsquigarrow t\)不存在，那么对于\(G\)中的所有流\(f\)，都有\(\forall v\in V,f(u,v)=f(v,u)=0\)。我们将使用反证法证明。

我们首先证明从\(u\)无法到达\(t\)的情况。假设\(\exists v\in V,f(u,v)>0\)，那么根据流量守恒可以知道，从\(u\)起必定有一条路径\(v_1,v_2,\dots,v_m\)，对于\(i\in[1,m-1]\)，都有\(f(v_{i},v_{i+1})>0\)成立，其中\(v_1=u,v_2=v\)。按照流量守恒的定义，只有汇点\(t\)允许流入量大于流出量，因此从\(u\)开始的流量只能不停向下传递，直到到达\(t\)，因此必定有\(v_m=t\)，这和从\(u\)到\(t\)中存在路径是矛盾的，因此只能有\(f(u,v)=0\)，也就是说\(u\)的所有出边的流量都为\(0\)，根据流量守恒，\(u\)的所有入边的流量都为\(0\)，因此原结论成立。

接下来证明从\(s\)无法到达\(u\)的情况。证明过程和上面的过程类似。假设\(\exists v\in V,f(v,u)>0\)，那么根据流量守恒可以知道，必定有以\(u\)为终点的一条路径\(w_1,w_2,\dots,w_n\)，对于\(\forall i\in[1,n-1]\)，都有\(f(w_i,w_{i+1})>0\)，其中\(v_{n-1}=v,v_n=u\)。按照流量守恒的定义，只有源点\(s\)允许流入量小于流出量，因此只能从\(u\)不停向上追溯，一直到达\(s\)，因此必定有\(w_1=s\)，这和从\(s\)到\(u\)中存在路径是矛盾的，因此只能有\(f(v,u)=0\)，也就是说\(u\)的所有入边的流量都为\(0\)，根据流量守恒，\(u\)的所有出边的流量都为\(0\)，因此原结论成立。

24.1-4

首先证明\(\alpha f_1+(1-\alpha)f_2\)是满足容量限制。

对于边\((u,v)\)，由于\(f_1(u,v)\ge 0,f_2(u,v)\ge 0,\alpha\in[0,1]\)，因此\(\alpha f_1(u,v)+(1-\alpha)f_2(u,v)\ge 0\)。此外，有

\(\begin{aligned} \alpha f_1(u,v)+(1-\alpha)f_2(u,v)&\le \alpha c(u,v)+(1-\alpha)c(u,v)\\ &=c(u,v) \end{aligned}\)

因此容量限制得证。

接下来证明\(\alpha f_1+(1-\alpha)f_2\)是满足流量守恒。对于每个节点\(u\in V-\{s,t\}\)，考虑证明\(\displaystyle{\sum_{v\in V}(\alpha f_1(u,v)+(1-\alpha)f_2(u,v))=\sum_{v\in V}(\alpha f_1(v,u)+(1-\alpha)f_2(v,u))}\)，那么有

\(\begin{aligned} &\sum_{v\in V}(\alpha f_1(u,v)+(1-\alpha)f_2(u,v))-\sum_{v\in V}(\alpha f_1(v,u)+(1-\alpha)f_2(v,u))\\=&\alpha\left(\sum_{v\in V} f_1(u,v)-\sum_{v\in V} f_1(v,u)\right)-(1-\alpha)\left(\sum_{v\in V} f_2(u,v)-\sum_{v\in V} f_2(v,u)\right)\\ =&\alpha\cdot0+(1-\alpha)\cdot 0\\ =&0 \end{aligned}\)

因此流量守恒得证。

因此，\(\alpha f_1+(1-\alpha)f_2\)是一个流。

24.1-5

令\(G=(V,E)\)，那么\(s\)到\(t\)的最大流问题表示成一个线性规划问题是：

\(\begin{aligned} \text{maximize}&& \sum_{(s,v)\in E} f(s,v)-\sum_{(v,s)\in E} f(v,s)\\ \text{subject to}& \\ &&f(u,v)&\ge 0 &&\forall (u,v)\in E \\ &&f(u,v)&\le c(u,v) &&\forall (u,v)\in E \\ &&\sum_{(u,v)\in E} f(u,v)&=\sum_{(v,u)\in E} f(v,u) &&\forall u\in V-\{s,t\} \end{aligned}\)

后面的两条式子分别代表了容量限制和流量守恒条件。

24.1-6

令\(s\)表示他们的家，令\(t\)表示他们的学校，地图\(G\)上的每条边的容量都设置为\(1\)。在这个输入上运行最大流算法，并判断最大流的值是否超过\(2\)，如果超过\(2\)，那么存在上学方案，否则不存在。

24.1-7

将图\(G=(V,E)\)中的每个节点\(v\)拆分成两个节点\(v_{in},v_{out}\)，并且从\(v_{in}\)到\(v_{out}\)只需要连一条容量为\(l(v)\)的边即可。对图\(G'=(V',E')\)更正式的描述如下：

  • \(\forall v\in V,v_{in},v_{out}\in V'\)均成立。
  • \(\forall v\in V,(v_{in},v_{out})\in E'\)均成立，其中\(c'(v_{in},v_{out})=l(v)\)。
  • \(\forall (u,v)\in E,(u_{out},v_{in})\in E'\)均成立，其中\(c'(u_{out},v_{in})=c(u,v)\)。

那么假设图\(G\)上对应的源点和汇点分别为\(s,t\)，那么在图\(G'\)上的源点和汇点分别为\(s_{in},t_{out}\)。

因此，图\(G'\)上一共有\(2|V|\)个节点，\(|V|+|E|\)条边。