# 最大流最小割定理

有限容量網路的最大feasible flow value等於全部s–t cuts中的最小capacity。

mko-max-flow-min-cut-theorem · theorem · v0.10.0



## 數學敘述

在完整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。





## 已採用的推導導讀

[完整四個 cut 與等值雙證書](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-max-flow-min-cut-theorem-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限流網路](https://ocme.evemisslab.com/zh-Hant/mko/mko-finite-flow-network/) — feasible flow與value。
- [最佳化問題](https://ocme.evemisslab.com/zh-Hant/mko/mko-optimization-problem/) — maximum/minimum語義。
- [線性規劃](https://ocme.evemisslab.com/zh-Hant/mko/mko-linear-programming/) — 一般定理背景。





## 驗證界線

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

not_formalized

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





## 下一個義務

加入augmenting paths與Ford–Fulkerson邊界。





## 同源結構化資料

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

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/max-flow-min-cut-theorem.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-max-flow-min-cut-theorem/index.md)