2011-06-23 07:38:09Morris
[轉貼*] 網路流 Network Flow
http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f3cec71910d4a0106624e839f2891b17198ef58be
網路流Network Flow
網路流(Network Flow)是近年來在圖論中相當熱門的問題，在
網路流Network Flow
網路流(Network Flow)是近年來在圖論中相當熱門的問題，在
1955 年，T.E. Harris 在研究鐵路最大通量時，首先提出在一個給定
的網路上尋求兩點間最大運輸量的問題。1956 年，L.R. Ford 和D.R.
Fulkerson 給出解決這類問題的演算法，從而建立了網路流理論。
最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯繫，開闢了圖論應用的新途徑。
關於網路流的定義Definitions of Network Flow的網路上尋求兩點間最大運輸量的問題。1956 年，L.R. Ford 和D.R.
Fulkerson 給出解決這類問題的演算法，從而建立了網路流理論。
最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯繫，開闢了圖論應用的新途徑。
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)。
.... 以下略，請參照網址
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)。
.... 以下略，請參照網址