最大流最小割定理
為什麼這個定理很精采？因為它可以幫助我們證明其他的定理！利用這些定理，我們可以得出更多的演算法與發掘其相關性質，從而對網路流的圖論模型有更深一層的見解。
定理
令 \(f\) 是網路 \(G=(V, E, c, s, t)\) 上面的一個 \(s\)-\(t\) 合法流。則以下三項敘述等價：
- \(f\) 是 \(G\) 上面的一個 \(s\)-\(t\) 最大網路流。
- 剩餘網路 \(G_f\) 中，不存在一條從 \(s\) 到 \(t\) 的路徑。
- 存在一個 \(s\)-\(t\) 割 \((A, B)\) 使得其容量等於 \(f\) 之流量，也就是 \(c(A, B) = \vert f\vert \)。
證明 1 \(\implies\) 2
我們可以利用反證法來證明：假設 \(f\) 是 \(G\) 上面的最大流，但 \(G_f\) 當中也存在一條從 \(s\) 到 \(t\) 的路徑 \(P\)。 由於路徑 \(P\) 上面的剩餘容量都是正數，我們令 \(f'\) 為 \(P\) 上能推送的極大流。 此時我們發現一個新的合法流 \(f'' \gets f + f'\)，其流量 \(|f''\vert = \vert f\vert + \vert f'\vert > \vert f\vert \)，與 \(f\) 是 \(G\) 上面的最大流這個假設矛盾。
證明 2 \(\implies\) 3
由於 \(G_f\) 中不存在 \(s\)-\(t\) 路徑，我們令集合 \(A\) 為所有 \(G_f\) 上面可以從 \(s\) 走得到的點形成的集合。定義 \(B = V\setminus A\)，為剩餘的點集。 顯然 \((A, B)\) 是一個 \(s\)-\(t\) 割。接下來我們想證明的是 \(c(A, B) = \vert f\vert \)： 對於任何一條圖 \(G\) 上、跨越這個割的邊 \((x, y)\)，其中 \(x\in A, y\in B\)，我們知道該邊不在剩餘網路 \(G_f\) 中，根據剩餘網路的定義，我們知道這條邊是飽和的(saturated)，也就是說 \(f(x, y) = c(x, y)\)。 更甚者，對於一個反向跨越割的邊 \((z, w)\)，其中 \(z\in B, w\in A\)，如果這條邊有任何容量 \(f(z, w) > 0\)，那麼在剩餘網路中，就有一條邊從 \(w\) 連到 \(z\)，根據 \(A\) 集合的定義我們有 \(z\in A\)，與 \(z\in B\) 的假設矛盾。 因此，我們知道 \(f(z, w) = 0\)。
現在我們可以說 \(|f\vert = c(A, B)\)：\(f\) 的流量，根據定義可以寫為「從 \(A\) 流出去的流量」扣除「流入 \(A\) 的流量」，但是後者是 \(0\)，因此我們得到 \(|f\vert = c(A, B)\)。
證明 3 \(\implies\) 1
對於任何合法流 \(f'\)，由於 \(f'\) 從 \(A\) 流出去的流量，不能超過流經的邊的總容量。因此，我們得知 \(|f'\vert \le c(A, B)\)，現在我們有 \(|f\vert =c(A, B)\)，因此 \(f\) 是一個 \(s\)-\(t\) 最大網路流。