Can you summarize the following document?
        
  令為一個網路(有向圖),並且有一個起源點 s 和一個超匯點 t,代表 s 是所有流的源頭,t 是所有流的終點。

  定義: 一條邊的容量是一個對映,記做 或者,代表著能通過這條邊的最大的流量。  定義: 一個流是一個對映,記做 或者 。每一條流有以下兩個限定條件: 定義: 流的流量的定義是 s 為 N 的源點,代表著從源點流向目標點的流量。

  定義:一個 s-t 割 是一種 V 的劃分使得 。"C "的割集是集合 因此如果 C 的割集是空集合,則.  定義: 一個s-t割的容量是 其中 formula_6 如果 formula_7 並且 formula_8, 0 反之。

  最大流最小割問題可以被看做為一對線性規劃對偶問題。 注意到在給定的 s-t 割 formula_9 中,如果 formula_7 那麼 formula_11 並且 0 反之。 所以 formula_12 應該等於 1 並且 formula_13 應該等於0。由線性規劃中的強對偶定理推得最大流最小割問題中的等式,也就是說如果原問題有一個最優解 "x"*,則對應問題也有一個最優解 "y"*,並且兩個解相等。

  上圖是一個網路,上有流量為 7 的流。令 S 集合和 T 集合分別包含所有白色和灰色的點, 從而形成了一個割集包含圖中虛線的 s-t 割,並且其容量為 7,與流量相同。故由大流最小割定理知,前述的流與 s-t 割皆達到流量及容量的極值。

  

  額外規定對映 formula_14為點的容量,記做 c(v),使得一個流 f 不只要滿足邊的流量限制與流量守恆,還要滿足點的流量限制,即 換句話說,流過 v 點的總流量不能超過 v 的容量 c(v)。一個 "s-t 割" 的定義為一個包含一些點和邊的集合,滿足與任一條由 s 到 t 的路徑皆不互斥。並且 s-t 割的"容量" 定義成所有點和邊的容量總和。  在此定義之下,廣義最大流最小割定理的敘仍為流量的最大值等於所有 s-t 割的容量最小值。

  不共邊路徑問題為給定無向圖 formula_16 及兩頂點 s、t,求從 s 到 t 彼此沒有共同邊的路徑數量的最大值。  門格爾定理的敘述為從 s 到 t 彼此沒有共同邊的路徑數量的最大值等於在所有 G 的 s-t 割(以原本的定義)中,頂點分別在不同集合的邊數的最小值。

  計劃選擇問題敘述如下:當下有 n 個計劃 formula_17可以被實施、m 種裝置 formula_18 可以被購買,要執行計劃必須擁有該計劃要求的裝置,執行計劃 formula_19可獲得 formula_20 的收益,但購買裝置 formula_21 要支付 formula_22 的費用。如何選擇執行計劃併購買所需裝置以獲得淨利的最大值?  設 P 為不被執行的計劃的集合,Q 為所購買的裝置,則問題變成求最大值 注意到 formula_24與 P、Q 的選擇無關,故只需求後兩項和的最小值,即 現在考慮一個網路,起源點 s 連線到 n 個點 formula_17,邊的容量分別為 formula_20,超匯點 t 連線到 m 個點 formula_18,邊的容量分別為 formula_22,若執行任務 formula_19需購買裝置 formula_21,則在 formula_19、formula_21 之間連上一條容量為無限大的邊,若不需購買裝置,則不連上邊。則 formula_34 對應到一個 s-t 割的容量,其中的兩個集合是要執行的計劃與要購買的裝置和它的餘集,也就是 在此,formula_36,formula_37。於是,原問題轉成求該圖的最大流問題,並且可以藉由各種演算法求得其極值。  以下給出一個計劃選擇問題的例子,右圖是該問題對應到的網路。  該網路的最小 s-t 割是選擇計劃 、 與裝置 、,容量為 250。三個計劃的總收益是 450,因此最大淨利為 450 − 250 = 200。  以上解法可以理解為將計劃所給予的收益流過所需裝置,如果無法流滿裝置至 t 的邊,代表執行計劃不合成本,最小割將選擇穿過 s 到計劃的邊而非穿過裝置到 t 的邊。

  設原圖有 n 畫素,想要把該圖分割為前景和背景,並且將 i 畫素歸類為前景有效益,歸類為背景有效益,但是若 i、j 畫素相鄰且被歸類為不同塊,則會減少 的效益。求將該圖分割為前後景的最有效益方法。  令 P 為前景的集合,Q 為背景的集合,於是問題轉化成求最大值 因為 、 的總合是與 P、Q的選取無關,因此等價於求以下最小值 以上的最小值問題可以被描述為一個網路的最小割問題,其中該網路如右圖,以橘點為起源點;紫點為超匯點。各個畫素被描述為網路的頂點,起源點至第 i 個畫素連上一條容量為 的有向邊;第 i 個畫素至超匯點連上一條容量為 的有向邊。相鄰的畫素 i、j 之間連上來回兩條容量為 的有像邊。則一個 s-t 割代表一種將部分畫素歸類為前景 P、其餘歸類為背景 Q 的安排。

  最大流最小割問題最早在1956年被P. Elias, A. Feinstein,和 C.E. Shannon 證明, 並且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年證明了該定理。

  同之前的設定, 是一個網路(有向圖),s 點和 t 點分別為 G 的起源點和超匯點。  將所有流考慮成一個歐式空間的有界閉子集,滿足流量限制與流量守恆,而流量是一個連續函式,因此有極大值 |f| 。  設 f 達到最大流,令 是 f 的殘留網路,定義  換句話說,v∈A 當且僅當 s 可以流出更多流量到 v。  聲稱 formula_40,其中該 s-t 割的容量定義為 由於 formula_42 的大小等於所有流出集合 "A" 的流量總和減所有流入集合 "A" 的流量總和,故 formula_43,並且等號成立當且僅當 我們用反證法分別證明以上兩點:  於是,聲稱得證。  由於流量恆不超過容量,|f| 是容量的下界,所以 formula_48 是容量的最小值,由聲稱知,最大流最小割定理得證。
在最優化理論中,最大流最小割定理提供了對於一個網路流,從源點到目標點的最大的流量等於最小割的每一條邊的和。即對於一個如果移除其中任何一邊就會斷開源點和目標點的邊的集合的邊的容量的總和。