最大流最小割定理

最大流最小割定理是最最佳化理論的定理。根據該定理，在一個網路流中，從源點到匯點的最大的流量，等於它的最小割中每一條邊的容量之和。“割”指的是一種邊的集合，如果移除這個集合的全部邊，就會斷開源點和匯點的連線。最大流最小割定理是線性規劃中的對偶問題的一種特殊情況，並且可以用來推導門格爾定理和König–Egerváry定理。定義.最大流和最小割定理是圖論的一部分，因此為了準確定義，我們需要先定義圖、流、割，然後再定義這個定理。圖.設 formula_1 為一個有向圖，其中有一個起源點 formula_2 和一個超匯點 formula_3，代表 formula_2 是所有流的源頭，formula_3 是所有流的終點。這個圖的每一條邊都有一個容量 "c" : "E" → R+，記做 formula_6 或者 formula_7，代表著能透過邊 formula_8 的最大流量。最大流.定義： 流量代表一種對映 formula_9，記做formula_10 或者 formula_11，代表透過邊 formula_8 的流量。每一條邊所透過的流有以下兩個限定條件：規定在一個圖中，流的值是formula_15也就是說，一個圖的流是自其源點流出的流量之和，也是向其匯點流入的流量之和。或者說，由源點向匯點移動多少內容，這個圖的流就是多少。最大流問題：計算formula_16的最大值，即從formula_2到formula_3的最大流量。最小割.定義： s-t割 formula_19 將圖 formula_20 完全劃分為兩部分，使得 formula_21 也就是一側有源，一側有匯。formula_22 的割集 formula_23 是 formula_24 也就是說，一條邊當且僅當騎在這個劃分方法上，一個節點位於劃分出來的源側，另一個位於匯側，那麼它包含在 formula_23 裡。因此如果 formula_22 的割集是空集，或者我們把一個割集裡的邊全都從圖中拿走，則 formula_27。通俗地說，割集就是一個圖的斷面，而割則是劃分斷面的方法。規定在一個圖中，s-t割的容量是formula_28 其中當 formula_29 時，formula_30 為 formula_31, 否則為 formula_32。通俗地說，割的容量就是斷面中所有邊的總容量。最小 s-t 割問題： 計算 formula_33 的最小值。即找到一種割法，使割的容量最小。也就是說，找到透過能力最弱的斷面。主定理.可以證明一切流都不能超過任何s-t割，所以經過圖的最大流就是圖的最小割。我們直觀上就可以知道，透過能力最弱的斷面就是整個網路的最大流量。這個理論把最大流問題和最小割問題聯絡了起來。線性規劃公式.最大流最小割問題可以被看做為一對線性規劃對偶問題。最大流的線性規劃公式是容易理解的，對於最小割的線性規劃公式的理解如下：formula_34formula_35最小化目標是使在割中的邊最小。下列限制保證了這些變數可以確保一個合法的割。需要注意的是，這是一個最小化問題，我們不需要確保一條邊不在割裡，我們只要保證每條應當在割裡的邊被計算了。注意到在給定的 s-t 割 formula_43 中，如果 formula_44 那麼 formula_45 並且 0 反之。 所以 formula_46 應該等於 1 並且 formula_47 應該等於0。由線性規劃中的強對偶定理推得最大流最小割問題中的等式，也就是說如果原問題有一個最優解 "x"*，則對應問題也有一個最優解 "y"* ，並且兩個解相等。舉例.上圖是一個網路，上有流量為 7 的流。令 S 集合和 T 集合分別包含所有白色和灰色的點， 從而形成了一個割集包含圖中虛線的 s-t 割，並且其容量為 7，與流量相同。故由大流最小割定理知，前述的流與 s-t 割皆達到流量及容量的極值。應用.廣義最大流最小割定理.額外規定對映 formula_48為點的容量，記做 c(v)，使得一個流 f 不只要滿足邊的流量限制與流量守恆，還要滿足點的流量限制，即formula_49換句話說，流過 v 點的總流量不能超過 v 的容量 c(v)。一個 "s-t 割" 的定義為一個包含一些點和邊的集合，滿足與任一條由 s 到 t 的路徑皆不互斥。並且 s-t 割的"容量" 定義成所有點和邊的容量總和。在此定義之下，廣義最大流最小割定理的敘仍為流量的最大值等於所有 s-t 割的容量最小值。門格爾定理.不共邊路徑問題為給定無向圖 formula_1 及兩頂點 s、t，求從 s 到 t 彼此沒有共同邊的路徑數量的最大值。門格爾定理的敘述為從 s 到 t 彼此沒有共同邊的路徑數量的最大值等於在所有 G 的 s-t 割(以原本的定義)中，頂點分別在不同集合的邊數的最小值。計畫選擇問題.計畫選擇問題敘述如下：當下有 n 個計畫 formula_51可以被實施、m 種裝置 formula_52 可以被購買，要執行計畫必須擁有該計畫要求的裝置，執行計畫 formula_53可獲得 formula_54 的收益，但購買裝置 formula_55 要支付 formula_56 的費用。如何選擇執行計畫並購買所需裝置以獲得淨利的最大值？設 P 為不被執行的計畫的集合，Q 為所購買的裝置，則問題變成求最大值formula_57注意到 formula_58與 P、Q 的選擇無關，故只需求後兩項和的最小值，即formula_59現在考慮一個網路，起源點 s 連線到 n 個點 formula_51，邊的容量分別為 formula_54，超匯點 t 連線到 m 個點 formula_52，邊的容量分別為 formula_56，若執行任務 formula_53需購買裝置 formula_55 ，則在 formula_53、formula_55 之間連上一條容量為無限大的邊，若不需購買裝置，則不連上邊。則 formula_68 對應到一個 s-t 割的容量，其中的兩個集合是要執行的計畫與要購買的裝置和它的餘集，也就是formula_69在此，formula_70，formula_71。於是，原問題轉成求該圖的最大流問題，並且可以藉由各種演算法求得其極值。以下給出一個計畫選擇問題的例子，右圖是該問題對應到的網路。該網路的最小 s-t 割是選擇計畫 "q"3，容量為 250。三個計劃的總收益是 450，因此最大淨利為 450 − 250 = 200。以上解法可以理解為將計畫所給予的收益流過所需裝置，如果無法流滿裝置至 t 的邊，代表執行計畫不合成本，最小割將選擇穿過 s 到計畫的邊而非穿過裝置到 t 的邊。影像分割問題.設原圖有 n 畫素，想要把該圖分割為前景和背景，並且將 i 畫素歸類為前景有效益 pij 的效益。求將該圖分割為前後景的最有效益方法。令 P 為前景的集合，Q 為背景的集合，於是問題轉化成求最大值formula_72因為  bi 的總合是與 P、Q的選取無關，因此等價於求以下最小值formula_73以上的最小值問題可以被描述為一個網路的最小割問題，其中該網路如右圖，以橘點為起源點；紫點為超匯點。各個畫素被描述為網路的頂點，起源點至第 i 個畫素連上一條容量為 pij 的有向邊。則一個 s-t 割代表一種將部分畫素歸類為前景 P、其餘歸類為背景 Q 的安排。歷史.最大流最小割問題最早在1956年被P. Elias, A. Feinstein，和 C.E. Shannon 證明， 並且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年證明了該定理。證明.同之前的設定，"G"("V", "E") 是一個網路(有向圖) ，s 點和 t 點分別為 G 的起源點和超匯點。將所有流考慮成一個歐式空間的有界閉子集，滿足流量限制與流量守恆，而流量是一個連續函式，因此有極大值 |f| 。設 f 達到最大流，令 ("Gf" ) 是 f 的殘留網路，定義換句話說，v∈A 若且唯若 s 可以流出更多流量到 v。我們宣稱 formula_74，其中該 s-t 割的容量定義為formula_75.由於 formula_16 的大小等於所有流出集合 "A" 的流量總和減所有流入集合 "A" 的流量總和，故 formula_77，並且等號成立若且唯若我們用反證法分別證明以上兩點：於是，聲稱得證。由於流量恆不超過容量，|f| 是容量的下界，所以 formula_82 是容量的最小值，由聲稱知，最大流最小割定理得證。