9.2 網路流與最大流最小割定理#
本章導言#
如果說背包問題展示了「離散選擇」的困難，網路流則展示了「連續流動」的優雅：當資源沿著管道網路傳輸、容量有限、可以任意拆分時，最大流問題有多項式演算法，而且最大流恰等於最小割——一道把「極值」與「分割」焊接在一起的定理，被譽為組合優化最美的結果之一。它的思想源頭可追溯至 1920–30 年代數學家 Menger 的路徑定理與 Kakutani 對極大化—極小化對偶的观察；1956 年 Lester R. Ford 與 Delbert R. Fulkerson 提出了如今通行的增廣路徑演算法，Ford 於 1957 年把方法帶到 RAND 與後來的加州大學。本節將完整走一遍 Ford–Fulkerson 演算法、證明最大流最小割定理的直覺，並展示它在運輸、通訊、排程與甚至「一個管理問題如何被翻譯成圖」上的通用性。
網路流模型#
一個有向網路 \(G=(V,E)\) ，指定源點 \(s\) 與匯點 \(t\) ，每條弧 \((i,j)\) 有容量 \(c_{ij} \ge 0\) 。流 \(f\) 是弧上的實值函數，滿足：
- 容量約束： \(0 \le f_{ij} \le c_{ij}\) ；
- 流量守恆：對每個中間節點 \(v \notin \{s,t\}\) ， \(\sum_{i} f_{iv} = \sum_{k} f_{vk}\) （流入＝流出）。
網路的流值 \(|f| = \sum_k f_{sk} - \sum_i f_{is}\) （淨流出 \(s\) ）。最大流問題： \(\max |f|\) 。
割（cut）：把 \(V\) 分成含 \(s\) 的 \(S\) 與含 \(t\) 的 \(T=V\setminus S\) ，割的容量 \(c(S,T) = \sum_{i \in S, j \in T} c_{ij}\) （只計從 \(S\) 指向 \(T\) 的弧）。
最大流最小割定理（1956）：任何網路中
此定理是強對偶：左邊是優化（選流），右邊是分割（選邊界）。它給出一個極其實用的判別準則：一旦找到某個流與某個割，且「流值＝割容量」，即可宣告兩者皆為最優——不需要搜遍所有流。這與 3.2 節 LP 對偶理論中「原始最優＝對偶最優」的結構完全平行：最大流問題的線性規劃對偶，恰好就是「找最小割」。
Ford–Fulkerson 增廣演算法#
在殘量網路 \(G_f\) 上反覆找 \(s\to t\) 路徑並增廣：
- 若 \(G_f\) 中存在 \(s\to t\) 路徑 \(P\) ，取瓶頸 \(\delta = \min_{(i,j)\in P} r_{ij}\) （ \(r\) 為殘量）；
- 沿 \(P\) 正向加 \(\delta\) 、反向減 \(\delta\) （反向弧允許「撤回」先前的流——這是演算法正確的關鍵）；
- 直到 \(s\) 在 \(G_f\) 中不可達 \(t\) ，此時 \(|f|\) 即最大流，不可達集合 \(S\) 與其補集構成最小割。
若所有容量為整數，每次增廣至少增加 1，演算法在 \(O(|f^\ast| \cdot |E|)\) 步內結束（ \(f^\ast\) 為最優流值）；配合 Edmonds–Karp（BFS 找最短增廣路徑）可達 \(O(VE^2)\) ，Dinic、Push-Label 等演算法更快。演算法終止時「 \(s\) 可達集合」即最小割的 \(S\) 側，這一步把最優解與證明同時交給使用者——優化與 certificate 的統一是此演算法的哲學亮點。
例題 9.2.1#
例題 9.2.1：網路弧與容量為： \(s\to a\) ：4、 \(s\to b\) ：3、 \(a\to b\) ：1、 \(a\to t\) ：2、 \(b\to t\) ：3。(1) 用 Ford–Fulkerson 求最大流；(2) 給出對應最小割並驗證定理。
解：
(1) 增廣三步（次序不唯一，結果相同）：
| 步驟 | 增廣路徑 | 瓶頸 | 累積流值 |
|---|---|---|---|
| 1 | \(s\to b\to t\) | \(\min(3,3)=3\) | 3 |
| 2 | \(s\to a\to t\) | \(\min(4,2)=2\) | 5 |
| 3 | \(s\to a\to b\to t\) | \(b\to t\) 殘量 \(=3-3=0\) ，路徑不通 | 5 |
第 3 步無增廣路徑可找（ \(b\to t\) 已飽和、 \(a\to t\) 已飽和），演算法終止， \(|f^\ast| = 5\) 。具體流配置： \(f_{sb}=3\) 、 \(f_{st}\) 不存在、 \(f_{sa}=2\) 、 \(f_{at}=2\) 、 \(f_{ab}=0\) （若第 3 步以 \(s\to a\to b\) 試圖經 \(b\) 出， \(b\to t\) 無殘量）。守恆驗算： \(a\) 流入 2、流出 2； \(b\) 流入 3、流出 3。
(2) 從 \(s\) 出發在殘量網路中標記可達集合： \(s\) 可達 \(a\) （殘量 \(4-2=2\) ）、可達 \(b\) （殘量 \(3-3=0\) ，不可經 \(s\to b\) ）； \(a\) 的 \(a\to t\) 、 \(a\to b\) 殘量： \(a\to t\) 為 0、 \(a\to b\) 為 1，故 \(a\) 可達 \(b\) ； \(b\) 出弧皆殘量 0。可達集 \(S = \{s,a,b\}\) ， \(T = \{t\}\) 。最小割容量 \(= c_{at} + c_{bt} = 2 + 3 = 5\) 。流值 5 ＝ 割容量 5，由最大流最小割定理， \(|f|=5\) 確為最大流，割為最小割。直覺：所有流向 \(t\) 的「咽喉」就是 \(a\to t\) 與 \(b\to t\) 兩條弧，合計容量 5，任何流都不可能超過——這也顯示瓶頸不在源端而在匯端，與 6.2 節「關鍵路徑決定工期」的思維同構：系統效能由最窄處決定。
應用全景#
- 運輸與物流：產地—銷地網路的最大可運量、管線輸送能力評估；
- 通訊網路：鏈路頻寬分配、 \(s\) – \(t\) 可靠性（最小割即「切斷通訊所需破壞的最小鏈路集合」——軍事通訊抗毀性分析的直接工具）；
- 二分圖配對：Hall 定理與 Kőnig 定理皆可由最大流最小割導出，指派問題（3.3 節）的特殊情形；
- 排程與產能：6.2 節 CPM 中「活動—事件」網路的產能版本；整數流版本可建模多商品流；
- 影像分割（計算機視覺）：把像素當節點、相鄰像素容量依色彩差、用最小割分割前景背景——組合優化跨出管理進入 AI。
前因後果與驅動關係#
- 驅動：二戰的補給輸送（10.1 節）與戰後的管線、鐵路、電話網擴張，都需要回答「這套系統最多能送多少」；Menger 1927 年的路徑定理與 1930–40 年代的對偶研究提供了理論胚胎，1950 年代軍事後勤與 RAND 的研究把它們收斂為可計算的演算法。冷戰時期的「蘇聯鐵路網瓶頸分析」是著名應用案例之一。
- 回頭改變實務：Ford–Fulkerson 方法成為運籌學與計算機科學的共同基礎課程；最大流最小割定理是強對偶的典範，加深了管理者對「瓶頸管理」的直覺—— Bottleneck 的量化；網路流框架也反哺第 6 章（PERT 活動網路的資源流分析）與第 4 章（服務網路的容量規劃）。
- 交叉引用：對偶思想見 3.2 節影子價格；指派與二分圖見 3.3 節；增廣路徑的「殘量＋撤回」機制與 9.1 節 DP 的「保留資訊」哲學相呼應；《金融的數學》第 7 章風險傳染網絡的級聯失效，可視為「割」概念的動態化。
練習#
- 承例題 9.2.1，若 \(b\to t\) 容量提高到 5，最大流變多少？新的最小割在哪裡？
- 證明：任何割容量都是流值的上界（提示：流值＝ \(S\) 的淨流出，而淨流出不超過 \(S\to T\) 的總容量）。
- 某水管网： \(s\to a\) （10）、 \(s\to c\) （8）、 \(a\to b\) （7）、 \(a\to c\) （2）、 \(c\to t\) （9）、 \(b\to t\) （6）。求最大流與最小割。
- 為何演算法允許「沿反向弧撤回流」？舉一個不撤回就會卡住的容量配置為例。
- 思考題：把「最小割」的概念延伸到組織：部門間協作網中，若把「資訊傳遞容量」當弧容量，最小割代表什麼？管理者應如何解讀？（提示：對照 6.2 節關鍵路徑與 4 節排隊擁塞。）
名詞速查表#
- 網路流：有向網路弧上滿足容量與守恆約束的流動配置。
- 殘量網路：扣除已用流、加上反向弧後的剩餘可增廣網路。
- 增廣路徑：殘量網路中的 \(s\) – \(t\) 路徑，沿之可提升流值。
- 割：分離 \(s\) 與 \(t\) 的節點分割，容量為跨割弧容量和。
- 最大流最小割定理：最大流值恰等於最小割容量（Ford–Fulkerson, 1956）。
- 強對偶：優化問題最優值與其對偶分割問題最優值相等的結構。
（本節完）