网络流算法课件(清华)

1网络优化NetworkOptimization清华大学数学科学系谢金星办公室：理科楼2206#（电话：62787812）Email:[e-mail]~jxie清华大学课号：70420133第6章最大流问题(MaximumFlowProblem)第1讲2许多实际问题都可以转化为最大流问题ST最大流问题的例子公路交通网络：车流流量3定义6.1在有向图G=(V，A)上定义如下的权函数：（1）L：AR为弧上的权函数，弧(i,j)对应的权L(i,j)记为lij，称为弧(i,j)的容量下界（lowerbound）;（2）U：AR为弧上的权函数，弧(i,j)对应的权U(i,j)记为uij，称为弧(i,j)的容量上界，或直接称为容量（capacity）;（3）D：VR为顶点上的权函数，节点i对应的权D(i)记为di，称为顶点i的供需量（supply/demand）;此时网络可称为流网络(FlowNetwork,一般仍简称为网络),记为N=(V,A,L,U,D).6.1.1网络中的流di0:供应点(supplynode)或源(source)、起始点或发货点di0:需求点(demandnode)或汇(sink)、终止点或吸收点di＝0:转运点(transshipmentnode)或平衡点、中间点4定义6.2对于流网络N=（V，A，L，U，D），其上的一个流(flow)x是指从N的弧集A到实数集合R的一个函数x：AR,即对每条弧(i,j)赋予一个实数(称为弧(i,j)上的流).如果流x满足存在可行流的必要条件则称x为可行流(feasibleflow).至少存在一个可行流的流网络称为可行网络(feasiblenetwork).如果流x只满足容量约束(6.2),但不一定满足流量守恒条件(6.1),则称x为伪流(pseudoflow)，或容量可行流..0Viid)1.6(,,),(:),(:VidxxiAijjjiAjijij流量守恒/平衡条件)2.6(,),(,Ajiuxlijijij容量约束/可行条件网络中的流一般可以把L0的流网络转化为L=0的流网络进行研究(思考？)除非特别说明,以后我们总是假设L=0,网络简记为N=(V,A,U,D).)0.6(,,,Vjixxjiij5运输网络的特点是只有源或汇，没有中间转运点.显然，此问题有解的一个必要条件是TjSixTjbxSiaxijjAjiiijiAjijij,,0,,,,),(:),(:TjjSiiba网络中的流例-运输网络和运输计划有一批货物从货源地运往目的地，假设货源集合为S，目的地集合为T.货源i可提供的货物数量为ai个单位，目的地j对货物的需求量为bj个单位.以（S，T）为节点集作完全二部图，以ai，-bj为节点上的供需量。通过每条弧的运输量没有限制（非负即可）。一个运输计划就相当于该网络中的一个流。ST6网络中的流例6.1有向网络中，令所有弧上的容量下界为0，容量（上界）为1，并令节点s的供需量为1，节点t的供需量为-1。从s到t的一条有向路正好对应于网络中的一个可行流x（当xij=1时，表示弧(i，j)位于s-t路上，当xij=0时，表示弧(i，j)不在s-t路上）.思考：网络中的任意一个可行流是否一定对应于一条有向路？Pst7网络中的流定义6.3在流网络N=(V,A,U,D)中，对于流x,如果某条弧(i,j)上的流量等于其容量（），则称该弧为饱和弧（saturatedarc）；如果某条弧（i，j）上的流量为0()，则称该弧为空弧（voidarc）.ijijux0ijx如果所有弧均为空弧，即则称x为零流，否则为非零流.,),(,0AjixijS15t2341,11,11,11,01,12,23,03,28网络中的流定义6.4对于给定流网络N=(V,A,U,D)中的流x：AR，如果N中存在一条有向路P，使得，则称x为路流（Pathflow），v称为该路流的流值（流量）.v=0时，称该路流为零路流，否则称为非零路流.Pjiuxvijij),(,0PAjixij\),(,0如果N中存在一个有向圈W，使得，则称x为圈流（Cycleflow），v称为该圈流的流值（流量）.v=0时，称该圈流为零圈流，否则称为非零圈流.Wjiuxvijij),(,0WAjixij\),(,056P65556W9定理6.1在网络N=(V,A,U,D)中，任何一个可行流可以表示为若干个路流和若干个圈流之和，且这些路流和圈流满足下列性质：（1）非零路流对应的有向路从一个源点指向一个汇点；（2）至多有m+n个路流和圈流为非零流，且其中至多有m个圈流为非零流.流的分解定理（FlowDecompositionTheorem）证明(构造性)记可行流为x，设i0是网络中的一个源点，则存在弧(i0,i1)使得0.10iix在一个无源无汇的流网络中，一个可行流称为可行循环流。推论一个可行循环流一定可以表示为至多m个非零圈流之和.如果i1是一个汇点,则找到了从源点指向汇点的一条有向路.否则从i1出发重复上述过程,直到找到一个汇点或再次遇到前面经过的某个顶点时为止,即直到下列两种情况之一出现为止:10当找到一个路流时,重新定义使得某个节点的供需量从非零成为零,或者使得某条弧的流量从非零成为零.当找到一个圈流时,重新定义使得某条弧的流量从非零成为零.对新网络,重复上述过程,直到所有顶点变成为转运点(平衡点).然后,找到一个至少有一条出弧上的流量为正的顶点,继续重复上述过程,这时只有情形(b)会出现,即一定获得一个非零圈流.重复上述过程,直到重新定义的流x成为零流为止.(b)找到一个有向圈W.此时,定义(a)找到一条从一个源点i0指向一个汇点ik的有向路P.定义PjixddPvijiik),(|min,,min)(0.),(),(),(),(00PjiPvxxPvddPvddijijiiiikk.),(),(WjiWvxxijijWjixWvij),(|min)(上述过程找到路流和圈流的次数之和不会多于m+n次，且其中找到圈流的次数不会多于m次.11单源单汇的网络，可行流x的流量（或流值）为v=v（x）=ds=-dt如果我们并不给定ds和dt,则网络一般记为N=（s,t,V,A,U），容量可行且转运点流量守恒的流称为s-t可行流，有时为了方便也称为可行流.最大流问题(MaximumFlowProblem)就是在N=（s,t,V,A,U）中找到流值最大的s-t可行流(即最大流).6.1.2最大流问题的数学描述..maxtsv,,,0,,,,),(:),(:tsitivsivxxAijjjiAjijijAjiuxijij),(,0定理6.2(整流定理)最大流问题所对应的约束矩阵是全么模矩阵.若所有弧容量均为正整数,则问题存在最优整数解.12引理6.1任意一个s-t可行流流值不超过任意一个s-t割容量.6.1.3增广路定理定义6.5设[S，T]是网络N=(s,t,V,A,U)中给定的一个割，且sS，tT，则称割[S，T]为s-t割.s-t割[S，T]中的弧(i，j)(iS，jT)称为割的前向弧，弧(i,j)(jS，iT)称为割的反向弧.s-t割[S，T]的容量定义为前向弧的容量之和，记为一个网络中容量最小的s-t割称为最小割.TjSiAjiijuTSU,,),(),(),()()0()(TSUuxuxxxxxxxxxxxvijijSiTjijjiSiTjijSiTjjiijSiTjjiijSiSjjiijSiVjjiVjij13增广路引理6.2如果对于一个可行流存在增广路，则该可行流不是最大流.定义6.6设x是流网络N=(s,t,V,A,U)中给定的可行流，P是一条s-t路，则P中满足下列两个条件之一的弧（i，j）称为增广弧(augmentingarc)：（1）弧（i，j）是P的前向弧且为不饱和弧；或（2）弧（i，j）是P的反向弧且为非空弧.如果P中的弧都是增广弧，则称P为关于流x的增广路,简称增广路(augmentingpath).这一过程称为x关于P的增广(augmentation)0min,minmin),(),(ijPjiijijPjixxu.),(,,),(,,),(,'PjixPjixPjixxijijijij14证明必要性可以由前面的引理直接得到.下面证明充分性.定理6.3(增广路定理)一个可行流为最大流的充要条件是不存在增广路.增广路定理假设流网络N=(s,t,V,A,U)中不存在关于可行流x的增广路,记网络中从s出发沿增广弧可以到达的节点集合为S,令T=V\S,则sS，tT，即[S,T]为s-t割.并且,对于A中的任意弧(i,j),如果它是该s-t割的前向弧,则;如果它是该s-t割的后向弧,则=0.ijijuxijx),()(TSUuxxxvSiTjijSiTjjiij引理6.1证明中的中间结果因此,[S,T]为最小割,x为最大流.定理6.4(最大流最小割定理)最大流的流值等于最小割的容量.156.2增广路算法6.2.1Ford-Fulkerson标号算法（１９５６）基本思想：从任何一个可行流开始,沿增广路对流进行增广,直到网络中不存在增广路为止.问题的关键在于如何有效地找到增广路,并保证算法在有限次增广后一定终止.基本思想：标号过程来寻找网络中的增广路pred（j）：节点j在可能的增广路中的前一个节点;maxf（j）:沿该可能的增广路到该节点为止可以增广的最大流量.LIST:记录可能的增广路上的节点16STEP5.转STEP3.STEP3.如果LIST且maxf（t）=0,继续下一步;否则:(3a)如果t已经有标号(即maxf(t)0)，则找到了一条增广路，沿该增广路对流x进行增广(增广的流量为maxf（t）,增广路可以根据pred回溯方便地得到),转STEP1.(3b)如果t没有标号(即LIST=且maxf(t)=0),转STEP1.STEP4.从LIST中移走一个节点i；寻找从节点i出发的所有可能的增广弧：(4a)对非饱和前向弧（i，j），若节点j没有标号(即pred（j）=0)，则对j进行标号，即令maxf(j)=min{maxf(i),uij-xij}，pred(j)=i,并将j加入LIST中.(4b)对非空反向弧（j，i），若节点j没有标号(即pred(j)=0)，则对j进行标号，令maxf(j)=min{maxf(i),xji}，pred(j)=i,并将j加入LIST中.STEP1.若maxf（t）0,继续下一步;否则结束.STEP0.置初始可行流x（如零流）;对节点t标号,即令maxf（t）=任意正值（如1）.STEP2.取消所有节点jV的标号，即令maxf（j）=0,pred（j）=0；令LIST={s};对节点s标号，即令maxf（s）=充分大的正值.17最大流流值为4Ford-Fulkerson标号算法,例：（uij，xij）S15t2341,11,11,11,01,02,13,13,0S15t2341,11,11,11,01,02,23,13,1S15t2341,11,11,11,01,12,23,03,218最大流流值为2*106Ford-Fulkerson标号算法,例：（uij，xij）S15t4106,11,1106,0106,1106,05t24106,01,010