最大流最小割定理（max-flow min-cut theorem）

關於管路網路的兩個問題看似無關：你能從抽水機推多少到排水口，以及多便宜地剪管子就能把兩者切斷？最大流最小割定理說它們的答案完全相同。你能運的最大量，等於切斷路線的最小代價。這個出人意表的等式是流理論的核心，也是你初嚐線性規劃對偶。

定理斷言：任一 s-t 流的最大值，等於任一 s-t 割的最小容量。「至多」那一半容易——每單位流量都得從 s 側越界到 t 側穿過任一割，故對每個割都有 值 <= 割容量，於是 最大流 <= 最小割。「至少」（等號）那一半才是核心，而證明是構造性的：執行增廣路徑法，直到殘餘網路中不存在增廣路徑為止。此時令 S 為殘餘網路中仍能從 s 抵達的所有頂點，T 為其餘。則 s 在 S、t 在 T，每條從 S 到 T 的邊必飽和（否則它會留有殘餘容量，t 便可達），而每條從 T 到 S 的邊載零流量。於是這個流的值等於這個割的容量——一個流與一個割數字相同，由「至多」那半，兩者都必為最佳。

在最佳處有三者相等：存在最大流、存在最小割、且兩者同值，這也正是增廣路徑演算法為何正確（它恰在流碰到割時停止）的原因。最小割還點名了真正的瓶頸，並提供一張憑證：你只要展示一個容量相等的割，就能證明某個流是最大的，無須信任演算法。這正是縮影版的線性規劃對偶——最大流是原始 LP、最小割是其對偶——而同樣的模式在最佳化中反覆出現。誠實的提醒：對實數容量等號精確成立，但構造性證明的終止需小心（整數或有理容量，或埃德蒙茲-卡普的最短路徑規則）。