最大流最小割定理

數學敘述

在完整finite flow network上枚舉每個含source、不含sink的vertex subset S；cut capacity只加總S→V\S的directed edges，反向edges不計。任一feasible flow對任一cut皆滿足value≤capacity。完整cut enumeration決定minimum cut；若一個feasible flow與一個cut同值，weak bound立即同時證flow maximum與cut minimum。單一feasible flow或單一cut不自動optimal；本輪不宣稱integral-flow、augmenting-path算法或以有限instances取代一般定理證明。

代表公式（精確 TeX）

F(N)=C(N)

成立條件

• 使用完整有限directed network、nonnegative exact rational capacities與flows。
• 頂點數有界以完整枚舉全部s–t cuts。

符號作用域

• F — 最大流值
• N — 有限流網路
• C — 最小割容量

直觀、定義與常見誤解

完整枚舉全部合法s–t cuts。

flow≤cut以capacity與conservation逐cut核對。

同值pair給雙optimality certificate。

把反向edge算入cut capacity，或從任一feasible flow／cut直接推optimal。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 有限流網路 — feasible flow與value。
• 最佳化問題 — maximum/minimum語義。
• 線性規劃 — 一般定理背景。

驗證界線

有限枚舉只證指定網路；不提前宣稱整數性或特定演算法正確性。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

加入augmenting paths與Ford–Fulkerson邊界。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。