教案16最大流问题

1、算法设计与分析第16讲最大流问题信息科学技术学院1流G=(V,E) 是一个有向图，其中有两个特殊顶点：源流点(s)和汇点(t)。流中的每条边(u,v)E均有一非负容量c(u,v)0。如果(u,v)ÏE，则定义c(u,v)=0。2流（flow）顶点间的净流量流是定义在G上的函数f:V×VR，且满足下列性质：容量限制：对所有u,vV，有f(u,v) c(u,v)流守恒性：对所有uV-s,t，有vV f(u,v) = 0斜对称性：对所有u,vV，有f(u,v) = -f(v,u)3隐含求和记号定义流 f 的值为 |f |，其中|f | = vV f(s,v) = f(s,V)用集

2、合代替元素变量代入函数中，表示对该集合中所有元素求函数值后求和。例如，流守恒性可以表示为 所有uV-s,t，f(u,V) = 0又如f(X,Y) = xU yV f(x,y)4流的简单性质流性质引理：1.2.f(X, X) = 0f(X, Y) = -f(Y, X)3. f(XY, Z) = f(X, Z) + f(Y, Z)，如果XY=Æ定理： |f | = f(V, t)|f | = f(s,V)= f(V,V) - f(V-s,V)= f(V, V-s)= f(V, t)+ f(V, V-s-t)= f(V, t) 证明：5流入汇点的值|f | = f(s,V) = 4f(V,

3、 t) = 46的割（cut）流割(S,T)是流G=(V,E)的一个划分，其中sS, tT。如果 f 是G上的流，那么流经割的净流量为f(S,T)7最大流的性质引理：对任意流 f 和任意割(S,T)，有|f | = f(S,T)证明：f(S,T) = f(S,V) - f(S,S)= f(S,V)= f(s, V) += f(s, V)= |f |f(S-s,V)8割的容量割(S,T)上的容量定义为c(S,T)9最大流的上界定理：任意流的值的上界为任意割的容量证明：|f | = f(S,T)= uS vT f(u,v) uS vT c(u,v)= c(S,T) 10剩余定义：设 f 是G=(V

4、,E)上的流，剩余集Ef为剩余容量cf(u, v)严格为正的边cf(u, v) = c(u, v) f (u, v)Ef =(u,v)VV : cf(u, v) > 0图Gf=(V,Ef)，边残留的例子引理：|Ef| 2|E|11增广路径G=(V,E)和流 f，增广路径 p 为剩定义：已知一个流Gf中从s到t的一条简单路径，流的值可以沿着增广余路径p增加cf (p)=mincf (u,v):(u,v)p这个值称为p的剩余容量。最大流最小割定理等价命题1.某个割(S,T) ，|f | = c(S,T)；2.3.f 是最大流；f 不增广路径。证明：(1) Þ (2):因为|f |

5、c(S,T)，所以|f | = c(S,T)蕴含着(2) Þ (3):f 是最大流。若f增广路径，则f 的值可以增长，与f 是最大流。13最大流最小割定理(3) Þ (1): 假定S=v V: 在Gff 没有增广路径，定义一条从s到v的路径，令T=VS，显中然sS且tT，即(S,T)是割。考虑任意顶点uS和vT必有cf (u, v) = 0，因为cf (u, v) > 0就有vS，与v T又因为cf (u, v) = c(u, v) f (u, v)，于是 f (u, v) = c(u, v)对所有uS和vT求和，有f (S, T) = c(S, T)根据|f | =

6、 f (S, T)，得证。 14Ford-Fulkerson最大流算法FORD-FULKERSON-METHOD(G, s, t)1 initialize flow f to 02 while there exists an augmenting path p3do augment flow f along p4 return f15Ford-Fulkerson最大流算法FORD-FULKERSON(G, s, t)1 for each edge (u, v) EG23do fu, v 0fv, u 04 while there exists a path p from s to t in t

7、he residual network Gf5678do cf(p) min cf(u, v) : (u, v) is in pfor each edge (u, v) in pdo fu, v fu, v + cf(p)fv, u -fu, v16Edmonds-Karp最大流算法Edmonds and Karp 发现多数人实现Ford-Fulkerson算法时采用广度优先的方式找增广路径（Gf中的从s到t最短路径，都为1）这种实现总是运行较快。每条边的因为广度优先增广路径可以在O(E)时间内找到，他们的分（ O(VE2) ）求最大流，析第一次给出了在多项式时间其特点是限制了流增长的次数。1

8、7单调性引理设(v) = f (s, v)为Gf中从s到v的宽度优先最小距离，在Edmonds-Karp算法中(v)单调递增。证明：设 f 是G上的流，通过增长产生新的流 f 。设(v) = f (s, v)，对(v)进行归纳来证明(v) (v)，初始情形 (s) = (s) = 0。归纳情形，考虑Gf '中宽度优先路径s.u v ， 一定有(v) = (u) + 1（因为最短路径的子路径仍是最短路径），并且(u, v)Ef ，现在来看是否(u,v)Ef 的两种情形。18情形 1如果(u,v)Ef ，有(v) (u) + 1 (三角不等式) (u) + 1 (归纳假设)= (v)(广度

9、优先最短路径)(v) 的单调性成立。19情形 2如果(u, v) Ï Ef因为(u, v)Ef'，从 f 增长为 f 的增广路径(v, u)，并且p是Gf中的广度优先增广路径： p = s . v u . t所以，有(v) = (u) 1 (广度优先)p 一定包含<(u) 1 (归纳假设)(v) 2 (广度优先)(v)(v) 的单调性成立。 20流增长的次数定理： Edmonds-Karp算法中流增长的次数(Ford-Fulkerson广度优先增广路径)为O(VE)证明：设p是一条增广路径，假定 (u, v)p的剩余容量为cf (u, v) = cf (p) ，则称(u

10、, v) 是关键的。(u, v)不在增长后的剩余中出现。cf (p)=221流增长的次数定理： Edmonds-Karp算法中流增长的次数(Ford-Fulkerson广度优先增广路径)为O(VE)证明：设p是一条增广路径，假定 (u, v)p的剩余容量为cf (u, v) = cf (p) ，则称(u, v) 是关键的。(u, v)不在增长后的剩余中出现。22流增长的次数（续）当(u, v)第一次成为是广度优先路径）时，有(v) = (u) + 1，（因为p只有(v, u)在增广路径上时，(u, v)才可能再次成为设 为当(v, u)出现在增广路径上时的距离函数，则(u) = (v) + 1

11、 (广度优先路径) (v) + 1 (单调性)= (u) + 2 (广度优先路径)23流增长的次数（续）当(u, v)第一次成为是广度优先路径）时，有(v) = (u) + 1，（因为p只有(v, u)在增广路径上时，(u, v)才可能再次成为设 为当(v, u)出现在增广路径上时的距离函数，则(u) = (v) + 1 (广度优先路径) (v) + 1 (单调性)= (u) + 2 (广度优先路径)24流增长的次数（续）当(u, v)第一次成为是广度优先路径）时，有(v) = (u) + 1，（因为p只有(v, u)在增广路径上时，(u, v)才可能再次成为设 为当(v, u)出现在增广路径

12、上时的距离函数，则(u) = (v) + 1 (广度优先路径) (v) + 1 (单调性)= (u) + 2 (广度优先路径)25流增长的次数（续）当(u, v)第一次成为是广度优先路径）时，有(v) = (u) + 1，（因为p只有(v, u)在增广路径上时，(u, v)才可能再次成为设 为当(v, u)出现在增广路径上时的距离函数，则(u) = (v) + 1 (广度优先路径) (v) + 1 (单调性)= (u) + 2 (广度优先路径)26流增长的次数（续）当(u, v)第一次成为是广度优先路径）时，有(v) = (u) + 1，（因为p只有(v, u)在增广路径上时，(u, v)才可

13、能再次成为设 为当(v, u)出现在增广路径上时的距离函数，则(u) = (v) + 1 (广度优先路径) (v) + 1 (单调性)= (u) + 2 (广度优先路径)27流增长的次数（续）当(u, v)第一次成为是广度优先路径）时，有(v) = (u) + 1，（因为p只有(v, u)在增广路径上时，(u, v)才可能再次成为设 为当(v, u)出现在增广路径上时的距离函数，则(u) = (v) + 1 (广度优先路径) (v) + 1 (单调性)= (u) + 2 (广度优先路径)28Edmonds-Karp算法的运行时间距离值初始非负，从不下降，值至多为|V| 1，最后成为不可达顶点，

14、又因为每次交替出现(v) 都增加至少2，所以 (u, v)最多O(|V|)次成为。有O(E)条边，故流增长次数为 O(VE)。剩余推论：Edmonds-Karp最大流算法运行时间为O(VE2)O(E)，证明：每次增长流时，广度优先搜索运行时间为所有其他标记操作需要O(V)。 29增广路径与预流推进的对比基于增广路径的算法从零流出发每步基于增广路径构造一个更大的流流不能增大时为止基于预流推进的算法从源点出发或者把预流尽可能地向前推（push）或者重新标记中间结点的高度（relabel） 不能继续操作时为止30信息学院预流（preflow）预流（preflow）的性质：预流函数 f: V×

15、;VR斜对称性 f(u, v) = -f(v, u)容量限制 f(u, v) c(u, v)宽松的流守恒性超额流（excess flow）非负 e(u) = f(V, u) 0, for "u V - s溢出（overflow）结点e(u) > 031信息学院预流推进算法的直觉思想洪水流经河网和水库流向大海的过程最上游水库开闸，洪水迅速涌向下游水库 此时下泄流量只与河道容量有关（割的容量） 洪峰到达，下游水库开闸，洪水继续涌向下游 (push) 流出量只和与下游水库间的河网总容量有关 流出量小于流入量时，水库水位不断增高 (relabel) 可能会出现新的泄洪 或减弱入库流量（

16、洪水回涌）最后最上游水库出库流量与河网泄洪流量一致 泄洪过程的动态平衡32信息学院预流推进的基本操作基本操作推进流：push重标记：relabel高度函数流G上的预流f的高度函数hhs = |V|, ht = 0hu hv + 1, for " (u, v) Ef边的关系（引理26.13）高度函数与剩余hu > hv + 1 Þ (u, v) Ï Ef33信息学院推进流（PUSH）PUSH(u, v)1 Applies when:u is overflowing, cf(u, v) > 0, and hu = hv + 1.2 Action: Push

17、 df(u, v) =min(eu, cf(u, v) units of flow from u to v.3 df(u, v) min(eu, cf(u, v)4 fu, v fu, v + df(u, v)5 fv, u - fu, v6 eu eu - df(u, v)7 ev ev + df(u, v)信息学院34关于PUSHPUSH(u, v)从u到v推进流（满足条件时才能推进）饱和推进（saturating push）如果推进后边的流量饱和（剩余容量cf(u, v) = 0）不饱和推进（saturating push）如果推进后边的流量不饱和（剩余容量cf(u, v) > 0

18、）不饱和推进把溢出结点转变为非溢出结点（引理26.14）要点：何时、为何35信息学院重标号（RELABLE）RELABEL(u)1 Applies when: u is overflowing andfor all v V such that (u, v) Ef, we have hu hv.2 Action: Increase the height of u. 3 hu 1 + min hv : (u, v) Ef要点：何时、为何36信息学院通用的预流推进算法INITIALIZE-PREFLOW(G, s)123456789101112for each vertex u VGdo hu 0e

19、u 0for each edge (u, v) EG do fu, v 0fv, u 0hs |VG|for each vertex u Adjs do fs, u c(s, u)fu, s -c(s,u)eu c(s, u)es es - c(s, u)信息学院37GENERIC-PUSH-RELABELGENERIC-PUSH-RELABEL(G) 1 INITIALIZE-PREFLOW(G, s)2 while 如果能够应用PUSH或RELABEL操作3do 任意选取结点做PUSH或RELABEL操作（预流推进算法演示）任何溢出结点（引理26.15）或者可以应用PUSH或者可以应用RE

20、LABEL不能应用PUSH蕴含着可以应证明：用高度函数的用RELABEL的条件即可证明。38信息学院预流推进算法的正确性证明思路算法终止时，所得预流即最大流算法一定会终止39信息学院引理26.16 结点高度降低结点高度hu减小，并且重标号使结点高度hu至少增加1证明：因为hu只在RELABEL过程中改变，而当结点u可以应用RELABEL时，对于剩余图任意满足(u, v) Ef的结点v，huhv所以hu < 1 + min hv : (u, v) Ef，即hu必增大40信息学院引理26.17 始终满足高度函数性质在通用预流推进算法过程中，结点高度始终保持遵从高度函数的性质（循环不变式）。证

21、明：（归纳法）初始时遵从高度函数性质RELABEL(u)操作不改变高度函数性质 任意出边 (u, v) Ef，重标号后hu hv+1 任意入边 (w, u) Ef，重标号前hw hu+1，而重标号后hu至少增加1，故hw<hu+1PUSH(u, v)可能在Ef中增加边(v, u)或删除边(u, v) 增加时：hv = hu - 1 < hu+1 删除时：hv 与 hu 间无约束41信息学院引理26.18 Gf中无从s到t的路径G=<V, E>上预流f的剩余Gf中无从s到t的路径流证明：反证法，设p = <v0, v1, ., vk>是Gf中无从s到t的路径，

22、其中v0=s，vk=t不失一般性，p是一条简单路径，故k < |V|而对于(vi, vi+1)Ef, (i=1.k-1)有hvi hvi+1+1于是|V| = hs ht+k = k。42信息学院定理26.19：通用预流推进算法是正确的如果在流G=<V, E>上GENERIC-PUSH-RELABEL算法能结束，则得到的预流f就是G的最大流。证明：循环不变量（每一步得到的f总是一个预流）初始：初始化后，得到的f显然是预流保持：循环中只设计PUSH和RELABEL操作。 RELABEL操作只改变高度，不改变流； PUSH量限制。结束：不使任何结点的超额为负，同时保持f的斜对称性

23、和容溢出结点，即对于"uV-s, t，eu=0。而f始终是预流，故f是G上的流。又Gf中不从s到t的路径，故f是最大流。43信息学院预流推进算法的时间效率分析方法：只有三种操作：的执行次数上界RELABEL：重标记PUSH：推进流 饱和推进（saturating push） 不饱和推进（saturating push）结论：通用预流推进算法的运行时间上界为O(V2E)44信息学院引理26.20 溢出结点u在Gf中可达sGf中。一条从溢出结点u到源点s的简单路径在剩余证明：反设U=v|在Gf中u可达v，假设sÏU，设U=V-U。则"wU，"vU，f(w,

24、v) 0 否则，如果f(w, v) > 0，则f(v, w) < 0，于是cf(v, w) = c(v, w) - f(v, w) > 0，即(v, w) Ef，这样wU，于是f(U, U) 0，就有。 eU = f(V, U) = f(, U) + f(U, U) = f(, U) 0既有eu = 0，。45信息学院引理26.21 结点高度hu小于2|V|-1在通用预流推进算法过程中，对"u V有hu 2 |V| - 1。证明：根据定义，源点s和汇点t满足引理。对"u V-s, t，初始时hu = 0 2 |V|-1。在RELABEL(u)后，u溢出，根

25、据引理26.20，在Gf 单路径p = <v0, v1, . . . ,vk>，其中v0 = u，vk = s，k |V|-1。而对于(vi, vi+1)Ef, (i=1.k-1)有hvi hvi+1+1于是hu hs+k = 2|V|-1从u到s的简46信息学院次数的上界RELABEL：2|V|2每个结点最多重标记2|V|-1次，共|V|-2个结点。饱和PUSH：2|V|E| u和v间饱和PUSH的次数为2|V|-1当PUSH(u,v)时有hv = hu - 1，再次PUSH(u,v)须发生在PUSH(v,u)之后（hv = hu + 1），hv值增加2不饱和PUSH：4 |V|

26、2 (|V| + |E|)定义势函数 = v:e(v)>0hv 0。RELABEL增加势： 2|V|；饱和PUSH增加势： 2|V|不饱和PUSH减少势至少1。47信息学院通用预流推进算法的时间效率通用预流推进算法一定能结束只需执行O(V2E)次操作，算法结束算法运行时间上界如果RELABEL操作的开销为O(V)；PUSH操作的开销为O(1)。则运行时间上界为O(V2E)48信息学院重标号前置预流推进算法通用预流推进算法对溢出结点做流推进或重标号操作操作的顺序是任意的时间界为O(V2E)重标号前置预流推进算法对溢出结点做流推进或重标号操作通过对重标号的结点前置规范结点被处理的顺序时间界为

27、O(V3)借助于“边”的概念证明和分析49信息学院边与边（admissible edge）(u, v) 是边 Û cf(u, v) > 0 且 h(u) = h(v) + 1（admissible network）Gf,h= (V, Ef,h)的边集Ef,h由边组成是有向无环图（DAG）（引理26.27）通过环上结点高度值可证50信息学院上的操作引理26.28结点u溢出且(u, v)是边，则可以应用PUSH(u, v)，操作不增加边，但可能使(u, v)成为非边引理26.29结点u溢出且没有出发于u的边，则可以应用RELABEL(u)，操作后至少一条出发于u的边，但有进入u的边51信息学院DISCHARGE(u)DISCHARGE(u)12345678while eu > 0do v currentu if v = NILthen RE