查看“︁网络流”︁的源代码

{{Unreferenced|time=2020-10-22T13:02:27+00:00}}
{{TA
|G1=IT
|G2=Math
}}
在[[圖論]]中，'''網絡流'''（{{lang-en|'''Network flow'''}}）是指在一個每條邊都有'''容量'''（Capacity）的[[圖#有/無向圖|有向圖]]分配'''流'''，使一條邊的流量不會超過它的容量。通常在[[运筹学]]中，有向图称为网络。[[顶点 (图论)|顶点]]称为'''节点'''（Node）而边称为'''弧'''（Arc）。一道流必須符合一個結點的進出的流量相同的限制，除非這是一個'''源點'''（Source）──有較多向外的流，或是一個'''匯點'''（Sink）──有較多向內的流。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網絡中遊動的任何事物。

== 定义 ==

=== 网络流图 ===
如果带权有限的[[有向图]]<math>G=(V,\,E)</math>满足如下条件，则称之为'''网络流图'''(或'''容量网络'''):

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

=== 净流 ===
通过容量网络中的一条弧 <math>(u,v)</math> 的'''流量'''(或'''净流''')记为 <math>f(u,v)</math>.

=== 弧 ===
'''弧'''是网络流图中的一条带权边 <math>(u,v)\in E</math>.

特殊的弧有：
* '''零流弧'''满足 <math>f(u,v)=0</math>.
* '''非零流弧'''满足 <math>f(u,v)\not=0</math>.
* '''饱和弧'''满足 <math>f(u,v)=c(u,v)</math>.
* '''非饱和弧'''满足 <math>f(u,v)<c(u,v)</math>.

=== 网络流 ===
一个[[#流量|流量]]的集合 <math>F=\{f(u,v)\}</math> 包含所有弧上的流，则称为这个[[#网络流图|容量网络]]的一个'''网络流'''。

=== 可行流 ===
在[[#网络流图|容量网络]]中满足以下条件的[[#网络流|网络流]]称为'''可行流''':

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

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

=== 剩餘容量 ===
边的'''剩餘容量（Residual Capacity）'''简称为'''残量''',是 <math>c_f(u,v)=c(u,v)-f(u,v)</math>.

=== 残量网络 ===
由所有边均为其残量的 <math>G_f(V,E_f)</math> 称为'''残量网络（Residual Network）'''或'''剩余网络'''.它显示可用的容量的多少。留意就算在原网络中由 <math>u</math> 到 <math>v</math> 没有边，在剩余网络仍可能有由 <math>u</math> 到 <math>v</math> 的边。因为相反方向的流抵消，减少由 <math>v</math> 到 <math>u</math> 的流等于增加由 <math>u</math> 到 <math>v</math> 的流。

=== 最大流 ===
对于一个[[#网络流图|网络流图]]，它最大的[[#可行流|可行流]]即为它的'''[[最大流]]'''。

=== 增广路 ===
'''增广路（Augmenting Path）'''是一条路径 <math>(u_1, u_2, \cdots, u_k)</math>，而 <math>u_1 = s</math>、<math>u_k = t</math> 及 <math>c_f(u_i, u_{i+1}) > 0</math>，这表示沿这条路径传送更多流是可能的。当且仅当剩余网络 <math>G_f</math> 没有增广路时处于最大流。

== 性质 ==

在任意时刻，<math>G</math> 的网络流都满足如下性质。

=== 容量限制 === 

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

<math>\forall u,v\in V,\;f(u,v)\leq c(u,v)</math>

=== 反对称性 ===

从一个结点 <math>u</math> 到另一个结点 <math>v</math> 的净流量一定是从 <math>v</math> 到 <math>u</math> 净流量的相反数。

<math>\forall u,v\in V,\;f(u,v)=-f(v,u)</math>

=== 流守恒 ===

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

<math>\forall u\in V-\{s,t\},\;\sum_{w\in V}f(u,w)\,=0</math>


==例子==

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

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

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

==應用==

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

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

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

===普遍化及專門化===

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

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

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

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

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

==参见==
* [[布雷斯悖论]]
* {{le|中心性|Centrality}}
* {{le|构形理论|Constructal theory}}
* [[Ford–Fulkerson算法]]
* [[Dinic算法]]
* {{le|流量 (计算机联网)|Flow (computer networking)}}
* {{le|有根图|Rooted graph}}
* [[最大流最小割定理]]
* {{le|定向拟阵|Oriented matroid}}
* [[最短路问题]]

==延伸阅读==
* {{cite book | author=George T. Heineman, Gary Pollice, and Stanley Selkow | title= Algorithms in a Nutshell | publisher=[[歐萊禮|Oreilly Media]] | year=2008 | chapter=Chapter 8:Network Flow Algorithms | pages = 226–250 | isbn=978-0-596-51624-6 }}
* {{cite book | author=[[Ravindra K. Ahuja]], [[Thomas L. Magnanti]], and [[James B. Orlin]] | title= Network Flows: Theory, Algorithms and Applications | url=https://archive.org/details/networkflowstheo0000ahuj | publisher=Prentice Hall | year=1993 | isbn=0-13-617549-X }}
* {{cite book | author=[[Béla Bollobás|Bollobás, Béla]] | title= Graph Theory: An Introductory Course | location=Heidelberg | publisher=Springer-Verlag | year=1979 | isbn=3-540-90399-2}}
* {{cite book | author=[[Gary Theodore Chartrand|Chartrand, Gary]] & Oellermann, Ortrud R. | title=Applied and Algorithmic Graph Theory | location=New York | publisher=McGraw-Hill | year=1993 | isbn=0-07-557101-3}}
* {{cite book | author=Even, Shimon | title=Graph Algorithms | url=https://archive.org/details/graphalgorithms0000even | location=Rockville, Maryland | publisher=Computer Science Press | year=1979 | isbn=0-914894-21-8}}
* {{cite book | author=Gibbons, Alan | title=Algorithmic Graph Theory | url=https://archive.org/details/algorithmicgraph0000gibb | location=Cambridge | publisher=Cambridge University Press | year=1985 | isbn=0-521-28881-9 }}
* {{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[罗纳德·李维斯特|Ronald L. Rivest]], and [[Clifford Stein]] | title = [[算法导论|Introduction to Algorithms]] | origyear = 1990 | edition = 2nd | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 696–697 | chapter = 26 | isbn = 0-262-03293-7}}

==外部链接==
* [https://web.archive.org/web/20080111234829/http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/Maxflow.shtml Maximum Flow Problem]
* [http://www.dis.uniroma1.it/~challenge9/download.shtml Real graph instances] {{Wayback|url=http://www.dis.uniroma1.it/~challenge9/download.shtml |date=20120213151113 }}
* [http://lemon.cs.elte.hu/ Lemon C++ library with several maximum flow and minimum cost circulation algorithms] {{Wayback|url=http://lemon.cs.elte.hu/ |date=20051025011207 }}
* [http://quickgraph.codeplex.com/ QuickGraph] {{Wayback|url=http://quickgraph.codeplex.com/ |date=20180121140629 }}, graph data structures and algorithms for .Net

== 参考资料 ==
{{reflist}}

[[Category:網絡流]]
[[Category:圖演算法]]
[[Category:圖論]]
[[Category:運籌學]]