第六章 网络流图问题.ppt

1、1,图论Graphic Theory,阙夏制作,2,第六章 网络流图问题,6-1 网络流图问题和最大流 6-2 割切 6-3 Ford-Fulkerson最大流最小割切定理 6-4 2F最大流最小割切标号算法 6-5 Edmonds-Karp修正算法，Dinic算法,3,6-1 网络流图问题和最大流,把一种产品从产地通过铁路或公路网运往市场，交通网络中每一段的运输能力有一定限度，问如何安排，使得运输最快？ 这个问题在运输调度工作中是重要内容之一，同时也是运筹学许多问题的模型。,4,1 网络流图问题和最大流-例,5,1 网络流图问题和最大流1,定义：带权的有向图G=(V,E)，满足以下条件，则称

2、为网络流图(flow network)。 （1）仅有一个入度为0的顶点s，称s为源点(source)或发点； （2）仅有一个出度为0的顶点t，称S为汇点(sink)或沟或收点； （3）每条边的权值都为非负数，称为该边的容量，记作c(i,j)。,6,1 网络流图问题和最大流-例,下图所示就是一个网络流图：,例,源点,汇点,容量,中转站,7,1 网络流图问题和最大流-2,对于网络流图G，每条边都给定一个非负数fij，这组数满足下面条件，称为网络的容许流(flow)，记作f。 （1）0fij c(i,j)； （2）除源点s和汇点t，其余顶点vi恒有： fij fki j k 即每个点流入和流出量相同

3、； （3）对于源点s和汇点t有： fsi fjtw i j w称为网络流的流量。,源点流出的量 汇点流入的量,8,1 网络流图问题和最大流-3,下图所示就是一个网络流图上的容许流：,例,容量,容许流fat,9,1 网络流图问题和最大流-4,对于下图，根据各点能量守恒的关系，可分别得下列各式： fsa+fsb+fsc=w (1) fat+fbt+fdt=w (2) fsa+fbafat+fab (3) fsb+fcb+fabfba+fbt+fbd (4) fscfcb+fcd (5) fbd+fcdfdt (6) 0fsa4， 0fsb3， 0fsc4， 0fab2， 0fba3， 0fat3，

4、 0fbt2， 0fbd2， 0fcb1， 0fcd2， 0fdt2， w0,现要求满足这些 不等式的最大w,10,6-2 割切,图G=(V,E)是已知的网络流图，假设S是V的一个子集，而且S满足以下条件： （1）sS （2）tS,11,2 割切-2,在边集(S, )中，把从S到 的边的容量之和称为割切的容量，记作C(S, ) ，即 C(S, )=,12,2 割切-定理6.1,网络容许流量和割切容量之间存在下述关系： 定理6.1：网络流的最大流量小于等于的任意的割切容量，即：max w C(S, )。,13,2 割切-定理6.1证明,当i点既不是源点s，也不是汇点t的任意点时，恒有：fijfj

5、i0 (1) jV jV 但i为源点s时有fsjw (2) jV 从(1)、(2)对iS求得 fij-fjiw iS, jV,证明,0,w,14,2 割切-定理6.1证明1,证明,又 0fijcij, fijfjifijcij,因为割切是任意的，所以得证。,15,6-3 Ford-Fulkerson最大流最小割切定理,定理6.2：在一个给定的网络流图上，其最大流量等于其最小割切的容量，即： max wmin,16,3 2F最大流最小切割定理1,如果网络的容许流不是最大的，则一定存在一条从s到t的增流路径。,什么样的路径 才是增流路径呢？,17,3 2F最大流最小切割定理2,令s,i1,i2,i

6、k,t是一条从s到t的路径Pst，其中： 边的方向是从ij-1到ij的，称为向前边； 边的方向是从ij到ij-1的 ，称为后退边；,后退边,向前边,18,3 2F最大流最小切割定理3,如果路径上全部都是向前边，且每条边eij都有fijcij，那么令=min(cij-fij)，这时令Pst上每条边的流都增加，结果仍是网络的容许流，但整个路径的流量比原来增加了。所以Pst是一条增流路径。,=min(cij-fij)=1,19,3 2F最大流最小切割定理4,如果路径上有向前边也有后退边，则在向前边中，令1=min(cij-fij)， 2=minfji， =min(1,2)，这时令Pst上每条向前边的

7、流都增加，后退边减少，结果仍是网络的容许流，但整个路径的流量比原来增加了。,=min(1, 2)=2,20,3 2F最大流最小切割定理5,注：网络里只存在上述的两类增流路径。,21,3 2F最大流最小切割定理例,求下图的最大流。,例,22,3 2F最大流最小切割定理例解1,如果最初的fij0，即w0，如下图所示：,解,23,3 2F最大流最小切割定理例解2,则发现的第一条增流路径可以是：(s,c,b,t),解,它全部由向前边组成，且2，所以可增流2。,24,3 2F最大流最小切割定理例解3,第二条增流路径是：(s,a,b,c,d,t),解,它由向前边和后退边组成。,1=1 ，2=2 ， =mi

8、n(1, 2)=1，所以此路径可增流1。,25,3 2F最大流最小切割定理例解4,在图中再也找不到增流路径，所以这时的网络流最大流量w3。,解,26,6-4 2F最大流最小切割标号算法,1962年，Ford和Fulkerson对于求最大网络流给出了一个有效算法，我们简称为2F算法。 算法包括两个过程： （1）标号过程； （2）增流过程；,27,4 2F最大流最小切割标号算法1,标号的约定： 源点s标号：标以(-,)； 正向标号：如果e=(vi,vj)且fijcij，顶点vj得到标号(vi+, ij) ，ijcij-fij ； 反向标号：如果e=(vj,vi)且fji0，顶点vj得到标号(vi-

9、, ij)， ijfji；,如果顶点关联的边为 饱和边，则无需标号,28,4 2F最大流最小切割标号算法2,什么是饱和边？ 向前边：fijcij时 后退边： fij0时 称为饱和边；,29,4 2F标号算法描述,2F算法描述： （1）初始化f(e)=0，eE； /初始化 （2）给源点s标号(-,)，其它顶点均未标号； （3）依次选一个未标号的顶点，根据其方向进行标号，若当前标号的顶点为t，转（4），否则转入（6）； （4）选择一条标号过的增流路径进行增流； （5）转（2） （6）这时得到的f就是最大容许流。,30,4 2F标号算法例,用2F标号算法求下图的最大流。,例,31,4 2F标号算法例

10、解1,（1）对所有eE，有f(e)=0；,解,32,4 2F标号算法例解2,（2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),33,4 2F标号算法例解3,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-, ),(s+, 2),(b+, 4),(a+, 7),(c+, 5),34,4 2F标号算法例解4,（4）对标号过的增流路径进行增流； 增流路径为：(s,a,b,c,t),解,(-, ),(s+, 2),(b+, 4),(a+, 7),(c+, 5),=min(cij-fij)=2,35,4 2F标号算

11、法例解5,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),36,4 2F标号算法例解6,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-, ),(s+, 9),(a+, 8),(b+, 6),37,4 2F标号算法例解7,（4）对标号过的增流路径进行增流； 增流路径为：(s,b,a,t),解,(-, ),=min(cij-fij)=6,38,4 2F标号算法例解8,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),39,4 2F标号算法例解9,（3）选可进行

12、正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-, ),(s+, 3),(b-, 2),(a+, 2),40,4 2F标号算法例解10,（4）对标号过的增流路径进行增流； 增流路径为：(s,b,a,t),解,(-, ),1=min(cij-fij)=2,2=fji=2,=min(1,2)=2,41,4 2F标号算法例解11,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),42,4 2F标号算法例解12,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时

13、，转入（6）；,解,(-, ),(s+, 1),(b+, 2),(c+, 3),43,4 2F标号算法例解13,（4）对标号过的增流路径进行增流； 增流路径为：(s,b,c,t),解,(-, ),=min(cij-fij)=1,44,4 2F标号算法例解14,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),45,4 2F标号算法例解15,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-, ),(s+, 3),(b+, 2),46,4 2F标号算法例解16,（4）对标号过的增流路径进行增流

14、； 增流路径为：(s,c,t),解,(-, ),=min(cij-fij)=2,47,4 2F标号算法例解17,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),48,4 2F标号算法例解18,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-, ),49,4 2F标号算法例解19,（6）这时得到的f就是最大容许流。,解,(-, ),这时得到的w13就是我们要求的最大流。,(s+, 1),(c-, 3),50,4 2F标号算法例解20,这时得到标号得顶点为S，没有得到标号的为S，此时(S,S

15、)=,，C(S,S)=13,解,(-, ),(s+, 1),(c-, 3),51,课堂练习,用2F算法求下图所示的网络流图的最大流。,52,5 Edmonds-Karp修正算法，Dinic算法例解1,若标号次序出现特殊情况，如下图所示：,(-,),出现增流路径如图所示，增流1,解,53,5 Edmonds-Karp修正算法，Dinic算法例解1,若标号次序出现特殊情况，如下图所示：,(-,),出现增流路径如图所示，增流1,解,54,5 Edmonds-Karp修正算法，Dinic算法例解2,上述两条增流路径如此交替出现，需要进行220次才能求出最大流。,55,6-5 Edmonds-Karp修

16、正算法，Dinic算法,在2F算法中，对顶点的标号是任意的，也就是说，增流路径的形成也是任意的。这样算法虽然方便，但同时存在很严重的缺陷。,56,一、Edmonds-Karp修正算法,为了避免出现刚才所述问题，Edmonds和Karp在1972年提出了一个严密的标号算法： 在每一次都沿一条最短的增流路径增流。,57,一、Edmonds-Karp修正算法1,Edmonds-Karp算法描述： （1）对所有eE，有f(e)=0；/初始化 （2）给源点s标号(-,)，其它顶点均未标号； （3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）； （4）选一条标号过的增

17、流路径进行增流； （5）转（2） （6）这时得到的f就是最大容许流。,58,一、Edmonds-Karp算法-例,用Edmonds-Karp算法求下图的最大流。,例,59,一、Edmonds-Karp算法-例解,（1）初始化f(e)=0，eE；,解,60,一、Edmonds-Karp算法-例解1,（2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),61,一、Edmonds-Karp算法-例解2,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-, ),(s+, 2),(a+, 8),(s+, 9),(s+, 3),62,一、Edmo

18、nds-Karp算法-例解3,（4）选一条标号过的增流路径进行增流； 增流路径为：(s，a，t),解,(-, ),(s+, 2),(a+, 8),(s+, 9),(s+, 3),=min(cij-fij)=2,63,一、Edmonds-Karp算法-例解4,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),64,一、Edmonds-Karp算法-例解5,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-, ),(b+, 6),(c+, 5),(s+, 9),(s+, 3),65,一、Edmonds-Karp算法-例

19、解6,（4）选一条标号过的增流路径进行增流； 增流路径为：(s，c，t),解,(-, ),(b+, 6),(c+, 5),(s+, 9),(s+, 3),=min(cij-fij)=3,66,一、Edmonds-Karp算法-例解7,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),67,一、Edmonds-Karp算法-例解8,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-, ),(b+, 6),(a+, 6),(s+, 9),(b+, 4),68,一、Edmonds-Karp算法-例解9,（4）选一条标号过

20、的增流路径进行增流； 增流路径为：(s，a，t),解,(-, ),(b+, 6),(a+, 6),(s+, 9),(b+, 4),=min(cij-fij)=6,69,一、Edmonds-Karp算法-例解10,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),70,一、Edmonds-Karp算法-例解11,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-, ),(c+, 2),(s+, 3),(b+, 4),71,一、Edmonds-Karp算法-例解12,（4）选一条标号过的增流路径进行增流； 增流路径为：

21、(s，c，t)；,解,(-, ),(c+, 2),(s+, 3),(b+, 4),=min(cij-fij)=2,72,一、Edmonds-Karp算法-例解13,（5）转（2） （2）给源点s标号(-,)，其它顶点均未标号；,解,(-, ),73,一、Edmonds-Karp算法-例解14,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-, ),(s+, 3),(b+, 4),74,一、Edmonds-Karp算法-例解15,（6）这时得到的f就是最大容许流。,解,(-, ),这时得到的w13也是我们要求的最大流。,(s+, 3),(b+,

22、 4),75,一、Edmonds-Karp算法-例解16,这时得到标号得顶点为S，没有得到标号的为S，此时(S,S)=,，C(S,S)=13,解,(-, ),(s+, 3),(b+, 4),76,二、Dinic算法,1970年，Dinic举了坏例说明2F算法的弱点，并设计了一种所谓分层算法，可以避免求最大流时，其运算的时间复杂度依赖边的权值的缺点。,77,二、Dinic算法1,Dinic算法的特点是： 将顶点按其与源点s的最短距离分层。,78,二、Dinic算法2,如果说，2F算法采用DFS策略； 那么，EK算法就是采用了BFS策略； 而，Dinic算法则兼采两者。,79,二、Dinic算法分

23、层描述,Dinic分层算法描述： （1）L0=s，i=0，R=V-L0；/分层初始化 （2）S=v|vR，且存在从Li某顶点到v的未饱和边； （3）若S=，则网络流已达到最大，停止； （4）i=i+1，Li=S，R=R-Li； （5）若tS，则分层停止，否则令S=，转（2）；,80,二、Dinic算法分层描述例,对下图进行分层：,例,81,二、Dinic算法分层描述例解,L0=s,解,0层,S=a,c；,82,二、Dinic算法分层描述例解1,L0=s ，L1=a,c,解,1层,0层,S=b,d；,83,二、Dinic算法分层描述例解2,L0=s ，L1=a,c ，L2=b,d,解,1层,0层,2层,S=t；,84,二、Dinic算法分层描述例解3,L0=s ，L1=a,c ，L2=b,d ，L3=t,解