一、 定義與定理
流網絡：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 閱讀(3568)
評論(0) 編輯 收藏 引用 所屬分類:
圖論