最大流是圖應用，將有向圖理解為一個流網絡，可模型化流經管道的液體、通過裝配線的部件、電網中的電流、通訊網絡傳送的信息等，源點以固定能量產生，而匯點則消耗同等能量，保持守恒。最大流問題追求的就是在流網絡中，物質從源點傳到匯點的最大能量是多少？對于流網絡，算法導論中給出了形式化定義。

流網絡G=(V,E)是一個有向圖，其中每條邊(u,v)∈E均有一個非負能量c(u,v)≥0。如果(u,v)?E，則假定c(u,v)=0。流網絡中有兩個特點的頂點，源點s和匯點t，假定每個頂點均處于從源點到匯點的某條路徑上，就是說，對每個頂點v∈V，存在一條路徑s->v->t，因此圖G是連通圖，且|E|≥|V|-1。

設G=(V,E)是一個流網絡，其能量函數為c。設s為網絡的源點，t為匯點。G的流是一個實值函數f:VXV->R，且滿足下列三個性質：

容量限制：對所有u,v∈V，要求f(u,v)≤c(u,v)

反對稱性：對所有u,v∈V，要求f(u,v)=-f(v,u)

容量限制性質說明從一個頂點到另一個頂點的網絡流不能超過設定的容量；反對稱性說明從頂點u到頂點v的流是其反向流求負所得。流手恒性說明從非源頂點或非匯點的頂點出發的總網絡流為0。

最大流問題，就是給出一個具有源點s和匯點t的流網絡G，希望找出從s到t的最大值流。

頂點總的凈流量：離開頂點的總的正流量，減去進入頂點的總的正流量。流守恒性的另一個說法，進入某個非源點非匯點的頂點的正網絡流，必須等于離開該頂點的正網絡流，即流進等于流出。注意是正網絡流。

存在多個源點和匯點的最大流問題中，將建立超級源點和超級匯點。

流函數f以流網絡中的兩個頂點作為自變量，并隱含求和記號的數學定義如下：

設G=(V,E)是一個流網絡，f是G中的一個流：

對所有X?V，f(X,X)=0

對所有X,Y?V，f(X,Y)=-f(Y,X)

對所有X,Y,Z?V，其中X∩Y=?，有f(XUY,Z)=f(X,Z)+f(Y,Z)且f(Z,XUY)=f(Z,X)+f(Z,Y)

應用隱含求和記法，可以證明一個流的值為進入匯點的全部網絡流：

|f|=f(V,t)，根據流守恒性，對所有頂點（非源點非匯點），進入頂點的總的正流量等于離開頂點的總的正流量。根據上面的數學定義，證明：

|f|=f(s,V)

? =f(V,V)-f(V-s,V)

? =-f(V-s,V)

? =f(V,V-s)

? =f(V,t)+f(V,V-s-t)

? =f(V,t)

1）Ford-Fulkerson方法

Ford-Fulkerson方法用流網絡的割求解最大流的值，依賴三個主要思想：殘留網絡、增廣路徑、割。

?? 殘留網絡形式化定義

假定一個流網絡G=(V,E)，源點為s，匯點為t；設f是G中的一個流，并考察一對頂點u,v∈V，在不超過容量c(u,v)的條件下，從u到v之間可以壓入的額外網絡流量，就是(u,v)的殘留容量，定義為：c_f(u,v)=c(u,v)-f(u,v)。

如果c(u,v)=16且f(u,v)=11，那么在不超過16的情況下，可以在增加c_f(u,v)=5的流來增加f(u,v)。

給定一個流網絡G=(V,E)和流f，由f壓得的G的殘留網絡G_f=(V,E_f)，其中：

E_f={(u,v)∈VXV: c_f(u,v)>0}

在殘留網絡中，每條殘留邊都能夠容納一個嚴格為正的網絡流。E_f中的邊可以是E中的也可以是反向邊。在f(u,v)<0情況下，即反向變邊，E_f中的邊不在E中。

設G=(V,E)是源點為s、匯點為t的一個流網絡，且f為G中的一個流。設G_f是由f導出的G的殘留網絡，且f’為G_f中的一個流。那么f+f’之和也是G中的一個流，|f+f’|=|f|+|f’|。

?? 增廣路徑的形式化定義

已知一個流網絡G=(V,E)和流f，增廣路徑p為殘留網絡G_f中從s到t的一條簡單路徑。

沿一條增廣路徑p的每條邊傳輸的網絡流的最大量為p的殘留容量，定義為：

c_f(p)=min{c_f(u,v):(u,v)在p上}

設G=(V,E)是一個流網絡，f是G的一個流，并設p是殘留網絡G_f中的一條增廣路徑，定義函數：

f_p:VXV->R

則f_p是G_f上的一個流，其值為|f_p|= c_f(p)>0。

設G=(V,E)是一個流網絡，f是G的一個流，p是殘留網絡G_f中的一條增廣路徑。f_p定義如上， f’=f+f_p也是G的一個流，值|f’|=|f|+|f_p|>|f|。

通俗地理解殘留網絡和增廣路徑：在流網絡的一個流f上還可以容納的多余的流量就是殘留網絡，而在殘留網絡中尋找最大流就是增廣路徑，原來流f加上殘留網絡中的增廣路徑流就是不斷增加了最大流的值，如此迭代，尋找最大流的值。

?? 流網絡的割形式化定義

Ford-Fulkerson方法沿著增廣路徑反復增加流，直至找到最大流為止。最大流最小割原理是：一個流使最大流，當且僅當它的殘留網絡不包含增廣路徑。

流網絡G=(V,E)的割(S,T)是將頂點集合V劃分為S和T=V-S兩部分，使得s∈S，t∈T。如果f是一個流，則穿過(S,T)的凈流定義為f(S,T)，割(S,T)的容量為c(S,T)。一個網絡的最小割也是網絡中所有割中具有最小容量的割。

設f是源點s、匯點t的流網絡G中的一個流，并且(S,T)是G的一個割，則通過割(S,T)的凈流f(S,T)=|f|，即一個流的值為進入匯點的總網絡流量。

網絡的最大流必定不超過此網絡最小割的容量，最大流的值實際上就是某一個最小割的容量。

這個很好理解了，就是關鍵割了，最大值取決于關鍵路徑上的容量。

有了上面三個形式化定義，現在可以正式說明最大流最小割定理。

如果f是具有源點s和匯點t的流網絡G=(V,E)中的一個流，則下列條件是等價的：

第一：f是G的一個最大流；

第二：殘留網絡G_f不包含增廣路徑；（迭代再也找不到增廣路徑）

第三：對G的某個割(S,T)，有|f|=c(S,T)；（最大流是最小割的容量）

對Ford-Fulkerson方法的算法分析以及通過最短路徑距離定義優化的Edmonds-Karp算法不多述。理解最大流最小割原理最重要是理解流的定義。

Ford-Fulkerson方法的基礎算法中關鍵是增廣路徑的尋找，這也是決定算法性能的關鍵點。

2）最大二分匹配

流網絡的流滿足容量限制、反對稱性、流守恒性三大性質，基于殘留網絡、流網絡割以及增廣路徑的定義，形成最大流的最小割容量值定理。

最大二分匹配正式在這樣基礎上，用以解決二分圖匹配問題?？梢哉f是將二分匹配問題轉化為最大流問題，也可以說是最大流問題適合用于解決二分匹配問題，anyway，先看看二分匹配問題的定義。

給定一個無向圖G=(V,E)，一個匹配是一個邊的子集M?E，且滿足對所有頂點v∈V，M中至多有一條邊和v關聯。如果M中某條邊和v關聯，則說頂點v∈V被匹配，否則是無匹配。最大匹配就是最大勢的匹配。假定頂點集合可被劃分為V=LUR，其中L和R是不相交的，且E中的所有邊一個端點在R中、另一個端點在l中，并假設V中的每個頂點至少有一條關聯的邊?；谶@樣的二分圖定義尋找最大匹配問題有很多實際應用。如集群機器執行分布式任務，機器是集合L，任務是集合R，E中的邊(u,v)假設為u∈L的機器執行一項任務v∈R，最大匹配可以將任務盡可能多地分配給機器執行。

應用Ford-Fulkerson方法可以在關于|V|和|E|的多項式時間內，找出無向二分圖G=(V,E)的最大匹配。針對二分圖建立一個流網絡，流對應于匹配，尋找最大匹配就是尋找最大流。定義下二分圖G的相應流網絡G¹=(V¹,E¹)：

設源點s和匯點t是不屬于V的新頂點，V¹=VU{s,t}，如果G的頂點劃分為V=LUR，G¹的有向邊為E的邊，從L指向R，再加上|V|條新邊：

E¹={(s,u):u∈L}U{(u,v):u∈L,v∈R，and (u,v)∈E}U{(v,t):v∈R}

V中的每個頂點至少有一條關聯邊，|E|≥|V|/2。

設G=(V,E)是一個二分圖，其頂點劃分為V=LUR，設G¹=(V¹,E¹)是G對應的流網絡。如果M是G的匹配，則G¹中存在一個整數值的流f，且|f|=|M|，相反，如果f是G¹中的整數值流，則G中存在一匹配M滿足|M|=|f|。二分圖G的一個最大匹配M的勢等于其相應的流網絡G¹中的某一最大流的值。

算法導論還就最大流給出了壓入與重標記算法以及優化的重標記與前移算法，值得去深入理解。在理解最大流及其應用上，還是有點脫離實際，所以暫不深入掌握這兩個算法。

總結

以上是生活随笔為你收集整理的算法导论之最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。