一、 定义与定理
流网络:G=(V, E)是一个有向图,其中每条边(u, v)∈E均有一个非负容量c(u, v) ≤0,否则c(u, v)为0.流网络中有两个特别的顶点:源点s和汇点t。对于每个顶点v∈V,都存在一条路径s…v…t。
流:G上的一个实值函数(V×V→R),满足1)对于任意u, v∈V,f(u, v)≤c(u, v);2)对于任意u, v∈V,f(u, v)=-f(u, v);3)对于任意u∈V-{s, t},∑f(u, i)=0。定义流|f|=∑f(s, i)。
残留网络:给定流网络和一个流,其残留网络由可以容纳更多网络流的边组成。定义残留容量cf(u, v)=c(u, v)-f(u, v)。残留网络Gf=(V,Ef),其中Ef={(u, v)∈V×V:cf(u, v)>0}。
增广路径:增光路径p为残留网络Gf中从s到t的一条简单路径。
流网络的割:流网络的割(S, T)将V划分为S和T=V-S两部分,使得s∈S,t∈T。穿过割的净流定义为f(S, T),且有f(S, T)=|f|。割的容量为c(u, v)。一个网络的最小割就是网络中所有割中流量最小的割。
最大流最小割定理:以下三个条件等价:1)f是G的一个最大流;2)残留网络Gf不包含增广路径;3)对G的某个割(S, T),有|f|=c(S, T)。
前置流:是一个函数f:V×V→R,它满足1)对于任意u, v∈V,f(u, v)≤c(u, v);2)对于任意u, v∈V,f(u, v)=-f(u, v);3)对于任意u∈V-{s, t},f[V, u]≥0。定义余流e[u]=f[V, u],对于u∈V-{s, t},当e[u]>0时,称顶点u溢出。
高度函数:函数h:V→N满足h[s]=|V|,h[t]=0,且对每条残留边(u, v)∈Ef,有h[u]≤h[v]+1。
容许边:如果cf(u, v)>0且h[u]=h[v]+1,则称(u, v)是容许边。否则,(u, v)是非容许边。容许网络为Gf,h=(V, Ef,h),其中Ef,h为容许边的集合。根据容许边有关高度的定义,易知,容许网络不存在回路。
二、 Ford-Fulkerson方法
1) 基本的Ford-Fulkerson算法
描述:
1 FORD-FULKERSON(G, s, t)
2 for each edge(u, v) in E(G)
3 do f[u, v] = 0
4 f[v, u] = 0
5 while exists a path p from s to t in Gf
6 do cf(p) = min{cf(u, v) : (u, v) in p}
7 for each edge(u, v) in p
8 do f[u, v] = f[u, v] + cf(p)
9 f[v, u] = - f[u, v]
分析:Ford-Fulkerson过程的效率取决于如何确定增广路径。如果选择不好,对于非有理的容量,算法有可能不能终止。如果容量是整数(如果容量不是整数,可以乘以特定的因子转化为整数)。这时,第2~4行运行时间为O(E),第5~9行,while循环至多执行|f*|,这是因为在每次迭代后,流值至少增加1。故算法效率为O(E|f*|)。当最大流f*较小时,这个算法的效率还是不错的。
2)Edmonds-Karp算法
描述:将基本的Ford-Fulkerson算法的第5行中用广度优先搜索来实现增广路p的计算,即增广路径是残留网络中从s到t的最短路径(其中每条边为单位距离或权),则能够改进Ford-Fulkerson算法的界。
分析:随着算法的运行,对于所有顶点v∈V-{s, t},残留网络Gf中的最短路径长度δf(s, v)随着每个流的增加而单调递增。直观看来,每次增加流的操作都将使得当前最短路中的一条边(即关键边,cf(a, b)=cf(p))从p中消失,从而使得新生成的Gf中的最短路径的长度增加。同时,任意边(u, v)至多能成为|V|/2-1次成为关键边。这是因为第i次成为关键边时有δf(s, v)=δf(s, u)+1,而第i+1次时f[u, v]只可能与上次异号,则有δf'(s, u)=δf'(s, v)+1,且有δf'(s, v)≥δf(s, v),则δf'(s, u)=δf'(s, v)+1)≥δf(s, v)+1=δf(s, u)+2。故(u, v)每次成为关键边都将使得δf(s, u)增加2,有由于δf(s, u)最大值为|V|-2,则任意边(u, v)至多能成为|V|/2-1次成为关键边。故该算法的时间复杂性为O(VE2)。
示例:POJ 1273 解题报告
三、 Push-Relabel算法
描述:
1 //Push操作
2 PUSH(u, v)
3 if cf(u, v)<=0 or h[u] != h[v]+1
4 then return
5 df(u, v) = min{e[u], cf(u, v)}
6 f[u, v] = f[u, v] + df(u, v)
7 f[v, u] = -f[u, v]
8 e[u] = e[u] - df(u, v)
9 e[v] = e[v] + df(u, v)
1 //Relabel操作
2 RELABEL(u)
3 if e[u]==0 or there is no v that (u, v) in Ef and h[u]>h[v]
4 then return
5 h[u] = 1 + min{h[v] : (u, v) in Ef}
1 //初始化前置流
2 INTIALIZE-PREFLOW(G, s)
3 for each vertex u in V[G]
4 do h[u] = 0
5 e[u] = 0
6 for each edge(u, v) in E[G]
7 do f[u, v] = 0
8 f[v, u] = 0
9 h[s] = |V[G]|
10 for each vertex u in Adj[s]
11 do f[s, u] = c[s, u]
12 f[u, s] = -c[s, u]
13 e[u] = c(s, u)
14 e[s] = e[s] - c(s, u)
1 //Push-Relabel算法
2 PUSH-RELABEL(G, s)
3 INTIALIZE-PREFLOW(G, s)
4 while there exists an applicable push or relabel operation
5 do select an applicable push or relabel operation and perform it
正确性:用循环不变式来说明
1)初始化:INITILIZATION-FREFLOW初始化f为前置流
2)保持:算法中只使用了push与relabel操作,relabel操作只影响高度,不影响f;而push(u, v)操作,只会增加点v的流入量即f(V, v),
所以如果操作以前是前置流,操作后还是前置流
3)终止:在终止时,V-{s, t}中的每个顶点的余流必为0(如果存在不为0的点,则必可以进行push或relabel操作),且最终得到的是一个前置流,故最终得到的是一个流。又在最终的残留网络中,不存在s到t的路径(否则,如存在一条路径s,v1,...,t,则s可以向压入流,使得v1溢出),根据最大流最小割定理,f是最大流。
分析:首先,证明对于任意溢出点u,均存在一条在Gf上的u到s的路,设U={v|在Gf存在一条s到v的路径},设U#=V-U,假设s不属于U,对于顶点对(v, w),v属于U,w属于U#,有f(v, w)≤0,否则,如果f(v, w)>0,则有cf(v, w)=c(v, w)-f(v, w)=c(v, w)+f(w, v)>0,这与w不属于U矛盾!e[u] =f(V, U)=F(U, U)+f(U#, U)=F(U#, U)≤0,而对于v∈V-{s},e[v]≥0,又e[u]>0,则U中必有s,矛盾!
relabel操作:对于源点与会点,不存在relabel操作,而对于其它顶点u,初始时,h[u]=0≤2|V|-1,当u进行relabel时,u溢出,则Gf中必存在一条u到s的路径p=<u=v0,v1,...,vk=s>,由高度函数的定义(u, v)∈Ef,有h[u]≤h[v]+1,则h[u]=h[v0]≤h[vk]+k≤h[s]+|V|-1=2|V|-1,算法中总共的relabel操作次数为O(V2)。
饱和push操作:进行操作后,(u, v)边从Ef中消失,则称该push操作为饱和push操作,进行一次(u, v)的饱和push操作必有h[u]=h[v]+1,同时,要进行下一次(u, v)的饱和push操作,必先经过一次(v, u)的饱和push操作,则两次饱和操作室h[u]增加2,又h[u]≤2|V|-1,则每个顶点至多进行|V|次饱和push操作,则总共的饱和push操作次数为O(|V||E|)。
不饱和push操作:push操作中除去饱和push操作,剩下的就是不饱和push操作。定义一个函数g,值为所有e值大于0的顶点的高度和,故g≥0。考察三种操作对g值的影响:1)relabel操作不会改变溢出性且只会改变一个点,而一个点的变化至多为2|V|-1,则g至多增加2|V|-1;2)饱和push操作可能能增加一个溢出点,g至多增加2|V|-1;3)不饱和push(u, v)操作会使u变为不溢出,而在v从不溢出到溢出时,减小的最少,为1(因为h[u]=h[v]+1)。则不饱和push操作的次数至多为O(|V|2|E|+|V|3)。
综上,Push-Relabel算法是正确的且效率为O(V2E)。
示例:POJ 1459 解题报告
四、 Relabel-To-Front算法
描述(Push、Relabel与Initalize-Flow操作参看Push-Relab):
1 //Discharge操作
2 DISCHARGE(u)
3 while e[u]>0
4 do v = current[u]
5 if v == NIL
6 then RELABEL(u)
7 current[u] = head[N[u]]
8 else if cf(u, v)>0 and h[u]=h[v]+1
9 then PUSH(u, v)
10 else
11 current[u] = next-neighbor[v]
1 //Relabel-To-Front算法
2 RELABEL-TO-FRONT(G, s, t)
3 INITIALIZE-PREFLOW(G, s)
4 L = V[G]-{s, t}, in any order
5 for each vertex u in V[G]-{s, t}
6 do current[u] = head[N[u]]
7 u = head[L]
8 while u != NIL
9 do old-height = h[u]
10 DISCHARGE(u)
11 if h[u] > old-height
12 then move u to the front of list L
13 u = next[u]
正确性:Relabel-To-Front算法只有在Push与relabel操作时才会改变f,故它是Push-Ralabel的一个实现,所以只要证明当算法终止时只要再无Push与Relabel操作即可。用循环不变式证明:
1)初始化:运行INITIALIZE-PREFLOW后,无容许边,故任意顶点序列就是拓扑排序的顶点。
2)保持:容许网络可通过Push和Relabel操作改变,对于Push操作,不会产生容许边,故u的前面的顶点与u不会有余流;而对于Relabel(u)操作,不会产生进入u的容许边,只会产生离开u的容许边,注意Relabel-To-Front算法的12行,将u移入L的前端,保证任意离开u的容许边都满足拓扑排序,同时,保证u的前面与u没有余流。
3)终止:循环终止时,u恰好在L最后,于是,L中所有的顶点均无余流,也就再无Push与Relabel操作。
分析:该算法是Push-Relabel算法的一种实现,所以每个顶点Relabel操作的界为O(V),则全部顶点的Relabel操作的界为O(V2)。如算法的11~13行表明两次Relabel操作之间,最多进行|L|次,即|V|次Discharge操作。每次Discharge操作至多只会有1不饱和Push操作,则不饱和操作的界为O(V3),同时通过Push-Ralabel算法对饱和Push操作的分析,整个算法的界为O(V3+VE)=O(V3)。
示例:POJ 1149 解题报告
posted on 2009-06-26 19:49
Icyflame 阅读(3539)
评论(0) 编辑 收藏 引用 所属分类:
图论