图论第12讲.ppt

《图论第12讲.ppt》由会员分享，可在线阅读，更多相关《图论第12讲.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论图论Graphic Theory阙夏制作1第六章第六章 网络流图问题网络流图问题1 网络流图问题和最大流2 割切3 Ford-Fulkerson最大流最小割切定理4 2F最大流最小割切标号算法5 Edmonds-Karp修正算法，Dinic算法24 2F标号算法例标号算法例用2F标号算法求下图的最大流。例例sabct9572438634 2F标号算法例解标号算法例解1（1）对所有eE，有f(e)=0；解解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)44 2F标号算法例解标号算法例解2（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(

2、9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,)54 2F标号算法例解标号算法例解3（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,)(s+,2 2)(b+,4 4)(a+,7 7)(c+,5 5)64 2F标号算法例解标号算法例解4（4）对标号过的增流路径进行增流；增流路径为：(s,a,b,c,t)解解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)

3、(-,)(s+,2 2)(b+,4 4)(a+,7 7)(c+,5 5)(2,2)(7,2)(4,2)(5,2)=min(cij-fij)=274 2F标号算法例解标号算法例解5（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,)84 2F标号算法例解标号算法例解6（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解解sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,)(s+,

4、9 9)(a+,8 8)(b+,6 6)94 2F标号算法例解标号算法例解7（4）对标号过的增流路径进行增流；增流路径为：(s,b,a,t)解解sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,)(s+,9 9)(a+,8 8)(b+,6 6)(8,6)(9,6)(6,6)=min(cij-fij)=6104 2F标号算法例解标号算法例解8（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,)114 2F标号算法例解标号算法例解9（3）选可进

5、行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解解sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,)(s+,3 3)(b-,2 2)(a+,2 2)124 2F标号算法例解标号算法例解10（4）对标号过的增流路径进行增流；增流路径为：(s,b,a,t)解解sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,)(s+,3 3)(b-,2 2)(a+,2 2)1=min(cij-fij)=22=fji=2=min(1,2)=2(9,8)(7,0)(8,

6、8)134 2F标号算法例解标号算法例解11（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,)144 2F标号算法例解标号算法例解12（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,)(s+,1 1)(b+,2 2)(c+,3 3)154 2F标号算法例解标号算法例解13（4）对标号过的增流路径进行增流；增流路径为：(s

7、,b,c,t)解解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,)(s+,1 1)(b+,2 2)(c+,3 3)=min(cij-fij)=1(9,9)(4,3)(5,3)164 2F标号算法例解标号算法例解14（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,9)(5,3)(7,0)(2,2)(4,3)(3,0)(8,8)(6,6)(-,)174 2F标号算法例解标号算法例解15（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解解sabct(9,

8、9)(5,3)(7,0)(2,2)(4,3)(3,0)(8,8)(6,6)(-,)(s+,3 3)(b+,2 2)184 2F标号算法例解标号算法例解16（4）对标号过的增流路径进行增流；增流路径为：(s,c,t)解解sabct(9,9)(5,3)(7,0)(2,2)(4,3)(3,0)(8,8)(6,6)(-,)(s+,3 3)(b+,2 2)=min(cij-fij)=2(3,2)(5,5)194 2F标号算法例解标号算法例解17（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)

9、204 2F标号算法例解标号算法例解18（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解解sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)(s+,1 1)(c-,3 3)214 2F标号算法例解标号算法例解19（6）这时得到的f就是最大容许流。解解sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)这时得到的w13就是我们要求的最大流。(s+,1 1)(c-,3 3)224 2F标号算法例解标号算法例解20 这时得到标号得顶点为S，

10、没有得到标号的为S，此时(S,S)=,，C(S,S)=13解解sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)(s+,1 1)(c-,3 3)23课堂练习课堂练习用2F算法求下图所示的网络流图的最大流。sabt120202020245 Edmonds-Karp修正算法，修正算法，Dinic算法例解算法例解1若标号次序出现特殊情况，如下图所示：sabt(1,0)(20,0)(20,0)(20,0)(20,0)(-,)(b+,20)(s+,20)(a+,1)出现增流路径如图所示，增流1解解(20,1)(1,1)(20,1)255 Edmonds-K

11、arp修正算法，修正算法，Dinic算法例解算法例解1若标号次序出现特殊情况，如下图所示：sabt(1,1)(20,1)(20,1)(20,0)(20,0)(-,)(a+,20)(s+,20)(b-,1)出现增流路径如图所示，增流1解解(20,1)(1,0)(20,1)265 Edmonds-Karp修正算法，修正算法，Dinic算法例解算法例解2 上述两条增流路径如此交替出现，需要进行220次才能求出最大流。sabt(1,0)(20,1)(20,1)(20,1)(20,1)(-,)(b-,1)(s+,20)(a+,20)sabt(1,1)(20,1)(20,1)(20,0)(20,0)(-,

12、)(s+,20)(a+,1)(b+,20)276-5 Edmonds-Karp修正算法，修正算法，Dinic算法算法 在2F算法中，对顶点的标号是任意的，也就是说，增流路径的形成也是任意的。这样算法虽然方便，但同时存在很严重的缺陷。28一、一、Edmonds-Karp修正算法修正算法 为了避免出现刚才所述问题，Edmonds和Karp在1972年提出了一个严密的标号算法：在每一次都沿一条最短的增流路径增流。29一、一、Edmonds-Karp修正算法修正算法1n nEdmonds-Karp算法描述：（1）对所有eE，有f(e)=0；/初始化（2）给源点s标号(-,)，其它顶点均未标号；（3）按

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

14、(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,)33一、一、Edmonds-Karp算法算法-例解例解2 （3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；解解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,)(s+,2 2)(a+,8 8)(s+,9 9)(s+,3 3)34一、一、Edmonds-Karp算法算法-例解例解3 （4）选一条标号过的增流路径进行增流；增流路径为：(s，a，t)解解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(

15、6,0)(-,)(s+,2 2)(a+,8 8)(s+,9 9)(s+,3 3)=min(cij-fij)=2(8,2)(2,2)35一、一、Edmonds-Karp算法算法-例解例解4（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,0)(5,0)(7,0)(2,2)(4,0)(3,0)(8,2)(6,0)(-,)36一、一、Edmonds-Karp算法算法-例解例解5 （3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；解解sabct(9,0)(5,0)(7,0)(2,2)(4,0)(3,0)(8,2)(6,0)(-,)(

16、b+,6 6)(c+,5 5)(s+,9 9)(s+,3 3)37一、一、Edmonds-Karp算法算法-例解例解6（4）选一条标号过的增流路径进行增流；增流路径为：(s，c，t)解解sabct(9,0)(5,0)(7,0)(2,2)(4,0)(3,0)(8,2)(6,0)(-,)(b+,6 6)(c+,5 5)(s+,9 9)(s+,3 3)=min(cij-fij)=3(3,3)(5,3)38一、一、Edmonds-Karp算法算法-例解例解7（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,0)(5,3)(7,0)(2,2)(4,0)(3,3)(8,2)(

17、6,0)(-,)39一、一、Edmonds-Karp算法算法-例解例解8（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；解解sabct(9,0)(5,3)(7,0)(2,2)(4,0)(3,3)(8,2)(6,0)(-,)(b+,6 6)(a+,6 6)(s+,9 9)(b+,4 4)40一、一、Edmonds-Karp算法算法-例解例解9（4）选一条标号过的增流路径进行增流；增流路径为：(s，a，t)解解sabct(9,0)(5,3)(7,0)(2,2)(4,0)(3,3)(8,0)(6,0)(-,)(b+,6 6)(a+,6 6)(s+,9 9)(

18、b+,4 4)=min(cij-fij)=6(6,6)(8,8)(9,6)41一、一、Edmonds-Karp算法算法-例解例解10（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,6)(5,3)(7,0)(2,2)(4,0)(3,3)(8,8)(6,6)(-,)42一、一、Edmonds-Karp算法算法-例解例解11（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；解解sabct(9,6)(5,3)(7,0)(2,2)(4,0)(3,3)(8,8)(6,6)(-,)(c+,2 2)(s+,3 3)(b+,4 4)43一、

19、一、Edmonds-Karp算法算法-例解例解12（4）选一条标号过的增流路径进行增流；增流路径为：(s，c，t)；解解sabct(9,6)(5,3)(7,0)(2,2)(4,0)(3,3)(8,8)(6,6)(-,)(c+,2 2)(s+,3 3)(b+,4 4)(9,8)(4,2)(5,5)=min(cij-fij)=244一、一、Edmonds-Karp算法算法-例解例解13（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；解解sabct(9,8)(5,5)(7,0)(2,2)(4,2)(3,3)(8,8)(6,6)(-,)45一、一、Edmonds-Karp算法算法-例解例解

20、14（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；解解sabct(9,8)(5,5)(7,0)(2,2)(4,2)(3,3)(8,8)(6,6)(-,)(s+,3 3)(b+,4 4)46一、一、Edmonds-Karp算法算法-例解例解15（6）这时得到的f就是最大容许流。解解sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)这时得到的w13也是我们要求的最大流。(s+,3 3)(b+,4 4)47一、一、Edmonds-Karp算法算法-例解例解16 这时得到标号得顶点为S，没有得到标号的为S，此时

21、(S,S)=,，C(S,S)=13解解sabct(9,9)(5,5)(7,0)(2,2)(4,3)(3,2)(8,8)(6,6)(-,)(s+,3 3)(b+,4 4)48二、二、Dinic算法算法 1970年，Dinic举了坏例说明2F算法的弱点，并设计了一种所谓分层算法，可以避免求最大流时，其运算的时间复杂度依赖边的权值的缺点。49二、二、Dinic算法算法1Dinic算法的特点是：将顶点按其与源点s的最短距离分层。50二、二、Dinic算法算法2如果说，2F算法采用DFS策略；那么，EK算法就是采用了BFS策略；而，Dinic算法则兼采两者。51二、二、Dinic算法分层描述算法分层描述

22、n nDinic分层算法描述：（1）L0=s，i=0，R=V-L0；/分层初始化（2）M=v|vR，且存在从Li某顶点到v的未 饱和边；（3）若M=，分层停止，网络流已达到最大；（4）若tM，i=i+1，Li=t，分层停止，否则i=i+1，Li=M，R=R-Li，转（2）；52二、二、Dinic算法分层描述例算法分层描述例对下图进行分层：例例sabct(9,0)(15,0)(17,0)(20,0)(3,0)d(15,0)(12,0)(5,0)53二、二、Dinic算法分层描述例解算法分层描述例解L0=s解解sabct(9,0)(15,0)(17,0)(20,0)(3,0)d(15,0)(12,

23、0)(5,0)0层M=a,c；54二、二、Dinic算法分层描述例解算法分层描述例解1L0=s，L1=a,c解解sabct(9,0)(15,0)(17,0)(20,0)(3,0)d(15,0)(12,0)(5,0)1层0层M=b,d；55二、二、Dinic算法分层描述例解算法分层描述例解2L0=s，L1=a,c，L2=b,d解解sabct(9,0)(15,0)(17,0)(20,0)(3,0)d(15,0)(12,0)(5,0)1层0层2层M=t；56二、二、Dinic算法分层描述例解算法分层描述例解3L0=s，L1=a,c，L2=b,d，L3=t解解sabct(9,0)(15,0)(17,0

24、)(20,0)(3,0)d(15,0)(12,0)(5,0)1层0层2层3层57二、二、Dinic算法最大流算法算法最大流算法n nDinic最大流算法：（1）对所有eE，f(e)=0；/初始化（2）对图进行分层；（3）对图中增流路径增流；（4）去掉图中饱和边，调整c(e)和f(e)值；（5）转（2）；58二、二、Dinic算法例算法例用Dinic算法求下图最大流：例例sabct91517203d1512559二、二、Dinic算法例算法例解解（1）对所有eE，f(e)=0；解解sabct(9,0)(15,0)(17,0)(20,0)(3,0)d(15,0)(12,0)(5,0)60二、二、D

25、inic算法例解算法例解1（2）对图进行分层；解解sabct(9,0)(15,0)(17,0)(20,0)(3,0)d(15,0)(12,0)(5,0)1层0层2层3层L0=s，L1=a,c，L2=b,d，L3=t61二、二、Dinic算法例解算法例解2（3）对图中增流路径增流；解解sabct(9,0)(15,0)(17,0)(20,0)(3,0)d(15,0)(12,0)(5,0)1层0层2层3层(20,12)(17,12)(12,12)(9,9)(15,9)(15,9)62二、二、Dinic算法例解算法例解2（4）去掉图中饱和边，调整c(e)和f(e)值；解解sabct(15,9)(17,

26、12)(20,12)(3,0)d(15,9)(5,0)(9,9)(12,12)(8,0)(5,0)(6,0)(5,0)63二、二、Dinic算法例解算法例解4（5）转（2）；（2）对图进行分层；解解sabct(6,0)(5,0)(8,0)(3,0)d(6,0)(5,0)0层1层2层3层4层5层L0=sL1=aL2=bL3=cL4=dL5=tsabct(6,0)(8,0)(3,0)d(6,0)(5,0)0层1层2层3层4层5层64二、二、Dinic算法例解算法例解5（3）对图中增流路径增流；解解sabct(6,0)(5,0)(8,0)(3,0)d(6,0)(5,0)sabct(6,0)(8,0)

27、(3,0)d(6,0)(5,0)1层0层2层3层4层5层(3,3)(5,3)(8,3)(6,3)(6,3)(3,3)(6,3)(6,3)(8,3)(5,3)65二、二、Dinic算法例解算法例解2（4）去掉图中饱和边，调整c(e)和f(e)值；解解(3,3)sabct(6,3)(5,3)(8,3)d(6,3)(5,0)(5,0)(2,0)(3,0)(3,0)66二、二、Dinic算法例解算法例解7（2）对图进行分层；解解sab(5,0)(2,0)0层1层2层sabct(3,0)(2,0)(5,0)d(3,0)(5,0)L0=s0层1层2层L1=aL2=b67二、二、Dinic算法例算法例解解8

28、w=24即为最大流解解sabct(9,9)(15,12)(17,15)(20,15)(3,3)d(15,12)(12,12)(5,0)68二、二、Dinic算法例算法例解解9 把已分层的顶点看为S，其余顶点的为S，此时(S,S)=,，C(S,S)=9+12+3=24解解sabct(9,9)(15,12)(17,15)(20,15)(3,3)d(15,12)(12,12)(5,0)69三、最大流问题的推广三、最大流问题的推广n n多产地多销问题：s1s2s3snt1t2t3tmts70三、最大流问题的推广三、最大流问题的推广n n顶点具有容量的网络：vivi2vi171三、最大流问题的推广三、最大流问题的推广如图：bsta344423sta23444a1b1b23272课后练习题课后练习题1、分别用Edmonds-Karp算法和Dinic算法求下图的最大流。sabet108843f232cd53967374