-图论与算法-第八讲 最大流问题

《算法艺术与信息学竞赛》算法图论第八讲最大流问题声明•本系列教学幻灯片属于刘汝佳、黄亮著《算法艺术与信息学竞赛》配套幻灯片•本幻灯片可从本书blog上免费下载，即使您并未购买本书.•若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用•有任何意见，欢迎在blog上评论•Blog地址：内容介绍一、最大流问题二、Ford-Fulkerson方法三、Edmond-Karp算法四、预流推进算法五、应用举例一、最大流问题流网络定义•一个流网络(flownetwork)G=(V,E)是一个有向图,每个边(u,v)有一个非负容量(capacity)c(u,v)=0.对于不在E中的(u,v),规定c(u,v)=0•有两个特殊结点:源(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,Y)•引理:在以f为流函数的流网络中,以下三个等式成立–f(X,X)=0–F(X,Y)=-f(X,Y)–若X和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方法基本思想•从零流开始迭代,每次沿着增广路(augmentingpath)调整流量,直到不存在增广路,算法停止•算法梗概残量网络•有的弧已经满载了,不可能增加流量,在寻找可增广路时应该避免.•引入残量网络(residualnetwork),表示所有可以增加流量的弧•定义(u,v)的残量容量为:cf(u,v)=c(u,v)-f(u,v)•注意:流量为负时,残量容量比原始容量还大!可以这样理解:在取消反向流量以后还可以增加正向流量,因此流量增加量(而不是终值)可以大于原始容量残量网络举例•残量网络:大于0的cf所构成的网络•由于一条弧最多从两边增广,|Ef|=2|E|可增广路•残量网络中任意一条s-t路称为可增广路•路上的最小容量称为路的残量容量(residualcapacity),记为d•对于可增广路上的有向边(u,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)的净流量(netflow)为f(S,T),容量(capacity)为c(S,T)•下图的割,流量为19(注意有反向流),容量为26切割与流•最小切割(minimumcut)是使c(S,T)最小的切割•定理:对于任意一个切割,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)的弧不满载,残量网络中会有更多弧存在)–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路,最多增广|f*|次,因此总时间复杂度为O(E|f*|)•下面的例子:任意增广可能会增广很多次练习•证明:残量网络中,cf(u,v)+cf(v,u)=c(u,v)+c(v,u)•证明:理论上,最大流总能通过不超过O(E)次增广得到•通过求解最多|V|次最大流(O(V)个点,O(E)条边)计算无向图的边连通度三、Edmond-Karp算法基本思想•用BFS找残量网络的最短(边最少)s-t路.•引理:在残量网络Gf中,每次增广将使df[v]单调增加.•证明:反证法.设增广前后的流为f和f’.取df减小的第一个点v,设在Gf’中,s-v的最短路的倒数第二个点为u,则–(u,v)在Gf’中,且df’[u]=df’[v]-1–由于v之前的点df值并不减少,故df’[u]=df[u]–若(u,v)也在Gf中,df[v]=df[u]+1=df’[u]+1=df’[v]引理的证明•设增广前后的流为f和f’.取df减小的第一个点v,设在Gf’中,s-v的最短路的倒数第二个点为u,则(u,v)在Gf’中.若(u,v)也在Gf中,df[v]=df[u]+1=df’[u]+1=df’[v],与v的d值减小矛盾!•因此(u,v)不在Gf中.但(u,v)在Gf’中,故从f到f’的增广路一定是增加了f(v,u)•因此(v,u)是Gf中s到u的最短路的最后一条弧,有df[v]=df[u]-1=df’[u]-1=df’[v]-2,与v的d值减小矛盾!时间复杂度•定理:Edmonds-Karp算法增广O(VE)次•证明–定义关键弧为使cf(p)=cf(u,v)的弧–增广后关键弧(至少一个)从残量网络中消失–每条弧最多充当|V|/2-1次关键弧–因此最多增广O(VE)次•下面用引理证明划线命题关键弧•定理:每条弧最多充当|V|/2-1次关键弧•证明:–由于增广路是最短路,关键弧(u,v)满足:df[v]=df[u]+1–增广后,(u,v)在Gf中消失.重新出现的条件是:(u,v)减小,即(v,u)出现在增广路上.设此时的流为f’,则df’[u]=df’[v]+1.由引理知df’[v]=df[v],因此df’[u]=df’[v]+1=df[v]+1=df[u]+2–因此重新出现时d值增加2.最多从0增加到|V|-2,增加的次数不超过(|V|-2)/2=|V|/2-1四、预流推进算法增广路算法的坏情况•增广路算法:O(V2)•预流推进:线性预流•预流推进算法(push-relabelalgorithms)和增广路算法不一样,它并不检查整个残量网络,而是每次考虑一个结点,在残量网络中只检查它的邻居•预流推进算法在执行过程中并不始终保持流量平衡条件,而是生成预流(preflow),它和可行流类似,满足对称性和容量限制,但只满足宽松的流量平衡式f(V,u)=0(u为不是s的任意点),即:流进每个非s点的净流非负(蓄势待发,等着流出)•记e(u)=f(V,u),即点u的盈余基本想法•想象自上而下的水流•有向边是管道•点是管道连接处–每个点都可以用接一个蓄水池–每个点和它的水池以都在一个平台上,随着算法进行,平台逐渐升高•水往低处流,直到没有水了或者弧满载(push过程),如果有水却流不动,需要抬高水位,让它可以继续往低处流(relabel过程)算法过程•水源高度固定为|V|,汇的高度固定为0,其他点的高度初始为0,随着时间推移慢慢增加•首先尽量多的从水源把水”推”出来,即让s出发的所有弧满载.•水流入某个结点u后,进入该结点的蓄水池–如果u出发有到达更低点v的非饱和弧,把尽量多的水推入v(push过程)–如果u出发的所有非饱和弧都连接着与u水平甚至更高的点,把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)+1Push操作•基本操作PUSH(u,v)的条件–u有盈余–cf(u,v)0–h(u)=h(v)+1•使用e[u]和h[u]记录u的盈余和高度函数•伪代码如下:Push操作•推进的分类–饱和推进(水太多)–非饱和推进(水不够)•进行非饱和推进后,盈余e[u]变为0Relabel操作•基本操作RELABEL(u)的条件–u是盈余的–对于Gf的所有弧(u,v),h[u]=h[v]•即:虽然u有盈余,可是由于位置太低,无法进行PUSH操作,需要RELABEL•注意:s和t是不会有盈余的,因此不需要RELABEL•既然u有盈余,在残量网络中,u出发一定有弧初始化•h函数合法,因为所有满足h[u]h[v]+1的弧都满载一般预流推进算法•引理1:盈余点u要么可以push要么可以relabel–证明:对于Gf中的弧(u,v),有h(u)=h(v)+1–若存在残量弧(u,v)满足h(u)=h(v)+1,则可以推进–否则所有弧都满足h(u)h(v)+1,因此h(u)=h(v),满足relabel条件.•引理2:h函数不减.relabel操作后h[u]至少增加1•引理3:h函数始终保持基本性质h(u)=h(v)+1•引理4:残量网络Gf中,s和t不存在通路.证明:若存在通路,一定存在简单路,设长度为k,则k=|V|,在路上持续使用h函数的性质得h[s]=h(t)+k-1=k-1|V|,和h[s]=|V|矛盾•定理:若算法终止,得到的流是最大流正确性证明•如果算法终止,所有点盈余为0(否则需要继续push或者relabel)•因此算法终止以后得到可行流•由于h函数性质一直得到保持,s到t没有通路.由最小切割最大流定理,此可行流是最大流•定理:基本操作执行次数为O(V2E)算法分析•引理1:对于盈余点u,Gf中有u到s的简单路•引理2:在任何时刻h[u]=2|V|-1•引理3:每个点的relabel操作最多执行2|V|-1次,一共最多(2|V|-1)(|V|-2)2|V|2(由引理2直接可得)•引理4:饱和推进次数小于2|V||E|(由引理2)•*引理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)从允许网络中消失•引理2:若u有盈余但从u出发无允许弧,则执行RELABEL(u).此操作执行后u出发至少有一条允许弧,但没有允许弧进入u•邻居表N[u]:储存u出发所有可能的允许弧(即(u,v)属于E或(v,u)属于E)•当前弧current[u]:指向当前扫描到的N[u]点Discharge过程•discharge可描述为用current[u]遍历N[u]的过程•v为当前弧–V