一、 定義與定理
流網(wǎng)絡(luò)：G=(V, E)是一個(gè)有向圖，其中每條邊(u, v)∈E均有一個(gè)非負(fù)容量c(u, v) ≤0，否則c(u, v)為0.流網(wǎng)絡(luò)中有兩個(gè)特別的頂點(diǎn)：源點(diǎn)s和匯點(diǎn)t。對(duì)于每個(gè)頂點(diǎn)v∈V，都存在一條路徑s…v…t。
流：G上的一個(gè)實(shí)值函數(shù)(V×V→R)，滿足1)對(duì)于任意u, v∈V，f(u, v)≤c(u, v)；2)對(duì)于任意u, v∈V，f(u, v)=-f(u, v)；3)對(duì)于任意u∈V-{s, t}，∑f(u, i)=0。定義流|f|=∑f(s, i)。
殘留網(wǎng)絡(luò)：給定流網(wǎng)絡(luò)和一個(gè)流，其殘留網(wǎng)絡(luò)由可以容納更多網(wǎng)絡(luò)流的邊組成。定義殘留容量cf(u, v)=c(u, v)-f(u, v)。殘留網(wǎng)絡(luò)Gf=(V,Ef),其中Ef={(u, v)∈V×V:cf(u, v)>0}。
增廣路徑：增光路徑p為殘留網(wǎng)絡(luò)Gf中從s到t的一條簡(jiǎn)單路徑。
流網(wǎng)絡(luò)的割：流網(wǎng)絡(luò)的割(S, T)將V劃分為S和T=V-S兩部分，使得s∈S，t∈T。穿過(guò)割的凈流定義為f(S, T)，且有f(S, T)=|f|。割的容量為c(u, v)。一個(gè)網(wǎng)絡(luò)的最小割就是網(wǎng)絡(luò)中所有割中流量最小的割。
最大流最小割定理：以下三個(gè)條件等價(jià)：1)f是G的一個(gè)最大流；2)殘留網(wǎng)絡(luò)Gf不包含增廣路徑；3)對(duì)G的某個(gè)割(S, T)，有|f|=c(S, T)。
前置流：是一個(gè)函數(shù)f：V×V→R，它滿足1)對(duì)于任意u, v∈V，f(u, v)≤c(u, v)；2)對(duì)于任意u, v∈V，f(u, v)=-f(u, v)；3)對(duì)于任意u∈V-{s, t}，f[V, u]≥0。定義余流e[u]=f[V, u]，對(duì)于u∈V-{s, t}，當(dāng)e[u]>0時(shí)，稱頂點(diǎn)u溢出。
高度函數(shù)：函數(shù)h：V→N滿足h[s]=|V|，h[t]=0，且對(duì)每條殘留邊(u, v)∈Ef，有h[u]≤h[v]+1。
容許邊：如果cf(u, v)>0且h[u]=h[v]+1，則稱(u, v)是容許邊。否則，(u, v)是非容許邊。容許網(wǎng)絡(luò)為Gf,h=(V, Ef,h)，其中Ef,h為容許邊的集合。根據(jù)容許邊有關(guān)高度的定義，易知，容許網(wǎng)絡(luò)不存在回路。
二、 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過(guò)程的效率取決于如何確定增廣路徑。如果選擇不好，對(duì)于非有理的容量，算法有可能不能終止。如果容量是整數(shù)（如果容量不是整數(shù)，可以乘以特定的因子轉(zhuǎn)化為整數(shù)）。這時(shí)，第2~4行運(yùn)行時(shí)間為O(E),第5~9行，while循環(huán)至多執(zhí)行|f*|，這是因?yàn)樵诿看蔚螅髦抵辽僭黾?。故算法效率為O(E|f*|)。當(dāng)最大流f*較小時(shí)，這個(gè)算法的效率還是不錯(cuò)的。
2）Edmonds-Karp算法
描述：將基本的Ford-Fulkerson算法的第5行中用廣度優(yōu)先搜索來(lái)實(shí)現(xiàn)增廣路p的計(jì)算，即增廣路徑是殘留網(wǎng)絡(luò)中從s到t的最短路徑(其中每條邊為單位距離或權(quán))，則能夠改進(jìn)Ford-Fulkerson算法的界。
分析：隨著算法的運(yùn)行，對(duì)于所有頂點(diǎn)v∈V-{s, t}，殘留網(wǎng)絡(luò)Gf中的最短路徑長(zhǎng)度δf(s, v)隨著每個(gè)流的增加而單調(diào)遞增。直觀看來(lái)，每次增加流的操作都將使得當(dāng)前最短路中的一條邊(即關(guān)鍵邊，cf(a, b)=cf(p))從p中消失，從而使得新生成的Gf中的最短路徑的長(zhǎng)度增加。同時(shí)，任意邊(u, v)至多能成為|V|/2-1次成為關(guān)鍵邊。這是因?yàn)榈趇次成為關(guān)鍵邊時(shí)有δf(s, v)=δf(s, u)+1，而第i+1次時(shí)f[u, v]只可能與上次異號(hào)，則有δ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)每次成為關(guān)鍵邊都將使得δf(s, u)增加2，有由于δf(s, u)最大值為|V|-2，則任意邊(u, v)至多能成為|V|/2-1次成為關(guān)鍵邊。故該算法的時(shí)間復(fù)雜性為O(VE2)。
示例：POJ 1273 解題報(bào)告
三、 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
正確性：用循環(huán)不變式來(lái)說(shuō)明
1）初始化：INITILIZATION-FREFLOW初始化f為前置流
2）保持：算法中只使用了push與relabel操作，relabel操作只影響高度，不影響f；而push(u, v)操作，只會(huì)增加點(diǎn)v的流入量即f(V, v)，
所以如果操作以前是前置流，操作后還是前置流
3）終止：在終止時(shí)，V-{s, t}中的每個(gè)頂點(diǎn)的余流必為0（如果存在不為0的點(diǎn)，則必可以進(jìn)行push或relabel操作），且最終得到的是一個(gè)前置流，故最終得到的是一個(gè)流。又在最終的殘留網(wǎng)絡(luò)中，不存在s到t的路徑（否則，如存在一條路徑s,v1,...,t，則s可以向壓入流，使得v1溢出），根據(jù)最大流最小割定理，f是最大流。
分析：首先，證明對(duì)于任意溢出點(diǎn)u，均存在一條在Gf上的u到s的路，設(shè)U={v|在Gf存在一條s到v的路徑}，設(shè)U#=V-U，假設(shè)s不屬于U，對(duì)于頂點(diǎn)對(duì)(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，而對(duì)于v∈V-{s}，e[v]≥0，又e[u]>0，則U中必有s，矛盾！
relabel操作：對(duì)于源點(diǎn)與會(huì)點(diǎn)，不存在relabel操作，而對(duì)于其它頂點(diǎn)u，初始時(shí)，h[u]=0≤2|V|-1，當(dāng)u進(jìn)行relabel時(shí)，u溢出，則Gf中必存在一條u到s的路徑p=<u=v0,v1,...,vk=s>，由高度函數(shù)的定義(u, v)∈Ef，有h[u]≤h[v]+1，則h[u]=h[v0]≤h[vk]+k≤h[s]+|V|-1=2|V|-1，算法中總共的relabel操作次數(shù)為O(V2)。
飽和push操作：進(jìn)行操作后，(u, v)邊從Ef中消失，則稱該push操作為飽和push操作，進(jìn)行一次(u, v)的飽和push操作必有h[u]=h[v]+1，同時(shí)，要進(jìn)行下一次(u, v)的飽和push操作，必先經(jīng)過(guò)一次(v, u)的飽和push操作，則兩次飽和操作室h[u]增加2，又h[u]≤2|V|-1，則每個(gè)頂點(diǎn)至多進(jìn)行|V|次飽和push操作，則總共的飽和push操作次數(shù)為O(|V||E|)。
不飽和push操作：push操作中除去飽和push操作，剩下的就是不飽和push操作。定義一個(gè)函數(shù)g，值為所有e值大于0的頂點(diǎn)的高度和，故g≥0。考察三種操作對(duì)g值的影響：1）relabel操作不會(huì)改變溢出性且只會(huì)改變一個(gè)點(diǎn)，而一個(gè)點(diǎn)的變化至多為2|V|-1，則g至多增加2|V|-1；2）飽和push操作可能能增加一個(gè)溢出點(diǎn)，g至多增加2|V|-1；3）不飽和push(u, v)操作會(huì)使u變?yōu)椴灰绯觯趘從不溢出到溢出時(shí)，減小的最少，為1（因?yàn)閔[u]=h[v]+1)。則不飽和push操作的次數(shù)至多為O(|V|2|E|+|V|3)。
綜上，Push-Relabel算法是正確的且效率為O(V2E)。
示例：POJ 1459 解題報(bào)告
四、 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操作時(shí)才會(huì)改變f，故它是Push-Ralabel的一個(gè)實(shí)現(xiàn)，所以只要證明當(dāng)算法終止時(shí)只要再無(wú)Push與Relabel操作即可。用循環(huán)不變式證明：
1）初始化：運(yùn)行INITIALIZE-PREFLOW后，無(wú)容許邊，故任意頂點(diǎn)序列就是拓?fù)渑判虻捻旤c(diǎn)。
2）保持：容許網(wǎng)絡(luò)可通過(guò)Push和Relabel操作改變，對(duì)于Push操作，不會(huì)產(chǎn)生容許邊，故u的前面的頂點(diǎn)與u不會(huì)有余流；而對(duì)于Relabel(u)操作，不會(huì)產(chǎn)生進(jìn)入u的容許邊，只會(huì)產(chǎn)生離開u的容許邊，注意Relabel-To-Front算法的12行，將u移入L的前端，保證任意離開u的容許邊都滿足拓?fù)渑判颍瑫r(shí)，保證u的前面與u沒有余流。
3）終止：循環(huán)終止時(shí)，u恰好在L最后，于是，L中所有的頂點(diǎn)均無(wú)余流，也就再無(wú)Push與Relabel操作。
分析：該算法是Push-Relabel算法的一種實(shí)現(xiàn)，所以每個(gè)頂點(diǎn)Relabel操作的界為O(V)，則全部頂點(diǎn)的Relabel操作的界為O(V2)。如算法的11~13行表明兩次Relabel操作之間，最多進(jìn)行|L|次，即|V|次Discharge操作。每次Discharge操作至多只會(huì)有1不飽和Push操作，則不飽和操作的界為O(V3)，同時(shí)通過(guò)Push-Ralabel算法對(duì)飽和Push操作的分析，整個(gè)算法的界為O(V3+VE)=O(V3)。
示例：POJ 1149 解題報(bào)告
posted on 2009-06-26 19:49
Icyflame 閱讀(3570)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
圖論