# 完整四個 cut 與等值雙證書 [← 導讀目錄](https://ocme.evemisslab.com/zh-Hant/derivations/) · [原始 MKO](https://ocme.evemisslab.com/zh-Hant/mko/mko-max-flow-min-cut-theorem/) 這是使用者已採用的自然語言教學導讀。有限／算術檢查不等於普遍證明；本輪未跑 Lean，各稿審查範圍見其修訂記錄。來源原有的狀態標籤保留為歷史資料。公式保留精確 TeX，不另造語意 AST。 derivation-mko-max-flow-min-cut-theorem-01 · ocme-new142-reader-adoption-20261021 ## 目標與範圍 枚舉四點網路全部 s-t cuts，給值 5 的可行流與同值 cut。 有限完整證書；不證 augmenting-path、整數性或用實例取代一般定理。 ## 已知條件與符號 - algebra - sets - flow_def - cut_def - G1 — V={s,a,b,t}；邊依序 sa,sb,ab,at,bt,ba，容量 (3,2,1,2,3,1)，流 (3,2,1,2,3,0)。 - S^c — 相對 V 的 cut 補集 - c(S) — 只計向外邊的容量 ## 規則與來源 - mko_definition · cited — 在完整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取代一般定理證明。 · mko-max-flow-min-cut-theorem - algebra · prerequisite — 實數域的等式運算；除法前分母必非零，不等式乘正數保持方向。 - sets · prerequisite — 集合的聯、交、補集、包含與函數逆像以逐元素定義計算。 - flow_def · prerequisite — 有限簡單有向網路無 self-loop、無重複 ordered pair，但容許反平行邊；可行流滿足每邊 0≤f≤c 及每內點流入等於流出，值為來源淨流出及終點淨流入。 - cut_def · prerequisite — 合法 s-t cut 是含 s 不含 t 的頂點子集 S；容量只加 S 到其補集的有向容量。 ## 逐步主鏈 S01 · implies操作前 E=\{sa,sb,ab,at,bt,ba\},\quad c=(3,2,1,2,3,1) 操作後 \text{all edges loop-free and unique},\quad0\le f\le c 條件：無 規則：flow_def · 依賴：G1 葉節點依據：flow_def 完整六邊無重複有向對，反平行合法，逐邊核流容量界。 S02 · implies操作前 \operatorname{in}(a)=3+0,\quad\operatorname{in}(b)=2+1 操作後 \operatorname{out}(a)=1+2=3,\quad\operatorname{out}(b)=3+0=3 條件：無 規則：algebra · 依賴：G1, S01 葉節點依據：algebra 完整兩內點守恆，流確可行。 S03 · implies操作前 |f|=f_{sa}+f_{sb}=3+2 操作後 |f|=5=f_{at}+f_{bt}=2+3 條件：無 規則：algebra · 依賴：G1, S02 葉節點依據：algebra 來源與終點淨值一致。 S04 · definition操作前 s\in S,\quad t\notin S 操作後 S\in\{\{s\},\{s,a\},\{s,b\},\{s,a,b\}\} 條件：無 規則：cut_def · 依賴：G1 葉節點依據：cut_def a,b 各可在或不在 S，完整列四種而不混補集同一 cut。 S05 · implies操作前 |h|=\sum_{e:S\to S^c}h_e-\sum_{e:S^c\to S}h_e\quad(h\text{ feasible}) 操作後 |h|\le\sum_{e:S\to S^c}h_e\le\sum_{e:S\to S^c}c_e=c(S) 條件：h\text{ feasible},\ s\in S,\ t\notin S 規則：algebra · 依賴：S01, S02, S04 葉節點依據：algebra 加總 S 內點的淨流，內部邊抵銷，只留 cut 淨流；入流非負和容量界給全可行流弱界。 S06 · implies操作前 c(\{s\}),c(\{s,a\}),c(\{s,b\}),c(\{s,a,b\}) 操作後 3+2=5,\quad2+1+2=5,\quad3+3+1=7,\quad2+3=5 條件：無 規則：algebra · 依賴：G1, S04 葉節點依據：algebra 只數向外邊。對 {s,a}，ba 是流入不計；對 {s,b}，ba 才是向外並計容量 1。 S07 · implies操作前 \{c(S):s\in S,t\notin S\}=\{5,5,7,5\} 操作後 \min_S c(S)=5\text{ attained at }S=\{s\} 條件：無 規則：algebra · 依賴：S04, S06 葉節點依據：algebra 完整清單最小值為 5，可選來源單點 cut 當證書。 S08 · implies操作前 |f|=5=c(\{s\}) 操作後 f\text{ maximum},\quad\{s\}\text{ minimum cut},\quad\max|h|=\min c(S)=5 條件：無 規則：algebra · 依賴：S03, S05, S07 葉節點依據：algebra 任意可行 h≤此 cut 5，候選 f 達到 5；任意 cut 又≥f 值，兩邊同時最優。 ## 局部子步與引理 本稿無局部子步。 ## 逐步反向審查 - S08 · premise_audit · S03, S05, S07 — 這是給定有限網路的等值雙證書，不宣稱算法或一般整數流性。 - S07 · premise_audit · S04, S06 — 不是因單獨找到一個容量 5 cut 就稱最小；完整表或弱界才支持。 - S06 · premise_audit · G1, S04 — 四個合法 cut 全算完且方向逐一明示。 - S05 · premise_audit · S01, S02, S04 — 弱界不假定 h 為主候選 f，才可用來證最優。 - S04 · premise_audit · G1 — s,t 歸屬固定，故 2^2 種已完整。 - S03 · premise_audit · G1, S02 — 所有內點守恆已核，非只算端點。 - S02 · premise_audit · G1, S01 — ba 必在 a 入流及 b 出流中保留。 - S01 · premise_audit · G1 — 網路資格及每邊可行性先行。 ## 錯誤控制與反例 cut 方向只算 S→V\S，不算反向。 任意比較流弱界量化全部可行 h，才可證 maximum。 - cut 兩個方向容量都加。 → reject — ba 在 {s,a} cut 是入邊，不能算入。 - 任何可行流已最大。 → reject — 只有與 cut 弱界達同值的候選才由此證最優。 - 此實例證所有 augmenting-path 演算法正確。 → reject — 本稿沒有算法或一般終止證明。 ## 結論與限制 最大流與最小 cut 值皆 5；全部四個 cut 為 5、5、7、5。 ## 驗證及來源綁定 2 個本稿宣告算術檢查；只支持所列算式。 - source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f - adopted source SHA-256: a3f6ca7038c79f9eea7d99baeadfe28a147465af5256279afd33c427ad4be560 - original source SHA-256: 05cf7399183d2ca5c249a6bc36b388edd4cd3634a6674052196c12852140714a - Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW [同源完整 JSON（含公式、AST、反控制與修訂記錄）](https://ocme.evemisslab.com/data/derivations/coverage-20261021/guides/derivation-mko-max-flow-min-cut-theorem-01.json)