有限流網路

數學敘述

network使用finite loop-free simple directed graph，source s與sink t不同；antiparallel edges可同時存在但每個ordered pair最多一條。capacity與flow為exact nonnegative rationals。feasible flow逐邊滿足0≤f(e)≤c(e)，且每個internal vertex的完整inflow等於outflow。flow value同時由source net outflow與sink net inflow計算並須相等。允許zero capacity與disconnected vertices。feasible不等於maximum，不得提前宣稱min-cut equality或augmenting-path optimality。

代表公式（精確 TeX）

V(f,s,t)=z

成立條件

• vertices、edges、capacity與flow keys完整一一對應；不允許self-loop或duplicate directed edge。
• 所有加總以exact rational arithmetic進行。

符號作用域

• V — 流值算子
• f — 有限邊流
• s — 源點
• t — 匯點
• z — 精確流值

直觀、定義與常見誤解

network資格先固定directed-edge convention。

capacity與conservation為不同feasibility責任。

source與sink兩種flow-value計算必須交叉核對。

只看總流值不檢每條edge／internal vertex，或把任何feasible flow稱maximum。

已採用的推導導讀

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

前置知識

• 有限有向圖 — network carrier。
• 函數映射 — capacity與flow的edge mapping。
• 線性規劃 — capacity與conservation constraints。

驗證界線

本輪不建立max-flow min-cut theorem、residual network或optimality。

not_formalized

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

下一個義務

加入最大流最小割定理。

同源結構化資料

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