计算机算法基础 第2版 习题及答案 第11章 .docx

PAGE1

第11章 网络流

在例11.7的网络中，如果集合S={s，v3，v4}，T={v1，v2，t}，那么割(S,T)的容量是多少？

解： 割(S,T)的容量是c(S,T)=13+12+9+19+7=60，参照下图。

sv

s

v1

v2

v3

v4

5

4

12

18

13

7

6

10

9

t

19

假设f是网络G(V,E)的一个流。证明，在剩余网络Gf(V,Ef)中，任一对顶点u和v之间有如下关系:cf(u,v)+cf(v,u)=c(u,v)+c(v,u)。

证明： 因为cf(u,v)=c(u,v)-?(u,v)和cf(v,u)=c(v,u)–?(v,u)，我们有cf(u,v)+cf(v,u)=c(u,v)+c(v,u)–[?(u,v)+?(v,u)]。因为[?(u,v)+?(v,u)]=0，从而有cf(u,v)+cf(v,u)=c(u,v)+c(v,u)。?

证明任一个网络G(V,E)的最大流总可以由最多m个增广路径增广而得。(等价地证明，其最大流可以分解为最多m个增广流之和。)

证明： 假设f是G(V,E)的最大流，其值为|f|=F。我们先复制一个网络G(V,E)的考贝，G’(V’,E’)=G(V,E)。其中，V’=V，E’=E，c’(u’,v’)=c(u,v)。因为网络G’和G完全一样，网络G的最大流也必定是G’的最大流，反之也成立。现在，我们利用G(V,E)的最大流f来找G’(V’,E’)的最大流。设G’(V’,E’)的初始流是零。我们证明，最多m次增广路径的增广可得到G’(V’,E’)的最大流。

在G(V,E)中一条从源点s到汇点t的路径p称为一条流路径(flowpath)，如果路径p经过的每条边都有非零的流。我们定义这条流路径的流量为fp=min{f(u,v)|(u,v)?p}，也就是路径p上有最小流量的边上的流。我们从G(V,E)的最大流f来找G’(V’,E’)的最大流的算法如下。

Max-flow(G’(V’,E’))

foreachedge(u’,v’)?E’

f’(u’,v’)?0 //初始流为零

endfor

foreachedge(u,v)?E

F(u,v)?f(u,v) //F(u,v)记下f的初值，算法会更改变f，但不改F

endfor

whilethereexistsaflowpathpinG(V,E) //如果存在一条s到t的流路径p(可用BFS找)

??f(p) //f(p)是p的流量，f(p)=min{f(u,v)|(u,v)?p}

foreachedge(u,v)?p

f’(u’,v’)?f’(u’,v’)+? //增加G’中边(u’,v’)上流量

f(u,v)?f(u,v)-? //减少G中边(u,v)上流量

endfor

endwhile

End

上面算法的正确性可以证明如下。

首先，我们证明，一条G中的流路径就是G’中的增广路径。因为G’中的任何一条边(u’,v’)上流量的增加就等于G中边(u,v)上流量的减少，两者之和f’(u’,v’)+f(u,v)始终不变，f’(u’,v’)+f(u,v)=0+F(u,v)?c(u,v)=c’(u’,v’)，所以，在每次第7行while循环之后，G’中边(u’,v’)上的剩余容量c’f(u’,v’)满足以下不等式：

c’f(u’,v’)=c(u,v)-f’(u’,v’)?F(u,v)-f’(u’,v’)=f(u,v)。

因此，只要f(u,v)0，就有c’f(u’,v’)0。所以，一条G中的流路径就是G’中的增广路径。

其次，容易看出，每一次G中的流减少以后仍然是一个正常流。这是因为它满足f(u,v)?c(u,v)和流量守恒。

现在需要证明的是，只要G中的流不是零，就一定有流路径。我们用反证法。如果不是，那么，我们把所有从源点s有流路径可达的点放在集合S中，其它点放在集合T中。因为t?T，(S,T)必定是个割，并且有f(S,T)=0从而|f|=0。这与G中的流不是零相矛盾。所以，上面的算法Max-flow正确地产生G’(V’,E’)的最大流。

因为每次增广后，G中至少有一条边