课件第八讲最大流问题

1、算法艺术与信息学竞赛教学幻灯片算法图论第八讲最大流问题本系列教学幻灯片属于、著算法艺术与信息学竞赛配套幻灯片本幻灯片可从本书 blog 上，即使本书 .您并未若作为教学使用，欢迎和作者技术支持，也欢迎提供有不同以取得性的修本，方便人使用有任何意见，欢迎在 blog 上评论Blog 地址：内容一、最大流问题二、 Ford-Fulkerson三、 Edmond-Karp 算法四、预流推进算法五、应用举例一、最大流问题流定义(flow network) G=(V,E) 是一个有向一个流图,每个边 (u,v) 有一个非负容量 (capacity)c(u,v)>=0. v)=0对于不在 E 中的

2、(u, v),规定 c(u,有两个特殊结点 :源(source) s 和汇 (sink) t.假设对于任意其他点 v,通路 sàvàt流的定义流(flow) 是一个边的函数 f(u,v),满足 :容量限制 : f(u,v)<=c(u,v)对称性 : f(u,v)=-f(u,v)收支平衡 :对于不是 s 或t 的其他点 u,的流量定义为 ( 即从 s 流出的流量 ):把整个最大流问题 :寻找流函数 f,使得流最大记号X 和Y 为结点集 ,定义记号 f(X,引理 :成立在以 f 为流函数的流中,以下三个等式 f(X, X) = 0 F(X, Y) = -f(X, Y)若X

3、 和Y 不相交 , f(XUY, Z) = f(X,Z)+f(Y,Z)可以定义流的加法和标量积 ( 注意容量限制 )可以证明 :可行流集合是凸的 ,即如果 f1 和f2 都是流 ,对于所有 0<=<=1, f1+(1-)f2 也是 .其他问题弧的两个方向同时有流量 ?消 (cancelling) 只保留一边可以进行流取附加 s 和 t,则 s-t 流变为循环流流分解定理 :任意循环流可以分解为不超过E 个有向环的并二、 Ford-Fulkerson基本思想从零流开始迭代 ,每次沿着增广路(augmenting path) 调整流量 , 直到不增广路,算法停止算法梗概残量有的弧已经满

4、载了 ,不可能增加流量 ,在寻找可增广路时应该避免 .(residual network),引入残量表示所有可以增加流量的弧定义 (u,v) 的残量容量为 : cf(u,v)=c(u,v)-f(u,v)注意 :流量为负时 ,残量容量比原始容量还大 !可以这样理解 :在取消反向流量以后还可以增加正向流量 ,因此流量增加量( 而不是终值 ) 可以大于原始容量残量举例:大于 0 的cf 所残量的由于一条弧最多从两边增广 , |Ef|<=2|E|可增广路中任意一条 s-t 路称为可增广路残量路上的最小容量称为路的残量容量(residual capacity),记为 d对于可增广路上的有向边 (u

5、,v),原始的流量 f(u,v) 增加 d,由对称性， f(v,u) 减少 d,则得到的新流也是可行流 ( 验证流的三个性质 )定理 :不流量 f 是最大流当且仅当残量可增广路中最小切割最大流定理G=(V,E) 的 s-t 切割 (cut) 是把 V 划分成 S和 T=V-S,使用前面使得 s 在S 中, t 在T 中的隐式求和记号 ,可以简单的定义切割 (S,T) 的量(net flow) 为f(S,T),容量(capacity) 为 c(S,T)下图的割 ,26流量为 19( 注意有反向流 ),容量为切割与流最小切割 (minimum cut) 是使 c(S,T) 最小的切割定理 :对于任

6、意一个切割 , f(S,T)=|f|.证明: f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(s,V)+f(S-s,V)=f(s,V) ( 最的根据是流量平衡 )推论 : |f|此任意流量超过任意一个切割的容量 ,超过最小切割的容量因定理 :最大流等于最小切割的容量最小切割最大流定理定理 :以下三个条件等价 f 是最大流证明残量中无可增广路某个切割 (S,T), |f|=c(S,T) 1è2: 2è3:反证 .此时不,若可沿它增广得到更大流s-t 通路 .定义 S 为s 可达结点集 ,T 为可达 t 结点集 ,则|f|=c(S,T) ( 若(S,T) 的弧不满载

7、 , 3è1:)残量中会有弧根据刚才的推论可证基本的 Ford-Fulkerson 算法不断迭代 .增广路 .若(u,v)每次寻找某和(v,u) 都不在图中出现 ,则 c(u,v)=f(u,v)=0.注意 :c(u,v) 和 c(v,u) 都大于 0时间复杂度对于整数容量 ,可以用 DFS/BFS 求残量的任意一条 s-t 路,杂度为 O(E|f*|)最多增广 |f*| 次,因此总时间复下面的例子 :任意增广可能会增广很多次练习证明 :+c(v,u)证明 :中, cf(u,v)+cf(v,u)=c(u,v)残量理论上 ,最大流总能通过不超过O(E) 次增广得到通过求解最多 |V| 次

8、最大流 (O(V) 个点 ,O(E) 条边 ) 计算无的边连通度三、 Edmond-Karp 算法基本思想用 BFS 找残量的最短 ( 边最少 )s-t 路.引理 :Gf 中,在残量每次增广将使dfv 单调增加 .证明 :反证法 .设增广前后的流为 f 和f.取df 减小的第一个点 v, 设在 Gf 中, s-v 的最短路的倒数第二个点为 u, 则 (u,v) 在Gf中,且dfu=dfv-1 由于 v 之前的点 df值并不减少 ,故dfu>=dfu 若(u,v) 也在 Gf+1=dfv中, dfv<=dfu+1<=dfu引理的证明设增广前后的流为 f 和f.取df 减小的第一

9、个点 v,设在 Gf 中, s-v 的最短路的倒数第二个点为 u, 则 (u, v) 在Gf 中.若 (u,v) 也在Gf 中, dfv<=dfu+1<=dfu+1=dfv, 与v 的d 值减小!因此 (u,v) 不在 Gf 中.但 (u,v) 在Gf 中,故从 f 到 f 的增广路一定是增加了 f(v,u)因此 (v,u) 是Gf 中s 到u 的最短路的最后一条弧 , 有dfv=dfu-1<=dfu-1=dfv-2,与v 的d 值减小!时间复杂度定理 : Edmonds-Karp 算法增广 O(VE) 次证明 定义关键弧为使 cf(p)=cf(u,v) 的弧 增广后关键弧

10、( 至少一个 ) 从残量 每条弧最多充当 |V|/2-1 次关键弧 因此最多增广 O(VE) 次下面用引理证明划线命题中消失关键弧定理 :证明 :每条弧最多充当 |V|/2-1 次关键弧 由于增广路是最短路 , dfv=dfu+1关键弧 (u,v) 满足 : 增广后 , (u,v) 在Gf中消失 .重新出现的条件是: (u,v) 减小 , 即(v,u) 出现在增广路上 .设此时的流为 f, 则dfu=dfv+1. 由引理知dfv>=dfv, 因此 dfu=dfv+1>=dfv+1=dfu+2 因此重新出现时 d 值增加 2.最多从 0 增加到 |V|-2, 增加的次数不超过 (|V

11、|-2)/2 = |V|/2-1四、预流推进算法增广路算法的坏情况增广路算法 : O(V2)预流推进 :线性预流预流推进算法 (push-relabel algorithms) 和增广路算法不一样 ,它并查整个残量而是每次考虑一个结点 ,在残量中只检查它的邻居预流推进算法在执行过程中并不始终保持流量平衡条件 ,而是生成预流 (preflow),它和可行流类似,满足对称性和容量限制 ,但只满足宽松的流量平衡式 f(V,u)>=0 (u 为不是 s 的任意点 ),即:流进每个非 s 点的出)非负 ( 蓄势待发 ,等着流记 e(u)=f(V,u),即点 u 的盈余基本想法想象自上而下的水流有向

12、管道点是管道连接处 每个点都可以用接一个蓄水池 每个点和它的水池以都在一个平台上 ,法进行 , 平台逐渐升高随着算水往低处流 ,直到没有水了或者弧满载(push 过程 ),如果有水却流不动 ,需要抬高水位 , 让它可以继续往低处流 (relabel 过程)算法过程水源高度固定为 |V|,汇的高度固定为 0, 其他点的高度初始为 0, 随着时间推移慢慢增加首先尽量多的从水源把水”推”出来 ,发的所有弧满载 .即让s 出水流入某个结点 u 后,进入该结点的蓄水池如果 u 出发有到达更低点 v 的非饱和弧 ,水推入 v (push 过程)如果 u 出发的所有非饱和弧都连接着与 u 水平甚至更高的点

13、, 把u 抬高直到可以推 (relabel 过程)把尽量多的最终 ,所有能到 t 的到 t 了 ,把蓄水池里的水倒回 s( 把水位抬得比 s 还高)高度函数 h结点的 h 函数应满足 : h(s)=|V|, h(t)=0,对即中的弧 (u,v), h(u)<=h(v)+1,于残量起点不能太高若 h(u)>h(v)+1, (u,v) 不是残量因此不予考虑可以把 h 比做到t 的最短路长度 ,原理得 h(u)<=h(v)+1中的弧 ,由最优性Push 操作基本操作 PUSH(u,v) 的条件 u 有盈余 cf(u,v)>0 h(u)=h(v)+1使用 eu 和 hu伪代码如

14、下 :u 的盈余和高度函数Push 操作推进的分类 饱和推进 ( 水太多 ) 非饱和推进 ( 水不够)进行非饱和推进后 ,盈余 eu 变为 0Relabel 操作基本操作 RELABEL(u) 的条件 u 是盈余的对于 Gf 的所有弧 (u,v), hu<=hv即:虽然 u 有盈余 ,由于位置太低 ,无法进行PUSH 操作,注意 : s 和t 是RELABEL需要 RELABEL有盈余的 , 因此不需要既然盈残量网发弧初始化h 函数合法 ,满载因为所有满足 hu>hv+1 的弧都一般预流推进算法盈余点 u 要么可以 push 要么可以 relabel引理 1:证明 :若对于 Gf

15、中的弧 (u, v),有h(u)<=h(v)+1残量弧 (u,v) 满足 h(u)=h(v)+1,则可以推进否则所有弧都满足 h(u)<h(v)+1,足 relabel 条件.因此 h(u)<=h(v),满引理 2: h 函数不减 . relabel 操作后 hu 至少增加1引理 3: h 函数始终保持基本性质 h(u)<=h(v)+1引理 4:Gf 中, s 和t 不通路 .残量证明:通路 ,简单路 ,设长度为 k,若一定则k<=|V|,在路上持续使用 h 函数的性质得hs<=h(t)+k-1=k-1<|V|, 和 hs=|V|定理 :若算法终止 ,

16、得到的流是最大流正确性证明如果算法终止 ,所有点盈余为 0( 否则需要继续push 或者 relabel)因此算法终止以后得到可行流由于 h 函数性质一直得到保持 , s 到t 没有通路 .由最小切割最大流定理 ,此可行流是最大流定理 :基本操作执行次数为 O(V2E)算法分析引理 1:单路引理 2:对于盈余点 u, Gf 中有 u 到s 的简在任何时刻 hu<=2|V|-1引理 3:每个点的 relabel 操作最多执行 2|V|-1 次, 一共最多 (2|V|-1)(|V|-2)<2|V|2 ( 由引理 2 直接可得 )引理 4:2)饱和推进次数小于 2|V|E| ( 由引理*

17、 引理 5:非饱和推进次数小于 4|V|2(|V|+|E|) ( 考虑所有盈余点的 h 值之和)定理 :基本操作执行次数为 O(V2E)改进维护结点列表 ,从头开始扫描 ,每次对一个盈余结点进行 discharge( 即连续进行push 和 relabel,指导它没有盈余 )relabel 时放到列表顶端 ,并重新扫描弧: cf(u,v)>0 且 h(u)=h(v)+1.网络:引理 :.弧的是无环的 .如果有 ,对环上所有点的 h 等式叠加 ,结点 )得到环长 =1( 单分析引理 1:若u 有盈余且从 u 出发有弧(u, v)则执行PUSH(u,v).但可能会让 (u,v) 从弧,此操作

18、创造新的中消失引理 2:若u 有盈余但从 u 出发无弧,则执行RELABEL(u).此操作执行后 u 出发至少有一弧,弧进入 u条但没有邻居表 Nu:储存u 出发所有可能的弧( 即(u,v) 属于 E 或(v,u) 属于 E)当前弧 currentu:指向当前扫描到的 Nu 点Discharge 过程discharge 可描述为用 currentu 遍历 Nu 的过程v 为当前弧 V 为空,则需要 RELABEL(u) V 非空且 (u,v) 是 V 非空且 (u v) 不是弧,弧则 PUSH(u,v)无操作算法步骤引理 : DISCHARGE 过程中的 PUSH 和RELABEL 将执行真正

19、的操作 ( 而不是返回”无法完成” )维护不包含 s 和t 的结点链表 L,一开始任意排列,假设事先 Nu 和 nextu 已经计算完毕 ,每次当relab扫描l 后把放到最前面并从第二个开始算法运行示例正确性引理 : L 是的一个拓扑排序 ,且在循环第 6 行中的 u 前面没有盈余点 .数学归纳法 .证明 :定理 :算法一定终止 ,且结果为最大流 .由引理和一般预流推进法的正确性直接得到时间复杂度定理 : relabel-to-front 算法时间复杂度为 O(V3)证明当前弧移动 : O(VE) relabel 操作最多 O(V2) 次( 前面已证 ), O(VE)时间复杂度每两次 relabel 操作间( 称为一个阶段