兩個本不該相等的數字
在本階的第一篇你學會了讀懂一個流網路：帶容量的邊、一個源點 s、一個匯點 t，以及在每個中間頂點都遵守守恆的流。一個流的值是離開 s 的淨流量，也就是從 s 到 t 的吞吐量。在第二篇你學會了「增加」那個值：建出殘餘網路、找一條從 s 到 t 的增廣路徑、再沿著它推送更多流。這兩篇都在講故事的一側——盡你所能地推送。本篇引入另一側，然後上演一個小小的奇蹟：證明兩側相遇。
另一側是一個割。想像把頂點分成兩隊：一個含有源點 s 的集合 S，以及其餘所有頂點構成的集合 T，T 含有匯點 t。一個 s-t 割正是這樣的劃分 (S, T)。它的容量是所有「從 S 跨到 T」的邊的容量總和——只算往前的邊；從 T 指回 S 的邊不計入。直觀上，割是一道牆：要真正切斷 s 與 t，你得砍掉每一條跨過這道牆往前的邊，而容量就是這麼做的總成本。
現在來看這個本該讓人起疑的主張。任何流的最大值，等於任何割的最小容量。一個數字是你靠「推送」能達到的最佳；另一個是「阻擋」最便宜的方式。它們由相反的動詞、針對不同的物件來定義，卻是同一個數字。這個等式就是最大流最小割定理，而贏得相信它的資格，正是本篇的全部任務。
簡單的一半：任何流都被任何割壓在底下
定理的一半幾乎是免費的，而且值得細細品味，因為它是你第一個弱對偶論證。主張：對「任何」流 f 與「任何」割 (S, T)，f 的值至多等於 (S, T) 的容量。不是最大流配最小割——而是任一個配任一個。理由是一個記帳上的恆等式。無論多少流離開 s，它最終都得跨過這道牆才能抵達 t，因為 t 住在牆的另一側。所以 f 的值等於「從 S 到 T 的邊上的流」減去「從 T 回到 S 的邊上的流」。
那個恆等式源自守恆：把守恆方程式對 S 中每個頂點加總，所有純粹內部的流都互相抵消，剩下的恰好是跨越邊界的淨流。現在來界定它。往前的部分至多等於那些「S 到 T」邊的「容量」之和，因為流永遠不超過容量。往後的部分是我們正在「減去」的量，而流永遠非負，所以減去它只會讓值更小。合起來：f 的值 = （往前的流）-（往後的流）<=（往前的流）<=（往前容量之和）= 割的容量。
困難的一半：殘餘網路發揮作用之處
弱對偶說最大流 <= 最小割。要完成定理，我們需要反向：某個流真的「達到」某個割的容量，使它們相等，而不只是有大小順序。這個證明正是你在上一篇所建立一切的妙處所在。關鍵敘述是關於一個流 f 的三方等價。以下三者要嘛全真、要嘛全假：(1) f 是最大流；(2) f 的殘餘網路沒有增廣路徑——沒有正殘餘容量的 s 到 t 路徑；(3) 存在一個割，其容量等於 f 的值。
- (1) 推得 (2)：若 f 有增廣路徑，你就能沿著它推送更多流並提高值，那麼 f 就不是最大的。這正是上一篇增廣步驟的逆否命題。
- (2) 推得 (3)：這是巧妙的構造。假設沒有增廣路徑。令 S 為在殘餘網路中仍從 s 可達的所有頂點之集合；t 不在 S 裡，因為沒有殘餘路徑能抵達它。
- 檢視割 (S, T)。每一條從 S 到 T 往前的邊都必須是飽和的——所載的流等於其容量——否則它會留下正的殘餘容量，讓你能再往 T 多走一步，這就與「S 恰是可達集」矛盾。
- 同理，每一條從 T 到 S 往後的邊都必須載零流，否則就會有往後進入 S 的殘餘容量——同樣會擴張可達集。所以往前的邊全滿、往後的邊全空。
- 把這代入值的恆等式：f 的值 =（往前的流）-（往後的流）=（滿載的往前容量）- 0 = (S, T) 的容量。弱對偶的不等式變成了等式。於是 (3) 成立，再配上弱對偶，f 就是最大的，得 (3) 推得 (1)。
看看這個等價交付了什麼。同一個條件——不再有增廣路徑——既告訴 福特-富爾克森法「何時該停」，又正是把一個吻合的割交到你手上的條件。最終殘餘網路中的可達集 S 不是另一次計算；你能從演算法最後跑的那次廣度或深度優先搜尋直接讀出最小割。證明與演算法，是同一個物件的兩個視角。
對偶的初嚐
把一個最大化問題與一個最小化問題配成對、且兩個最佳值重合——這正是對偶的核心，是最佳化中最深刻的主題。最大流是一個線性規劃：變數是每條邊上的流，約束是容量（流 <= 容量）與守恆，而你要最大化值。每個線性規劃都有一個夥伴，它的「對偶」，由相同的資料機械地導出；把最大流線性規劃的對偶拿來最小化，結果——幾乎完全——就是最小割問題。一般理論保證只要問題行為良好，兩個最佳值就相等，而最大流最小割正是這個承諾最受人喜愛的具體實例。
為什麼這幅圖景的意義超越優雅？因為對偶給你一張「證書」。單獨一個流只是你算出的一個數字；把它配上一個容量相等的割，你就有了一個無法偽造的證明：不存在更大的流，能在一趟掃描中核驗，無需信任演算法。這就是弱對偶的實際禮物：兩側的可行解把真正的最佳值夾在中間，而相等則精準地把它釘死。你會在流之外的許多地方再次遇到這個原始對偶的想法——它撐起了整個最佳化中良好下界的構築方式。
誠實的界線：定理承諾與不承諾什麼
要對「相等」的意思講究。定理說的是最大流的「值」等於最小割的「容量」——兩個數字相等。它並沒有說那個達到最大的流、或達到最小的割是唯一的。一個網路可以有許多不同的最大流、許多不同的最小割，全都共享那一個共同的值。所以「找最小割」可以有好幾個正確答案；你從最終殘餘網路讀出的割是「一個」最小割，不一定是「那個」。
這個漂亮的等式也倚賴一些值得點名的假設。經典敘述假設容量有限、且單一源點與單一匯點；多個源點或匯點可以透過加上超級源點與超級匯點來處理，但你必須在套用定理之前先完成那個轉換。整數容量還給你一個額外的獎賞——整數性定理說最大流存在於整數中——這正是讓流成為匹配乾淨工具的原因，畢竟半條邊毫無意義。當容量為無理數時，樸素的福特-富爾克森法甚至可能不會終止，這提醒我們定理講的是等式的存在性，而非任何特定演算法能否達到它。
最後，把定理與它的執行時間分開。最大流最小割是個關於「什麼是真的」的敘述，其證明完全不涉及任何事情要花多久。「計算」那個共同值的成本，全看你如何搜尋增廣路徑：盲目的福特-富爾克森可能很慢、甚至不終止，而 埃德蒙茲-卡普（用廣度優先搜尋找最短增廣路徑）以 O(V E^2) 執行，而迪尼茨演算法用阻塞流做得更好。對偶是精確且永恆的；效率則是由你所選演算法述說的另一個工程故事。