24h購物| | PChome| 登入
2011-06-23 07:38:09| 人氣1,605| 回應0 | 上一篇 | 下一篇

[轉貼*] 網路流 Network Flow

推薦 0 收藏 0 轉貼0 訂閱站台

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

.... 以下略，請參照網址

我要檢舉
台長： Morris

您可能對以下文章有興趣

人氣(1,605) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 演算法 |
此分類下一篇:CountSort + SA
此分類上一篇:[轉貼*] 中國郵路問題 The Chinese post problem

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文