第六章、网络流

1第六章网络流图问题§1网络流图问题和最大流§2割切§3Ford-Fulkerson最大流最小割切定理§42F最大流最小割切标号算法§5Edmonds-Karp修正算法，Dinic算法应用篇2§1网络流图问题和最大流把一种产品从产地通过铁路或公路网运往市场，交通网络中每一段的运输能力有一定限度，问如何安排，使得运输最快？这个问题在运输调度工作中是重要内容之一，同时也是运筹学许多问题的模型。3§1网络流图问题和最大流-例产地市场中转站a中转站b中转站c中转站d443322241324§1网络流图问题和最大流－1定义：带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flownetwork)。（1）仅有一个入度为0的顶点s，称s为源点(source)或发点；（2）仅有一个出度为0的顶点t，称S为汇点(sink)或沟或收点；（3）每条边的权值都为非负数，称为该边的容量，记作c(i,j)。5§1网络流图问题和最大流-例下图所示就是一个网络流图：例stabcd44332224132源点汇点容量中转站6§1网络流图问题和最大流-2对于网络流图G，每条边都给定一个非负数fij，这组数满足下面条件，称为网络的容许流(flow)，记作f。（1）0≤fij≤c(i,j)；（2）除源点s和汇点t，其余顶点vi恒有：∑fij＝∑fkijk即每个点流入和流出量相同；（3）对于源点s和汇点t有：∑fsi＝∑fjt＝wijw称为网络流的流量。源点流出的量＝汇点流入的量7§1网络流图问题和最大流-3下图所示就是一个网络流图上的容许流：例stabcd(4,3)(4,3)(3,2)(3,0)(2,1)(2,2)(2,2)(4,4)(1,1)(3,2)(2,2)容量容许流fat8§1网络流图问题和最大流-4对于下图，根据各点能量守恒的关系，可分别得下列各式：fsa+fsb+fsc=w(1)fat+fbt+fdt=w(2)fsa+fba＝fat+fab(3)fsb+fcb+fab＝fba+fbt+fbd(4)fsc＝fcb+fcd(5)fbd+fcd＝fdt(6)0≤fsa≤4，0≤fsb≤3，0≤fsc≤4，0≤fab≤2，0≤fba≤3，0≤fat≤3，0≤fbt≤2，0≤fbd≤2，0≤fcb≤1，0≤fcd≤2，0≤fdt≤2，w≥0stabcd443322241329§2割切图G=(V,E)是已知的网络流图，假设S是V的一个子集，而且S满足以下条件：（1）s∈S（2）t∈S\令=V-S，即是S的补集。SSSS这样把顶点分为S和两个部分，s∈S，t∈。SS定义：起点在S，终点在的边的集合是割切，用(S,)表示。10§2割切-2在边集(S,)中，把从S到的边的容量之和称为割切的容量，记作C(S,)，即C(S,)=SSSstabcd44332224132S={s,b,c,d}，={a,t}SC(S,)=csa+cba+cbt+cdt=4+3+2+4=13SSSjSiijc(S,)={(s,a),(b,a),(b,t),(d,t)}S11§2割切-定理6.1网络容许流量和切割容量之间存在下述关系：定理6.1：网络流的最大流量小于等于的任意的割切容量，即：maxw≤C(S,)。S12§2割切-定理6.1证明当i点既不是源点s，也不是汇点t的任意点时，恒有：∑fij－∑fji＝0(1)j∈Vj∈V但i为源点s时有∑fsj＝w(2)j∈V从(1)、(2)对i∈S求得∑[fij-fji]＝wi∈S,j∈V证明∵V=S∪S∴[][][]wffffffSjSijiijSjSijiijVjSijiij=-+-=-,,,＝0＝w13§2割切-定理6.1证明－1证明[]wffSjSijiij=-,∴又∵0≤fij≤cij∴fij－fji≤fij≤cij因为割切是任意的，所以得证。[]=≤-=SjSiijSjSijiijcffw,,C(S,)S∴14§3Ford-Fulkerson最大流最小割切定理定理6.2：在一个给定的网络流图上，其最大流量等于其最小割切的容量，即：maxw＝minC(S,)S15§32F最大流最小切割定理－1如果网络的容许流不是最大的，则一定存在一条从s到t的增流路径。什么样的路径才是增流路径呢？16§32F最大流最小切割定理－2令s,i1,i2,…,ik,t是一条从s到t的路径Pst，其中：边的方向是从ij-1到ij的，称为向前边；边的方向是从ij到ij-1的，称为后退边；后退边向前边si1i2ijikt(4,2)(3,2)(3,1)(5,1)(6,2)17§32F最大流最小切割定理－3如果路径上全部都是向前边，且每条边eij都有fij＜cij，那么令δ=min(cij-fij)，这时令Pst上每条边的流都增加δ，结果仍是网络的容许流，但整个路径的流量比原来增加了δ。所以Pst是一条增流路径。δ=min(cij-fij)=1si1i2ijikt(4,2)(3,2)(3,1)(5,1)(6,2)(cij,fij)(4,3)(3,3)(3,2)(5,2)(6,3)18§32F最大流最小切割定理－4如果路径上有向前边也有后退边，则在向前边中，令δ1=min(cij-fij)，δ2=minfji，δ=min(δ1,δ2)，这时令Pst上每条向前边的流都增加δ，后退边减少δ，结果仍是网络的容许流，但整个路径的流量比原来增加了δ。δ=min(δ1,δ2)=2si1i2ijikt(4,1)(3,2)(3,0)(5,1)(6,2)(cij,fij)(4,3)(3,0)(3,2)(5,3)(6,4)19§32F最大流最小切割定理－5注：网络里只存在上述的两类增流路径。20§32F最大流最小切割定理－例求下图的最大流。例sabcdt112221121§32F最大流最小切割定理－例解1如果最初的fij＝0，即w＝0，如下图所示：解sabcdt(1,0)(1,0)(2,0)(2,0)(2,0)(1,0)(1,0)22§32F最大流最小切割定理－例解2则发现的第一条增流路径可以是：(s,c,b,t)解sabcdt(1,0)(1,0)(2,0)(2,0)(2,0)(1,0)(1,0)2)2)2)它全部由向前边组成，且δ＝2，所以可增流2。23§32F最大流最小切割定理－例解3第二条增流路径是：(s,a,b,c,d,t)解sabcdt(1,0)(1,0)(2,2)(2,2)(2,2)(1,0)(1,0)它由向前边和后退边组成。δ1=1，δ2=2，δ=min(δ1,δ2)=1，所以此路径可增流1。(1,1)(1,1)(2,1)(1,1)(1,1)24§32F最大流最小切割定理－例解4在图中再也找不到增流路径，所以这时的网络流最大流量w＝3。解sabcdt(1,1)(1,1)(2,2)(2,1)(2,2)(1,1)(1,1)25§42F最大流最小切割标号算法1962年，Ford和Fulkerson对于求最大网络流给出了一个有效算法，我们简称为2F算法。算法包括两个过程：（1）标号过程；（2）增流过程；26§42F最大流最小切割标号算法1标号的约定：源点s标号：标以(-,∞)；正向标号：如果e=(vi,vj)且fij＜cij，顶点vi得到标号(vi+,δij)，δij＝cij-fij；反向标号：如果e=(vj,vi)且fji＞0，顶点vi得到标号(vi-,δij)，δij＝fji；如果顶点关联的边为饱和边，则无需标号27§42F最大流最小切割标号算法2什么是饱和边？向前边：fij＝cij时后退边：fij＝0时称为饱和边；28§42F标号算法描述2F算法描述：（1）初始化f(e)=0，e∈E；//初始化（2）给源点s标号(-,∞)，其它顶点均未标号；（3）依次选一个未标号的顶点，根据其方向进行标号，若当前标号的顶点为t，转（4），否则转入（6）；（4）选择一条标号过的增流路径进行增流；（5）转（2）（6）这时得到的f就是最大容许流。29§42F标号算法例用2F标号算法求下图的最大流。例sabct9572438630§42F标号算法例解1（1）对所有e∈E，有f(e)=0；解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)31§42F标号算法例解2（2）给源点s标号(-,∞)，其它顶点均未标号；解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,∞)32§42F标号算法例解3（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,∞)(s+,2)(b+,4)(a+,7)(c+,5)33§42F标号算法例解4（4）对标号过的增流路径进行增流；增流路径为：(s,a,b,c,t)解sabct(9,0)(5,0)(7,0)(2,0)(4,0)(3,0)(8,0)(6,0)(-,∞)(s+,2)(b+,4)(a+,7)(c+,5)(2,2)(7,2)(4,2)(5,2)δ=min(cij-fij)=234§42F标号算法例解5（5）转（2）（2）给源点s标号(-,∞)，其它顶点均未标号；解sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,∞)35§42F标号算法例解6（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解sabct(9,0)(5,2)(7,2)(2,2)(4,2)(3,0)(8,0)(6,0)(-,∞)(s+,9)(a+,8)(b+,6)36§42F标号算法例解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)(a+,8)(b+,6)(8,6)(9,6)(6,6)δ=min(cij-fij)=637§42F标号算法例解8（5）转（2）（2）给源点s标号(-,∞)，其它顶点均未标号；解sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,∞)38§42F标号算法例解9（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解sabct(9,6)(5,2)(7,2)(2,2)(4,2)(3,0)(8,6)(6,6)(-,∞)(s+,3)(b-,2)(a+,2)39§42F标号算法例解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)(b-,2)(a+,2)δ1=min(cij-fij)=2δ2=fji=2δ=min(δ1,δ2)=2(9,8)(7,0)(8,8)40§42F标号算法例解11（5）转（2）（2）给源点s标号(-,∞)，其它顶点均未标号；解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,∞)41§42F标号算法例解12（3）选可进行正向或反向标号的顶点进行标号，若当前标号的顶点为t，转（4），如果没有这样的顶点可选时，转入（6）；解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,∞)(s+,1)(b+,2)(c+,3)42§42F标号算法例解13（4）对标号过的增流路径进行增流；增流路径为：(s,b,c,t)解sabct(9,8)(5,2)(7,0)(2,2)(4,2)(3,0)(8,8)(6,6)(-,∞)(s+,1)(b+,2)(c+,3)δ=min(cij-fij)=1(9,9)(4,3)(5