网络流

维基百科，自由的百科全书

在圖論中，網絡流 (Network Flow) 是指在一個每條邊都有容量 (Capacity) 的有向圖分配流，使一條邊的流量不會超過它的容量。（邊有附帶容量的圖稱為網絡。）一道流必須符合一個結點的進出的流量相同的限制，除非這是一個源點 (Source) ──有較多向外的流，或是一個匯點 (Sink) ──有較多向內的流。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點 (Node) 的網絡中遊動的任何事物。

[编辑] 定義

假設 $G (V, E)$ 是一個有限的有向圖，它的每條邊 $(u, v) \in E$ 都有一個非負值實數的容量 $c (u, v)$ 。如果 $(u, v) \not \in E$ ，我們假設 $c (u, v) = 0$ 。我們區別兩個頂點：一個源點 $s$ 和一個匯點 $t$ 。一道網絡流是一個對於所有結點 $u$ 和 $v$ 都有以下特性的實數函數 $f:V \times V \rightarrow \mathbb{R}$ ：

容量限制 (Capacity Constraints):	$\ f(u, v) \le c(u, v)$ 一條邊的流不能超過它的容量。
斜對稱 (Skew Symmetry):	$\ f(u, v) = - f(v, u)$ 由 $u$ 到 $v$ 的淨流必須是由 $v$ 到 $u$ 的淨流的相反（參考例子）。
流守恆 (Flow Conservation):	除非 $u = s$ 或 $u = t$ ，否則 $\ \sum_{w \in V} f(u, w) = 0$ 一結點的淨流是零，除了「製造」流的源點和「消耗」流的匯點。

注意 $f (u, v)$ 是由 $u$ 到 $v$ 的淨流。如果該圖代表一個實質的網絡，由 $u$ 到 $v$ 有 4 單位的實際流及由 $v$ 到 $u$ 有 3 單位的實際流，那麼 $f (u, v) = 1$ 及 $f (v, u) = - 1$ 。

邊的剩餘容量 (Residual Capacity) 是 $c f (u, v) = c (u, v) - f (u, v)$ 。這定義了以 $G f (V, E f)$ 表示的剩餘網絡 (Residual Network)，它顯示可用的容量的多少。留意就算在原網絡中由 $u$ 到 $v$ 沒有邊，在剩餘網絡乃可能有由 $u$ 到 $v$ 的邊。因為相反方向的流抵消，減少由 $v$ 到 $u$ 的流等於增加由 $u$ 到 $v$ 的流。擴張路徑 (Augmenting Path) 是一條路徑 $(u_1, u_2, \dots, u_k)$ ，而 $u 1 = s$ 、 $u k = t$ 及 $c f (u i, u i + 1) > 0$ ，這表示沿這條路徑傳送更多流是可能的。

[编辑] 例子

一個顯示了流及容量的流網絡。

在右邊可以看到一個有以 $s$ 標示的源點、以 $t$ 標示的匯點及 4 個額外結點的流網絡。流及容量以 $f / c$ 顯示。注意網絡怎樣保證斜對稱、容量限制及流守恆。由 $s$ 到 $t$ 的總流量為 5，由此可簡單地觀察到源於 $s$ 的所有向外流是 5，也就是匯於 $t$ 的向內流。我們知道在其它結點中沒有任何流出現或消失。

上面的流網絡的剩餘網絡，顯示了剩餘容量。

在下面你可以看到對既定的流的剩餘網絡。注意某些邊的剩餘容量是正數而原來的容量是零，如邊 $(d, c)$ 。這道流不是一道最大流。沿路徑 $(s, a, c, t)$ 、 $(s, a, b, d, t)$ 及 $(s, a, b, d, c, t)$ 還有可用的容量，也就是擴張路徑。第一條路徑的剩餘容量是 $min(c (s, a) - f (s, a), c (a, c) - f (a, c), c (c, t) - f (c, t)) = min(5 - 3,3 - 2,2 - 1) = min(2,1,1) = 1$ 。注意擴張路徑 $(s, a, b, d, c, t)$ 在原來的網絡中並不存在，但你可以沿它傳送流，因此仍是一道正當的流。

假如這是一個真實的網絡，由 $a$ 到 $b$ 的 2 單位的流及由 $b$ 到 $a$ 的 1 單位的流事實上可能存在，但我們只維持淨流。

[编辑] 應用

將一連串的水管繪畫成一個網絡。每條水管有一特定的闊度，因此只可以保持一特定的水流量。當任何水管匯合，流入匯流點的總水量必須等於流出的水量，否則我們會很快地缺水，或者我們會團積水。我們有一個作為源點的入水口，和一個作為匯點的出水口。一道流便是一條由源點到匯點而使從出水口流出的總水量一致的可能路徑。直觀地，一個網絡的總流量是水從出口流出的速率。

流可以關於在交通網絡上的人或物質，或電力分配系統上的電力。對於任何這樣的實物網絡，進入任何中途結點的流需要等於離開那結點的流。Bollobás 以基爾霍夫電流定律 (Kirchhoff's Current Law) 描繪這限制的特性，同時較遲的作者（即 Chartrand）提及它在某些守恆方程的普遍化。

在生態學中也可找到流網絡的應用：當考慮在食物網中不同組織之間養料及能量的流，流網絡便自然地產生。與這些網絡有聯繋的數學問題和那些液體流或交通流網絡中所產生的難題有很大分別。由 Robert Ulanowicz 及其他人發展的生態系統網絡分析領域包含使用資訊理論及熱力學的概念去研究這些網絡隨時間的演變。

[编辑] 普遍化及專門化

利用網絡流去找出最大流是最簡單及最普通的問題，它提供了在一指定的圖中由源點到匯點的最大可能總流量。還有很多其它問題可以利用最大流演算法去解決，假設它們可以適當地塑造成流網絡的模樣，例如二部圖匹配 (Bipartite Matching)、任務分配問題 (Assignment Problem) 和運輸問題 (Transportation Problem)。

在多物網絡流問題 (Multi-commodity Flow Problem) 中，可以有多個源點和匯點，和各種各樣的由指定源點傳送到指定匯點的「物品 (Commodities)」。例如這可能是不同的工廠生產的各種各樣的貨物經由「同一」運輸網絡運送到不同的消費者手上。

在最少費用流問題 (Minimum Cost Flow Problem) 中，每條邊 $u, v$ 都有特定費用 $k (u, v)$ 。沿這條邊傳送 $f (u, v)$ 的費用是 $f(u,v) \cdot k(u,v)$ 。目標是要用最低的成本由源點傳送一特定數量的流到匯點。

在環流問題 (Circulation Problem) 中，每條邊除了有上限 $c (u, v)$ 外，還有下限 $l (u, v)$ 。每條邊亦有一個費用。很多時，流守恆適用於環流問題中所有結點，由匯點到源點亦有一條連結。這樣便能利用 $l (t, s)$ 和 $c (t, s)$ 支配總流量。這問題因流環繞網絡流動而得名。

在有增益網絡或普遍化網絡中，每條邊都有增益，一個實數（非零）使如果這條邊有一增益 g 而有一流量 x 的流在尾部流入，便有一流量 gx 的流從頭部流出。

[编辑] 參考

Bollobás, Béla (1979). Graph Theory: An Introductory Course，Heidelberg: Springer-Verlag. ISBN 3-540-90399-2.
Chartrand, Gary & Oellermann, Ortrud R. (1993). Applied and Algorithmic Graph Theory，New York: McGraw-Hill. ISBN 0-07-557101-3.
Even, Shimon (1979). Graph Algorithms，Rockville, Maryland: Computer Science Press. ISBN 0-914894-21-8.
Gibbons, Alan (1985). Algorithmic Graph Theory，Cambridge: Cambridge University Press. ISBN 0-521-28881-9 ISBN 0-521-24659-8.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein [1990] (2001). "26"， Introduction to Algorithms，2nd edition, 696-697，MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

[编辑] 關連項目

最大流量等於最小切割定理

[编辑] 外部連接

来自“http://zh.wikipedia.org../../../%E7%BD%91/%E7%BB%9C/%E6%B5%81/%E7%BD%91%E7%BB%9C%E6%B5%81.html”

页面分类: 網絡流 | 图算法 | 图论 | 運算研究

网络流