網絡流

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

定義

網絡流圖

如果帶權有限的有向圖$G=(V,\,E)$滿足如下條件，則稱之為網絡流圖(或容量網絡):

• 有且僅有一個結點 $s\in V$ 入度為0.稱為源點。
• 有且僅有一個結點 $t\in V$ 出度為0.稱為匯點。
• $\forall (u,v)\in E\quad \exists c(u,v)\in R^{+}$, 稱為這條弧的容量。特別地，如果 $(u,v)\not \in E$，可以假定 $c(u,v)=0$.

淨流

通過容量網絡中的一條弧 $(u,v)$ 的流量(或淨流)記為 $f(u,v)$.

弧

弧是網絡流圖中的一條帶權邊 $(u,v)\in E$.

特殊的弧有：

• 零流弧滿足 $f(u,v)=0$.
• 非零流弧滿足 $f(u,v)\not =0$.
• 飽和弧滿足 $f(u,v)=c(u,v)$.
• 非飽和弧滿足 $f(u,v)<c(u,v)$.

網絡流

一個流量的集合 $F=\{f(u,v)\}$ 包含所有弧上的流，則稱為這個容量網絡的一個網絡流。

可行流

在容量網絡中滿足以下條件的網絡流稱為可行流:

• 容量限制（Capacity Constraints）: $f(u,v)\leq c(u,v)$.
• 流守恆（Flow Conservation）: 除非 $u=s$ 或 $u=t$，否則 $\sum _{w\in V}f(u,w)=0$ 一結點的淨流是零，除了「製造」流的源點和「消耗」流的匯點。

偽流

偽流是一種與可行流相對的概念，如果一個網絡流只滿足容量限制條件，不滿足流守恆條件，那麼這個網絡流就是一個偽流。

剩餘容量

邊的剩餘容量（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},\cdots ,u_{k})$，而 $u_{1}=s$、$u_{k}=t$ 及 $c_{f}(u_{i},u_{i+1})>0$，這表示沿這條路徑傳送更多流是可能的。當且僅當剩餘網絡 $G_{f}$ 沒有增廣路時處於最大流。

性質

在任意時刻，$G$ 的網絡流都滿足如下性質。

容量限制

通過一條弧的流量不能超過這條弧的容量上限。

$\forall u,v\in V,\;f(u,v)\leq c(u,v)$

反對稱性

從一個結點 $u$ 到另一個結點 $v$ 的淨流量一定是從 $v$ 到 $u$ 淨流量的相反數。

$\forall u,v\in V,\;f(u,v)=-f(v,u)$

流守恆

對於 $G$ 中任意一個結點 $u$,如果它既不是源點也不是匯點，那麼它到相鄰結點的所有流量之和為0.

$\forall u\in V-\{s,t\},\;\sum _{w\in V}f(u,w)\,=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單位的流事實上可能存在，但我們只維持淨流。

應用

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

流可以適用於交通網絡上的人或材料，或配電系統上的電力。對於任何這樣的實物網絡，進入任何中途結點的流需要等於離開那個結點的流。這個守恆限制相當於基爾霍夫電流定律。

在生態學中也可找到網絡流的應用：當考慮在食物網中不同組織之間養料及能量的流，網絡流便自然地產生。與這些網絡有聯繫的數學問題和那些液體流或交通流網絡中所產生的難題有很大分別。由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的流從頭部流出。

參見

• 布雷斯悖論
• 中心性
• 構形理論
• Ford–Fulkerson演算法
• Dinic演算法
• 流量 (電腦聯網)
• 有根圖
• 最大流最小割定理
• 定向擬陣
• 最短路問題

延伸閱讀

• George T. Heineman, Gary Pollice, and Stanley Selkow. Chapter 8:Network Flow Algorithms. Algorithms in a Nutshell. Oreilly Media. 2008: 226–250. ISBN 978-0-596-51624-6. 
• Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall. 1993. ISBN 0-13-617549-X. 
• Bollobás, Béla. Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag. 1979. ISBN 3-540-90399-2. 
• Chartrand, Gary & Oellermann, Ortrud R. Applied and Algorithmic Graph Theory. New York: McGraw-Hill. 1993. ISBN 0-07-557101-3. 
• Even, Shimon. Graph Algorithms. Rockville, Maryland: Computer Science Press. 1979. ISBN 0-914894-21-8. 
• Gibbons, Alan. Algorithmic Graph Theory. Cambridge: Cambridge University Press. 1985. ISBN 0-521-28881-9. 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 26. Introduction to Algorithms 2nd. MIT Press and McGraw-Hill. 2001: 696–697 [1990]. ISBN 0-262-03293-7. 

外部連結

• Maximum Flow Problem
• Real graph instances （頁面存檔備份，存於互聯網檔案館）
• Lemon C++ library with several maximum flow and minimum cost circulation algorithms （頁面存檔備份，存於互聯網檔案館）
• QuickGraph （頁面存檔備份，存於互聯網檔案館）, graph data structures and algorithms for .Net