流網(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算法
      描述：

     分析：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(VE²)。
      示例：POJ 1273 解題報(bào)告

三、     Push-Relabel算法
      描述：

      正確性：用循環(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(V²)。
      飽和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?？疾烊N操作對(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)椴灰绯?，而在v從不溢出到溢出時(shí)，減小的最少，為1（因?yàn)閔[u]=h[v]+1)。則不飽和push操作的次數(shù)至多為O(|V|²|E|+|V|³)。
      綜上，Push-Relabel算法是正確的且效率為O(V²E)。
      示例：POJ 1459 解題報(bào)告