最大流最小割定理

現實生活中，人們經常見到一些網絡，如鐵路網、公路網、通信網、運輸網等等。這些網絡有一個共同的特點，就是在網絡中都有物資、人或信息等某種量從一個地方流向另一個地方，如何安排這些量的流動以便取得最大效益是一個很有意義的實際問題。50年代福特（Ford）、富克遜（Fulkerson）建立的“網絡流理論”，是網絡應用的重要組成部分 ^[1]  。

給定指定的一個有向圖，其中有兩個特殊的點源S(Sources)和匯T(Sinks)，每條邊有指定的容量(Capacity)，求滿足條件的從S到T的最大流(MaxFlow)。

割是網絡中定點的一個劃分，它把網絡中的所有頂點劃分成兩個頂點集合S和T，其中源點s∈S,匯點t∈T。記為CUT(S,T)，滿足條件的從S到T的最小割（Min cut）。

定理一：

如果f是網絡中的一個流，CUT(S,T)是任意一個割，那麼f的值等於正向割邊的流量與負向割邊的流量之差。

證明：

設X和Y是網絡中的兩個頂點集合，用f（X,Y）表示從X中的一個頂點指向Y的一個頂點的所有弧（弧尾在X中，弧頭在Y中：

）的流量和。只需證明：f=f(S,T)-f(T,S) 即可。

下列結論成立：

如果X∩Y=

，那麼：f(X,(Y1∪Y2))=f(X,Y1)+f(X,Y2) ，f((X1∪X2),Y)=f(X1,Y)+f(X2,Y) 成立。

根據網絡流的特點：

如果V既不是源點也不是匯點，那麼： f({V},S∪T)-f(S∪T,{V})=0；任何一個點，流入的與流出的量相等。

如果V是源，那麼：f({V},S∪T)-f(S∪T,{V})=f。

對於S中的所有點V都有上述關係式，相加得到：f(S,S∪T)-f(S∪T,S)=f 。

又因為： f(S,S∪T)-f (S∪T,S)= (f(S,S)+f (S,T))-(f(S,S) +f (T,S))= f(S,T)- f(T,S)，

所以：f= f(S,T)- f(T,S) 定理得證 ^[2]  。

推論一：

如果f是網絡中的一個流，CUT(S,T)是一個割，那麼f的值不超過割CUT(S,T)的容量。

推論二：

網絡中的最大流不超過任何割的容量。

定理二：

在網絡中，如果f是一個流，CUT (S,T)是一個割，且f的值等於割CUT(S,T)的容量，那麼f是一個最大流， CUT(S,T)是一個最小割。

證明：

令割CUT（S,T）的容量為C，所以流f的流量也為C。假設另外的任意流f1，流量為c1，根據流量不超過割的容量，則c1<=c,所以f是最大流。 假設另外的任意割CUT（S1,T1），容量為c1，根據流量不超過割的容量，所以有c1>=c,故，CUT（S,T）是最小割 ^[2]  。

在任何的網絡中，最大流的值等於最小割的容量 ^[1]  。

結論一：

最大流時，最小割cut(S,T)中，正向割邊的流量=容量，逆向割邊的流量為0。

結論二：

在最小割cut(S,T)中：

問題描述：

某軟件公司有n個可選的程序項目，其中第i個項目需要耗費資金

元，開發成功後可以獲得的收益為

元。

程序項目之間不是獨立的：開發第i個項目的前提條件是必須先開發出一些其他的項目，這些項目成為第i個項目的“前驅項目”。已經給出所有項目的

和

以及前驅項目，請幫助該公司從這n個程序項目中選擇若干個進行開發，使獲得的總收益最大 ^[3]  。

分析：令

，淨收益。A={i|

>=0}:可以獲得利潤的項目集合。 B={i|

<0}：虧損的項目集合。

構造網絡圖： G=（V，E，C）。

1、兩類頂點：N+2個點：源點s個匯點t，第i個項目點vi。

2、三種弧：如果i∈A，存在弧<i,t>,容量為

。如果i∈B，存在弧<s,i>,容量法|

|。如果i個前驅項目為j，存在弧<j,i>，容量為+∞。

構造割cut（S，T），如果i∈T，則i的前驅j∈T。割對應一種實驗方案。最大收益為

。