完整四個 cut 與等值雙證書

目標與範圍

枚舉四點網路全部 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 到其補集的有向容量。

逐步主鏈

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

\operatorname{in}(a)=3+0,\quad\operatorname{in}(b)=2+1

\operatorname{out}(a)=1+2=3,\quad\operatorname{out}(b)=3+0=3

|f|=f_{sa}+f_{sb}=3+2

|f|=5=f_{at}+f_{bt}=2+3

s\in S,\quad t\notin S

S\in\{\{s\},\{s,a\},\{s,b\},\{s,a,b\}\}

|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)

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

\{c(S):s\in S,t\notin S\}=\{5,5,7,5\}

\min_S c(S)=5\text{ attained at }S=\{s\}

|f|=5=c(\{s\})

f\text{ maximum},\quad\{s\}\text{ minimum cut},\quad\max|h|=\min c(S)=5

局部子步與引理

本稿無局部子步。

逐步反向審查

• 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、反控制與修訂記錄）