网络流

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

定义

网络流图

如果带权有限的有向图${\displaystyle G=(V,\,E)}$ 满足如下条件，则称之为网络流图(或容量网络):

• 有且仅有一个结点 ${\displaystyle s\in V}$  入度为0.称为源点。
• 有且仅有一个结点 ${\displaystyle t\in V}$  出度为0.称为汇点。
• ${\displaystyle \forall (u,v)\in E\quad \exists c(u,v)\in R^{+}}$ , 称为这条弧的容量。特别地，如果 ${\displaystyle (u,v)\not \in E}$ ，可以假定 ${\displaystyle c(u,v)=0}$ .

净流

通过容量网络中的一条弧 ${\displaystyle (u,v)}$  的流量(或净流)记为 ${\displaystyle f(u,v)}$ .

弧

弧是网络流图中的一条带权边 ${\displaystyle (u,v)\in E}$ .

特殊的弧有：

• 零流弧满足 ${\displaystyle f(u,v)=0}$ .
• 非零流弧满足 ${\displaystyle f(u,v)\not =0}$ .
• 饱和弧满足 ${\displaystyle f(u,v)=c(u,v)}$ .
• 非饱和弧满足 ${\displaystyle f(u,v)<c(u,v)}$ .

网络流

一个流量的集合 ${\displaystyle F=\{f(u,v)\}}$  包含所有弧上的流，则称为这个容量网络的一个网络流。

可行流

在容量网络中满足以下条件的网络流称为可行流:

• 容量限制（Capacity Constraints）: ${\displaystyle f(u,v)\leq c(u,v)}$ .
• 流守恒（Flow Conservation）: 除非 ${\displaystyle u=s}$  或 ${\displaystyle u=t}$ ，否则 ${\displaystyle \sum _{w\in V}f(u,w)=0}$  一结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。

伪流

伪流是一种与可行流相对的概念，如果一个网络流只满足容量限制条件，不满足流守恒条件，那么这个网络流就是一个伪流。

剩餘容量

边的剩餘容量（Residual Capacity）简称为残量,是 ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ .

残量网络

由所有边均为其残量的 ${\displaystyle G_{f}(V,E_{f})}$  称为残量网络（Residual Network）或剩余网络.它显示可用的容量的多少。留意就算在原网络中由 ${\displaystyle u}$  到 ${\displaystyle v}$  没有边，在剩余网络仍可能有由 ${\displaystyle u}$  到 ${\displaystyle v}$  的边。因为相反方向的流抵消，减少由 ${\displaystyle v}$  到 ${\displaystyle u}$  的流等于增加由 ${\displaystyle u}$  到 ${\displaystyle v}$  的流。

最大流

对于一个网络流图，它最大的可行流即为它的最大流。

增广路

增广路（Augmenting Path）是一条路径 ${\displaystyle (u_{1},u_{2},\cdots ,u_{k})}$ ，而 ${\displaystyle u_{1}=s}$ 、${\displaystyle u_{k}=t}$  及 ${\displaystyle c_{f}(u_{i},u_{i+1})>0}$ ，这表示沿这条路径传送更多流是可能的。当且仅当剩余网络 ${\displaystyle G_{f}}$  没有增广路时处于最大流。

性质

在任意时刻，${\displaystyle G}$  的网络流都满足如下性质。

容量限制

通过一条弧的流量不能超过这条弧的容量上限。

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

反对称性

从一个结点 ${\displaystyle u}$  到另一个结点 ${\displaystyle v}$  的净流量一定是从 ${\displaystyle v}$  到 ${\displaystyle u}$  净流量的相反数。

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

流守恒

对于 ${\displaystyle G}$  中任意一个结点 ${\displaystyle u}$ ,如果它既不是源点也不是汇点，那么它到相邻结点的所有流量之和为0.

${\displaystyle \forall u\in V-\{s,t\},\;\sum _{w\in V}f(u,w)\,=0}$ 

例子

 

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

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

 

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

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

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

應用

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

流可以适用于交通網絡上的人或材料，或配电系统上的電力。對於任何這樣的實物網絡，進入任何中途結點的流需要等於離開那个結點的流。这个守恒限制相当于基爾霍夫電流定律。

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

普遍化及專門化

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

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

在最小费用最大流问题（Minimum Cost Flow Problem）中，每條邊${\displaystyle u,v}$ 都有特定費用${\displaystyle k(u,v)}$ 。沿這條邊傳送${\displaystyle f(u,v)}$ 的費用是${\displaystyle f(u,v)\cdot k(u,v)}$ 。目標是要用最低的成本由源點傳送一特定數量的流到匯點。

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

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

参见

• 布雷斯悖论
• 中心性（英语：Centrality）
• 构形理论（英语：Constructal theory）
• Ford–Fulkerson算法
• Dinic算法
• 流量 (计算机联网)（英语：Flow (computer networking)）
• 有根图（英语：Rooted graph）
• 最大流最小割定理
• 定向拟阵（英语：Oriented matroid）
• 最短路问题

延伸阅读

• 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. 

外部链接

• Real graph instances （页面存档备份，存于互联网档案馆）
• Lemon C++ library with several maximum flow and minimum cost circulation algorithms （页面存档备份，存于互联网档案馆）
• QuickGraph （页面存档备份，存于互联网档案馆）, graph data structures and algorithms for .Net

参考资料