# 有限流網路

有限有向網路中的非負流須逐邊不超過capacity，並在source與sink以外每個頂點滿足流量守恆。

mko-finite-flow-network · definition · v0.10.0



## 數學敘述

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。





## 已採用的推導導讀

[逐邊與逐內點核可行流](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-finite-flow-network-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [有限有向圖](https://ocme.evemisslab.com/zh-Hant/mko/mko-finite-directed-graph/) — network carrier。
- [函數映射](https://ocme.evemisslab.com/zh-Hant/mko/mko-function-mapping/) — capacity與flow的edge mapping。
- [線性規劃](https://ocme.evemisslab.com/zh-Hant/mko/mko-linear-programming/) — capacity與conservation constraints。





## 驗證界線

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

not_formalized

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





## 下一個義務

加入最大流最小割定理。





## 同源結構化資料

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

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