Network Flow

source: http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f3cec71910d4a0106624e839f2891b17198ef58be

網路流 Network Flow

(Network Flow)是近年來在圖論中相當熱門的問題，在
1955 年 ，T.E. Harris 在研究鐵路最大通量時，首先提出在一個給定
的網路上尋求兩點間最大運輸量的問題。1956 年，L.R. Ford 和 D.R.
Fulkerson 給出解決這類問題的演算法，從而建立了網路流理論。
最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯繫，開闢了圖論應用的新途徑。
關於網路流的定義 Definitions of Network Flow
1. 網路(Network)：圖 G = ( V, A )為一有向圖，稱為網路
2. 源點與匯點(Source and Sink)：令一點 S 為源點、一點 T 為匯點，其餘點則為中間點
3. 容量(Capacity)：每條弧上定義一個非負數 C(u, v)
4. 流量(Flow)：每條弧上定義一個 F(u, v) ，所有 。
5. 剩餘容量(Residual Capacity)：每條弧上定義一個 Cf(u, v) = C(u, v) – F(u, v) 為該弧的剩餘
容量，而剩餘容量的集合則稱為剩餘網路(Residual Network)
6. 網路的流量(Flow of Network)：由源點發出，匯點匯集的總流量 ，，， ，若其為該網路能產生的
量，則稱其為 量量量 (Maximum Flow)。 ...