第十一章图与网络分析2.ppt

《第十一章图与网络分析2.ppt》由会员分享，可在线阅读，更多相关《第十一章图与网络分析2.ppt（110页珍藏版）》请在三一办公上搜索。

1、第十一章 图与网络分析,Graph theory and network analysis,第十一章 图与网络分析,11.1 引言11.2 图与网络的基本概念11.3 最短路问题11.4 最小生成树问题11.5 最大流问题,11.5 最大流问题,最大流问题是一类应用极为广泛的问题，例如交通运输网络中有人流、车流、物流，供水网络中有水流；金融系统中有现金流；通讯系统中有信息流。50年代福特（Ford）和富克逊（Fulkerson）建立的“网络流理论”，是网络应用的重要组成部分。,11.5 最大流问题,11.5 最大流问题,11.5 最大流问题,什么是最大流问题？,11.5 最大流问题,什么是最大

2、流问题？,假设图为输油网络，Vs为起点，Vt为终点，V2,V3,V4,V5为中转站，边上的数表示该管道的最大输油能力，问该如何安排各管道输油量能使从Vs到Vt的总运输量最大？管道网络中的每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量，上述问题就是讨论如何充分利用装置的能力。,11.5 最大流问题,最大流问题有关概念,定义：设有向连通图 G=(V,E),G 的每条边(vi,vj)上有非负数 cij 称为边的容量,仅有一个入次为0的点 vs 称为发点(源),一个出次为0的点 vt 称为收点(汇),其余点为中间点,这样的网络G称为容量网络,常记做G=(V,E,C).,11.5 最大流问

3、题,最大流问题有关概念,11.5 最大流问题,最大流问题有关概念,V5,定义：对任一 G 中的边(vi,vj)有流量 fij,称集合f=fij 为网络G上的一个流；称满足下列条件的流f 为可行流：（1）容量限制条件：对 G 中每条边(vi,vj)，有 0 fij cij（2）平衡条件：对中间点vi，有 fij fki(即从中间点vi的物资输入量与输出量相等)对收发点 vs,vt 有 fsj fti=W（W为网络的总流量）(即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,可行流总是存在的，例如 f=0 就是一个流量为0 的可行流。最大流问题 在容量网

4、络中，寻找流量最大的可行流。饱和与不饱和 一个流 f=fij，当fijcij，则称流 f 对边(vi,vj)是饱和的，否则称f 对边(vi,vj)不饱和。,11.5 最大流问题,最大流问题有关概念,11.5 最大流问题,最大流问题有关概念,最大流问题实际是个线性规划问题，但利用它与图的紧密关系，能更为直观简便地求解。,定义：对任一 G 中的边(vi,vj)有流量 fij,称集合f=fij 为网络G 上的一个流；称满足下列条件的流 f 为可行流：（1）容量限制条件：对 G 中每条边(vi,vj)，有 0 fij cij（2）平衡条件：对中间点vi，有 fij fki(即从中间点vi的物资输入量与

5、输出量相等)对收发点 vs,vt 有 fsj fti=W（W为网络的总流量）(即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,V7,约束条件：（1）容量限制条件：fij cij（i=1,2,3,4,5,6,j=2,3,4,5,6,7）0 fij（i=1,2,3,4,5,6,j=2,3,4,5,6,7）,V5,定义：对任一 G 中的边(vi,vj)有流量 fij,称集合f=fij 为网络G 上的一个流；称满足下列条件的流f 为可行流：（1）容量限制条件：对 G 中每条边(vi,vj)，有 0 fij cij（2）平衡条件：对中间点vi，有 fij f

6、ki(即从中间点vi的物资输入量与输出量相等)对收发点 vs,vt 有 fsj fti=W（W为网络的总流量）(即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,V7,约束条件：（2）平衡条件：f12=f23 f25（V2）,V5,V7,约束条件：（2）平衡条件：f12=f23 f25（V2）,V5,V7,约束条件：（2）平衡条件：f12=f23 f25（V2）,V5,V7,6,3,5,2,2,2,4,1,2,6,3,V1,V2,V4,V3,V6,约束条件：（2）平衡条件：f12=f23 f25（V2）,V5,V7,6,3,5,2,2,2,4,1,2

7、,6,3,V1,V2,V4,V3,V6,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V3）,V5,V7,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V3）,V5,V7,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V3）f14=f43 f46 f47（V4）,V5,V7,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V3）f14=f43 f46 f47（V4）,V5,V7,6,3,5,2,2,2,4,1,2,6,3,V1,V

8、2,V4,V3,V6,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V3）f14=f43 f46 f47（V4）,f25 f35=f57（V5）,V5,V7,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V3）f14=f43 f46 f47（V4）,V5,f25 f35=f57（V5）,V7,6,3,5,2,2,2,4,1,2,6,3,V1,V2,V4,V3,V6,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V3）f14=f43 f46 f47（V4）,V5,f25

9、f35=f57（V5）f36 f46=f67（V6）,定义：对任一 G 中的边(vi,vj)有流量 fij,称集合f=fij 为网络G 上的一个流；称满足下列条件的流f 为可行流：（1）容量限制条件：对 G 中每条边(vi,vj)，有 0 fij cij（2）平衡条件：对中间点vi，有 fij fki(即从中间点vi的物资输入量与输出量相等)对收发点 vs,vt 有 fsj fti=W（W为网络的总流量）(即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,V7,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V

10、3）f14=f43 f46 f47（V4）,V5,f25 f35=f57（V5）f36 f46=f67（V6）,V7,6,3,5,2,2,2,4,1,2,6,3,V1,V2,V4,V3,V6,约束条件：（2）平衡条件：f12=f23 f25（V2）f23 f43=f34 f35（V3）f14=f43 f46 f47（V4）,V5,f25 f35=f57（V5）f36 f46=f67（V6）f47 f57 f67=f12 f14（W）,11.5 最大流问题,最大流问题有关概念,目标函数 max f12 f14 约束条件 fij cij（i=1,2,3,4,5,6,j=2,3,4,5,6,7）0

11、fij（i=1,2,3,4,5,6,j=2,3,4,5,6,7）f12=f23 f25（V2）f23 f43=f34 f35（V3）f14=f43 f46 f47（V4）f25 f35=f57（V5）f36 f46=f67（V6）f47 f57 f67=f12 f14（W）,11.5 最大流问题,最大流的标号算法设已有一个可行流 f，标号的方法可分为两步 第一步是标号过程，通过标号来寻找可增广链；第二步是调整过程，沿可增广链调整 f 以增加流量。,11.5 最大流问题,可增广链：容量网路G，若u为网络中从Vs（发点）到Vt（收点）的一条链，给u定向为从Vs到Vt，u上的边凡与u同向称为向前边，

12、凡于u反向的称为向后边，其集合分别用u+和u-表示，f 是一个可行流，如果满足 0 fij cij(vi,vj)u+0 fij cij(vi,vj)u-则称u为从Vs到Vt的（关于f的）可增广链。,11.5 最大流问题,图为一个网络及初始可行流，每条边上的有序数表示（cij,fij），求最大流。,(3,0),11.5 最大流问题,图为一个网络及初始可行流，每条边上的有序数表示（cij,fij），求最大流。,(3,0),定义：对任一 G 中的边(vi,vj)有流量 fij,称集合f=fij 为网络G 上的一个流；称满足下列条件的流f 为可行流：（1）容量限制条件：对 G 中每条边(vi,vj)，

13、有 0 fij cij（2）平衡条件：对中间点vi，有 fij fki(即从中间点vi的物资输入量与输出量相等)对收发点 vs,vt 有 fsj fti=W（W为网络的总流量）(即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,11.5 最大流问题,图为一个网络及初始可行流，每条边上的有序数表示（cij,fij），求最大流。,(3,0),11.5 最大流问题,可增广链：容量网路G，若u为网络中从Vs（发点）到Vt（收点）的一条链，给u定向为从Vs到Vt，u上的边凡与u同向称为前向边，凡于u反向的称为后向边，其集合分别用u+和u-表示，f 是一个可行流

14、，如果满足 0 fij cij(vi,vj)u+(前向边不饱和)0 fij cij(vi,vj)u-(后向边不为零)则称u为从Vs到Vt的（关于f的）可增广链。,11.5 最大流问题,Vt,(5,5),Vs,V1,V3,V6,V2,V5,V4,(5,2),(3,3),(4,2),(3,3),(5,4),(2,2),(2,2),(3,2),(4,2),图为一个网络及初始可行流，每条边上的有序数表示（cij,fij），求最大流。,(3,0),Vt,(5,5),Vs,V1,V3,V6,V2,V5,V4,(5,2),(3,3),(4,2),(3,3),(5,4),(2,2),(2,2),(3,2),(

15、4,2),(3,0),若u为网络中从Vs（发点）到Vt（收点）的一条链，0 fij cij(vi,vj)u+（前向边不饱和）0 fij cij(vi,vj)u-（后向边不为零）则称u为从Vs到Vt的（关于f的）可增广链。,Vt,(5,5),Vs,V1,V3,V6,V2,V5,V4,(5,2),(3,3),(4,2),(3,3),(5,4),(2,2),(2,2),(3,2),(4,2),(3,0),若u为网络中从Vs（发点）到Vt（收点）的一条链，0 fij cij(vi,vj)u+（向前边不饱和）0 fij cij(vi,vj)u-（向后边不为零）则称u为从Vs到Vt的（关于f的）可增广链。

16、,Vt,(5,5),Vs,V1,V3,V6,V2,V5,V4,(5,2),(3,3),(4,2),(3,3),(5,4),(2,2),(2,2),(3,2),(4,2),(3,0),若u为网络中从Vs（发点）到Vt（收点）的一条链，0 fij cij(vi,vj)u+（向前边不饱和）0 fij cij(vi,vj)u-（向后边不为零）则称u为从Vs到Vt的（关于f的）可增广链。,可增广链的实际意义是：沿着这条链从Vs（发点）到Vt输送的流，还有潜力可挖，可以经过调整，将流量提高，调整后的流，在各点仍然满足平衡条件及容量限制,11.5 最大流问题,最大流的标号算法设已有一个可行流 f，标号的方法

17、可分为两步 第一步是标号过程，通过标号来寻找可增广链；第二步是调整过程，沿可增广链调整 f 以增加流量。,11.5 最大流问题,最大流的标号算法1.标号过程（1）给发点以标号（，+）（2）选择边一个已标号的顶点Vi,对于Vi的所有未给标号的相邻点Vj 按下列规则处理：a)若边(vj,vi)E，且fji 0 则令 j=min(fji,i)并给vj标号（-vi，j）反向非零弧 b)若边(vi,vj)E，且fij cij 则令 j=min(cij-fij,i)并给vj标号（+vi，j）正向非饱和弧重复（2）直到收点Vt 被标号或不再有顶点可标号为止。,11.5 最大流问题,最大流的标号算法 如若Vt

18、得到标号，说明存在一条可增广链，进行调整，反之计算结束。2.调整过程（1）若(vi,vj)是可增广链上的前向边，则f ij=fij+t 若(vi,vj)是可增广链上的后向边，则f ij=fij-t 若(vi,vj)不在可增广链上，则f ij=fij（2）去掉所有标号，回到第1步,11.5 最大流问题,11.5 最大流问题,最大流的标号算法1.标号过程（1）给发点以标号（，+）（2）选择边一个已标号的顶点Vi,对于Vi的所有未给标号的相邻点Vj 按下列规则处理：a)若边(vj,vi)E，且fji 0 则令 j=min(fji,i)并给vj标号（-vi，j）b)若边(vi,vj)E，且fij ci

19、j 则令 j=min(cij-fij,i)并给vj标号（+vi，j）重复（2）直到收点Vt 被标号或不再有顶点可标号为止。,，+,(3,0),11.5 最大流问题,最大流的标号算法1.标号过程（1）给发点以标号（，+）（2）选择边一个已标号的顶点Vi,对于Vi的所有未给标号的相邻点Vj 按下列规则处理：a)若边(vj,vi)E，且fji 0 则令 j=min(fji,i)并给vj标号（-vi，j）b)若边(vi,vj)E，且fij cij 则令 j=min(cij-fij,i)并给vj标号（+vi，j）正向非饱和弧重复（2）直到收点Vt 被标号或不再有顶点可标号为止。,，+,(3,0),，+,

20、检查Vs点的相邻点V1 V1 点满足(vs,v1)E，但是fs1=cs15 因此先不考虑,(3,0),，+,检查Vs点的相邻点V2 正向非饱和弧V2点满足(vs,v2)E，且fs2 cs22=min(cs2 fs2,1)=min(4-2,+)=2并给v2标号（+Vs，2）=（+Vs，2）,+Vs，2,(3,0),，+,检查Vs点的相邻点V3 正向非饱和弧V3点满足(Vs,V3)E，且fs3 cs33=min(cs3 fs3,1)=min(3-2,+)=1并给v3标号（+Vs，3）=（+Vs，1）,+Vs，2,+Vs，1,(3,0),，+,+Vs，2,+Vs，1,(3,0),，+,+Vs，2,+

21、Vs，1,检查V2 点的尚未标号的相邻点,(3,0),，+,+Vs，2,+Vs，1,检查V2 点的尚未标号的相邻点,(3,0),，+,+Vs，2,+Vs，1,检查 V2 点的相邻点 V5V5点满足(V2,V5)E，且 f25 C255=min(C25 f25,2)=min(3-0,2)=2并给V5标号（+V2，5）=（+V2，2）,(3,0),+V2，2,，+,+Vs，2,+Vs，1,检查 V2 点的相邻点 V6V6点满足(V2,V6)E，且 f26=C26因此先不考虑,(3,0),+V2，2,，+,+Vs，2,+Vs，1,检查 V3 点的相邻点 V6V6点满足(V3,V6)E，且 f36=C

22、36因此先不考虑,(3,0),+V2，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,检查已经标号V5 点的尚未标号的相邻点,，+,+Vs，2,+Vs，1,(3,0),+V2，2,检查已经标号V5 点的尚未标号的相邻点,，+,+Vs，2,+Vs，1,(3,0),+V2，2,检查已经标号V5 点的尚未标号的相邻点,11.5 最大流问题,最大流的标号算法1.标号过程（1）给发点以标号（，+）（2）选择边一个已标号的顶点Vi,对于Vi的所有未给标号的相邻点Vj 按下列规则处理：a)若边(vj,vi)E，且fji 0 则令 j=min(fji,i)并给vj标号（-vi，j）反向非零弧 b)若

23、边(vi,vj)E，且fij cij则令 j=min(cij-fij,i)并给vj标号（+vi，j）重复（2）直到收点Vt 被标号或不再有顶点可标号为止。,，+,+Vs，2,+Vs，1,(3,0),+V2，2,检查 V5 点的相邻点 V1 反向非零弧V1点满足(V1,V5)E，且 f15 0 则令 1=min(f15,5)=min(3,2)并给V1标号（-V5，1）=（-V5，2）,-V5，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,检查 V5 点的相邻点 VtVt点满足(V5,Vt)E，且 f5t=C

24、5t因此先不考虑,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,检查 V1 点的相邻点 V4V4点满足(V1,V4)E，且 f14 C144=min(C14 f14,1)=min(5-2,2)=2并给V4标号（+V1，4）=（+V1，2）,+V1，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,检查 V4 点的相邻点 Vt

25、Vt点满足(V4,Vt)E，且 f4t C4tt=min(C4t f4t,t)=min(4-2,2)=2并给Vt标号（+V4，t）=（+V4，2）,+V4，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,11.5 最大流问题,最大流的标号算法 如若Vt得到标号，说明存在一条可增广链，进行调整，反之计算结束。2.调整过程（1）若(vi,vj)是可增广链上的前向边，则f ij=fij+t 若(vi,vj)是可增广链上的后向边，则f ij=fij-t 若(vi,vj)不在可增广链上，则f ij=fij（2）去掉所有标号，回到第1步,，+,+Vs，2,+V

26、s，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,11.5 最大流问题,最大流的标号算法 如若Vt得到标号，说明存在一条可增广链，进行调整，反之计算结束。2.调整过程（1）若(vi,vj)是可增广链上的前向边，则f ij=

27、fij+t 若(vi,vj)是可增广链上的前后边，则f ij=fij-t 若(vi,vj)不在可增广链上，则f ij=fij（2）去掉所有标号，回到第1步,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,t=2,即为调整量，从Vs点开始，链上所有的正向边流量加2，反向边流量减2,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,t=2,即为调整量，从Vs点开始，链上所有的正向边流量加2，反向边流量减2,11.5 最大流问题,最大流的标号算法 如若Vt得到标号，说明存在一条可增广链，进行调整，反之计算结束。2.调整

28、过程（1）若(vi,vj)是可增广链上的前向边，则f ij=fij+t 若(vi,vj)是可增广链上的前后边，则f ij=fij-t 若(vi,vj)不在可增广链上，则f ij=fij（2）去掉所有标号，回到第1步,，+,+Vs，2,+Vs，1,(3,0),+V2，2,-V5，2,+V1，2,+V4，2,t=2,即为调整量，从Vs点开始，链上所有的前向边流量加2，后向边流量减2,，+,+Vs，2,+Vs，1,(3,2),+V2，2,-V5，2,+V1，2,+V4，2,t=2,即为调整量，从Vs点开始，链上所有的前向边流量加2，后向边流量减2,11.5 最大流问题,最大流的标号算法 如若Vt得到

29、标号，说明存在一条可增广链，进行调整，反之计算结束。2.调整过程（1）若(vi,vj)是可增广链上的前向边，则f ij=fij+t 若(vi,vj)是可增广链上的后向边，则f ij=fij-t 若(vi,vj)不在可增广链上，则f ij=fij（2）去掉所有标号，回到第1步,(3,2),(3,2),，+,+Vs，1,如若Vt得到标号，说明存在一条可增广链，进行调整，反之计算结束。,(3,2),此时：W=fS1 fS2 fS3=f4t f5t f6t=11即为最大流的流量,11.5 最大流问题,习题,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3

30、),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1

31、）,(1,1),，+,+V1,4,11.5 最大流问题,最大流的标号算法1.标号过程（1）给发点以标号（，+）（2）选择边一个已标号的顶点Vi,对于Vi的所有未给标号的相邻点Vj 按下列规则处理：a)若边(vj,vi)E，且fji 0 则令 j=min(fji,i)并给vj标号（-vi，j）b)若边(vi,vj)E，且fij cij则令 j=min(cij-fij,i)并给vj标号（+vi，j）重复（2）直到收点Vt 被标号或不再有顶点可标号为止。,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1)

32、,（1,1）,(1,1),，+,+V1,4,-V3,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5

33、,1),（1,1）,(1,1),，+,+V1,4,-V3,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3)

34、,(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,1,+V4,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,1,+V5,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,

35、1,+V4,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,1,+V4,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,1,+V4,1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0

36、),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,1,+V4,1,6=1,即为调整量，从Vs点开始，链上所有的前向边流量加1，后向边流量减1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,3),(5,3),(3,0),(2,1),(2,2),(5,1),（1,1）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,1,+V4,1,6=1,即为调整量，从Vs点开始，链上所有的前向边流量加1，后向边流量减1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4

37、,4),(5,4),(3,0),(2,1),(2,2),(5,2),（1,0）,(1,1),，+,+V1,4,-V3,1,+V2,1,-V2,1,+V4,1,6=1,即为调整量，从Vs点开始，链上所有的前向边流量加1，后向边流量减1,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,4),(5,5),(3,0),(2,1),(2,2),(5,2),（1,0）,(1,1),，+,+V1,3,标号过程中断,不能标到V6，说明不存在一条可增广链，计算结束。,11.5 最大流问题,习题,V6,(3,3),V1,V2,V3,V5,V4,(4,4),(5,4),(3,0),(2,1),(2,2),(5,2),（1,0）,(1,1),此时：W=f12 f13=f46 f56=5即为最大流的流量,