一、 定义与定理
流网络：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) 编辑 收藏 引用 所属分类:
图论