第六章、网络流.ppt

1,第六章网络流图问题,1网络流图问题和最大流2割切3Ford-Fulkerson最大流最小割切定理42F最大流最小割切标号算法5Edmonds-Karp修正算法，Dinic算法,应用篇,2,1网络流图问题和最大流,把一种产品从产地通过铁路或公路网运往市场，交通网络中每一段的运输能力有一定限度，问如何安排，使得运输最快？这个问题在运输调度工作中是重要内容之一，同时也是运筹学许多问题的模型。,3,1网络流图问题和最大流-例,4,1网络流图问题和最大流1,定义：带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flownetwork)。（1）仅有一个入度为0的顶点s，称s为源点(source)或发点；（2）仅有一个出度为0的顶点t，称S为汇点(sink)或沟或收点；（3）每条边的权值都为非负数，称为该边的容量，记作c(i,j)。,5,1网络流图问题和最大流-例,下图所示就是一个网络流图：,例,源点,汇点,容量,中转站,6,1网络流图问题和最大流-2,对于网络流图G，每条边都给定一个非负数fij，这组数满足下面条件，称为网络的容许流(flow)，记作f。（1）0fijc(i,j)；（2）除源点s和汇点t，其余顶点vi恒有：fijfkijk即每个点流入和流出量相同；（3）对于源点s和汇点t有：fsifjtwijw称为网络流的流量。,源点流出的量汇点流入的量,7,1网络流图问题和最大流-3,下图所示就是一个网络流图上的容许流：,例,容量,容许流fat,8,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，0fbt2，0fbd2，0fcb1，0fcd2，0fdt2，w0,9,2割切,图G=(V,E)是已知的网络流图，假设S是V的一个子集，而且S满足以下条件：（1）sS（2）tS,10,2割切-2,在边集(S,)中，把从S到的边的容量之和称为割切的容量，记作C(S,)，即C(S,)=,11,2割切-定理6.1,网络容许流量和切割容量之间存在下述关系：定理6.1：网络流的最大流量小于等于的任意的割切容量，即：maxwC(S,)。,12,2割切-定理6.1证明,当i点既不是源点s，也不是汇点t的任意点时，恒有：fijfji0(1)jVjV但i为源点s时有fsjw(2)jV从(1)、(2)对iS求得fij-fjiwiS,jV,证明,0,w,13,2割切-定理6.1证明1,证明,又0fijcij,fijfjifijcij,因为割切是任意的，所以得证。,14,3Ford-Fulkerson最大流最小割切定理,定理6.2：在一个给定的网络流图上，其最大流量等于其最小割切的容量，即：maxwmin,15,32F最大流最小切割定理1,如果网络的容许流不是最大的，则一定存在一条从s到t的增流路径。,什么样的路径才是增流路径呢？,16,32F最大流最小切割定理2,令s,i1,i2,ik,t是一条从s到t的路径Pst，其中：边的方向是从ij-1到ij的，称为向前边；边的方向是从ij到ij-1的，称为后退边；,后退边,向前边,17,32F最大流最小切割定理3,如果路径上全部都是向前边，且每条边eij都有fijcij，那么令=min(cij-fij)，这时令Pst上每条边的流都增加，结果仍是网络的容许流，但整个路径的流量比原来增加了。所以Pst是一条增流路径。,=min(cij-fij)=1,18,32F最大流最小切割定理4,如果路径上有向前边也有后退边，则在向前边中，令1=min(cij-fij)，2=minfji，=min(1,2)，这时令Pst上每条向前边的流都增加，后退边减少，结果仍是网络的容许流，但整个路径的流量比原来增加了。,=min(1,2)=2,19,32F最大流最小切割定理5,注：网络里只存在上述的两类增流路径。,20,32F最大流最小切割定理例,求下图的最大流。,例,21,32F最大流最小切割定理例解1,如果最初的fij0，即w0，如下图所示：,解,22,32F最大流最小切割定理例解2,则发现的第一条增流路径可以是：(s,c,b,t),解,它全部由向前边组成，且2，所以可增流2。,23,32F最大流最小切割定理例解3,第二条增流路径是：(s,a,b,c,d,t),解,它由向前边和后退边组成。,1=1，2=2，=min(1,2)=1，所以此路径可增流1。,24,32F最大流最小切割定理例解4,在图中再也找不到增流路径，所以这时的网络流最大流量w3。,解,25,42F最大流最小切割标号算法,1962年，Ford和Fulkerson对于求最大网络流给出了一个有效算法，我们简称为2F算法。算法包括两个过程：（1）标号过程；（2）增流过程；,26,42F最大流最小切割标号算法1,标号的约定：源点s标号：标以(-,)；正向标号：如果e=(vi,vj)且fijcij，顶点vi得到标号(vi+,ij)，ijcij-fij；反向标号：如果e=(vj,vi)且fji0，顶点vi得到标号(vi-,ij)，ijfji；,如果顶点关联的边为饱和边，则无需标号,27,42F最大流最小切割标号算法2,什么是饱和边？向前边：fijcij时后退边：fij0时称为饱和边；,28,42F标号算法描述,2F算法描述：（1）初始化f(e)=0，eE；/初始化（2）给源点s标号(-,)，其它顶点均未标号；（3）依次选一个未标号的顶点，根据其方向进行标号，若当前标号的顶点为t，转（4），否则转入（6）；（4）选择一条标号过的增流路径进行增流；（5）转（2）（6）这时得到的f就是最大容许流。,29,42F标号算法例,用2F标号算法求下图的最大流。,例,30,42F标号算法例解1,（1）对所有eE，有f(e)=0；,解,31,42F标号算法例解2,（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),32,42F标号算法例解3,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-,),(s+,2),(b+,4),(a+,7),(c+,5),33,42F标号算法例解4,（4）对标号过的增流路径进行增流；增流路径为：(s,a,b,c,t),解,(-,),(s+,2),(b+,4),(a+,7),(c+,5),=min(cij-fij)=2,34,42F标号算法例解5,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),35,42F标号算法例解6,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-,),(s+,9),(a+,8),(b+,6),36,42F标号算法例解7,（4）对标号过的增流路径进行增流；增流路径为：(s,b,a,t),解,(-,),=min(cij-fij)=6,37,42F标号算法例解8,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),38,42F标号算法例解9,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-,),(s+,3),(b-,2),(a+,2),39,42F标号算法例解10,（4）对标号过的增流路径进行增流；增流路径为：(s,b,a,t),解,(-,),1=min(cij-fij)=2,2=fji=2,=min(1,2)=2,40,42F标号算法例解11,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),41,42F标号算法例解12,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-,),(s+,1),(b+,2),(c+,3),42,42F标号算法例解13,（4）对标号过的增流路径进行增流；增流路径为：(s,b,c,t),解,(-,),=min(cij-fij)=1,43,42F标号算法例解14,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),44,42F标号算法例解15,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-,),(s+,3),(b+,2),45,42F标号算法例解16,（4）对标号过的增流路径进行增流；增流路径为：(s,c,t),解,(-,),=min(cij-fij)=2,46,42F标号算法例解17,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),47,42F标号算法例解18,（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；,解,(-,),48,42F标号算法例解19,（6）这时得到的f就是最大容许流。,解,(-,),这时得到的w13也是我们要求的最大流。,(s+,1),(c-,3),49,42F标号算法例解20,这时得到标号得顶点为S，没有得到标号的为S，此时(S,S)=,，C(S,S)=13,解,(-,),(s+,1),(c-,3),50,课堂练习,用2F算法求下图所示的网络流图的最大流。,51,5Edmonds-Karp修正算法，Dinic算法例解1,若标号次序出现特殊情况，如下图所示：,(-,),出现增流路径如图所示，增流1,解,52,5Edmonds-Karp修正算法，Dinic算法例解1,若标号次序出现特殊情况，如下图所示：,(-,),出现增流路径如图所示，增流1,解,53,5Edmonds-Karp修正算法，Dinic算法例解2,上述两条增流路径如此交替出现，需要进行220次才能求出最大流。,54,5Edmonds-Karp修正算法，Dinic算法,在2F算法中，对顶点的标号是任意的，也就是说，增流路径的形成也是任意的。这样算法虽然方便，但同时存在很严重的缺陷。,55,一、Edmonds-Karp修正算法,为了避免出现刚才所述问题，Edmonds和Karp在1972年提出了一个严密的标号算法：在每一次都沿一条最短的增流路径增流。,56,一、Edmonds-Karp修正算法1,Edmonds-Karp算法描述：（1）对所有eE，有f(e)=0；/初始化（2）给源点s标号(-,)，其它顶点均未标号；（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；（4）选一条标号过的增流路径进行增流；（5）转（2）（6）这时得到的f就是最大容许流。,57,一、Edmonds-Karp算法-例,用Edmonds-Karp算法求下图的最大流。,例,58,一、Edmonds-Karp算法-例解,（1）初始化f(e)=0，eE；,解,59,一、Edmonds-Karp算法-例解1,（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),60,一、Edmonds-Karp算法-例解2,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-,),(s+,2),(a+,8),(s+,9),(s+,3),61,一、Edmonds-Karp算法-例解3,（4）选一条标号过的增流路径进行增流；增流路径为：(s，a，t),解,(-,),(s+,2),(a+,8),(s+,9),(s+,3),=min(cij-fij)=2,62,一、Edmonds-Karp算法-例解4,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),63,一、Edmonds-Karp算法-例解5,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-,),(b+,6),(c+,5),(s+,9),(s+,3),64,一、Edmonds-Karp算法-例解6,（4）选一条标号过的增流路径进行增流；增流路径为：(s，c，t),解,(-,),(b+,6),(c+,5),(s+,9),(s+,3),=min(cij-fij)=3,65,一、Edmonds-Karp算法-例解7,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),66,一、Edmonds-Karp算法-例解8,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-,),(b+,6),(a+,6),(s+,9),(b+,4),67,一、Edmonds-Karp算法-例解9,（4）选一条标号过的增流路径进行增流；增流路径为：(s，a，t),解,(-,),(b+,6),(a+,6),(s+,9),(b+,4),=min(cij-fij)=6,68,一、Edmonds-Karp算法-例解10,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),69,一、Edmonds-Karp算法-例解11,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-,),(c+,2),(s+,3),(b+,4),70,一、Edmonds-Karp算法-例解12,（4）选一条标号过的增流路径进行增流；增流路径为：(s，c，t)；,解,(-,),(c+,2),(s+,3),(b+,4),=min(cij-fij)=2,71,一、Edmonds-Karp算法-例解13,（5）转（2）（2）给源点s标号(-,)，其它顶点均未标号；,解,(-,),72,一、Edmonds-Karp算法-例解14,（3）按层次依次对可以标号的顶点进行标号，若当前标号的顶点为t，转（4），否则转入（6）；,解,(-,),(s+,1),(b+,2),73,一、Edmonds-Karp算法-例解15,（6）这时得到的f就是最大容许流。,解,(-,),这时得到的w13也是我们要求的最大流。,(s+,3),(b+,4),74,一、Edmonds-Karp算法-例解16,这时得到标号得顶点为S，没有得到标号的为S，此时(S,S)=,，C(S,S)=13,解,(-,),(s+,3),(b+,4),75,二、Dinic算法,1970年，Dinic举了坏例说明2F算法的弱点，并设计了一种所谓分层算法，可以避免求最大流时，其运算的时间复杂度依赖边的权值的缺点。,76,二、Dinic算法1,Dinic算法的特点是：将顶点按其与源点s的最短距离分层。,77,二、Dinic算法2,如果说，2F算法采用DFS策略；那么，EK算法就是采用了BFS策略；而，Dinic算法则兼采两者。,78,二、Dinic算法分层描述,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）；,79,二、Dinic算法分层描述例,对下图进行分层：,例,80,二、Dinic算法分层描述例解,L0=s,解,0层,S=a,c；,81,二、Dinic算法分层描述例解1,L0=s，L1=a,c,解,1层,0层,S=b,d；,82,二、Dinic算法分层描述例解2,L0=s，L1=a,c，L2=b,d,解,1层,0层,2层,S=t；,83,二、Dinic算法分层描述例解3