在圖論 中,網絡流 (英語:Network flow )是指在一個每條邊都有容量 (Capacity)的有向圖 分配流 ,使一條邊的流量不會超過它的容量。通常在運籌學 中,有向圖稱為網絡。頂點 稱為節點 (Node)而邊稱為弧 (Arc)。一道流必須符合一個結點的進出的流量相同的限制,除非這是一個源點 (Source)──有較多向外的流,或是一個匯點 (Sink)──有較多向內的流。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網絡中遊動的任何事物。
此條目
沒有列出任何參考或來源 。
(2020年10月22日 )
如果帶權有限的有向圖
G
=
(
V
,
E
)
{\displaystyle G=(V,\,E)}
滿足如下條件,則稱之為網絡流圖 (或容量網絡 ):
有且僅有一個結點
s
∈
V
{\displaystyle s\in V}
入度為0.稱為源點 。
有且僅有一個結點
t
∈
V
{\displaystyle t\in V}
出度為0.稱為匯點 。
∀
(
u
,
v
)
∈
E
∃
c
(
u
,
v
)
∈
R
+
{\displaystyle \forall (u,v)\in E\quad \exists c(u,v)\in R^{+}}
, 稱為這條弧的容量。特別地,如果
(
u
,
v
)
∉
E
{\displaystyle (u,v)\not \in E}
,可以假定
c
(
u
,
v
)
=
0
{\displaystyle c(u,v)=0}
.
通過容量網絡中的一條弧
(
u
,
v
)
{\displaystyle (u,v)}
的流量 (或淨流 )記為
f
(
u
,
v
)
{\displaystyle f(u,v)}
.
弧 是網絡流圖中的一條帶權邊
(
u
,
v
)
∈
E
{\displaystyle (u,v)\in E}
.
特殊的弧有:
零流弧 滿足
f
(
u
,
v
)
=
0
{\displaystyle f(u,v)=0}
.
非零流弧 滿足
f
(
u
,
v
)
≠
0
{\displaystyle f(u,v)\not =0}
.
飽和弧 滿足
f
(
u
,
v
)
=
c
(
u
,
v
)
{\displaystyle f(u,v)=c(u,v)}
.
非飽和弧 滿足
f
(
u
,
v
)
<
c
(
u
,
v
)
{\displaystyle f(u,v)<c(u,v)}
.
一個流量 的集合
F
=
{
f
(
u
,
v
)
}
{\displaystyle F=\{f(u,v)\}}
包含所有弧上的流,則稱為這個容量網絡 的一個網絡流 。
偽流 是一種與可行流 相對的概念,如果一個網絡流 只滿足容量限制條件,不滿足流守恆條件,那麼這個網絡流就是一個偽流。
邊的剩餘容量(Residual Capacity) 簡稱為殘量 ,是
c
f
(
u
,
v
)
=
c
(
u
,
v
)
−
f
(
u
,
v
)
{\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}
.
在任意時刻,
G
{\displaystyle G}
的網絡流都滿足如下性質。
通過一條弧的流量不能超過這條弧的容量上限。
∀
u
,
v
∈
V
,
f
(
u
,
v
)
≤
c
(
u
,
v
)
{\displaystyle \forall u,v\in V,\;f(u,v)\leq c(u,v)}
對於
G
{\displaystyle G}
中任意一個結點
u
{\displaystyle u}
,如果它既不是源點也不是匯點,那麼它到相鄰結點的所有流量之和為0.
∀
u
∈
V
−
{
s
,
t
}
,
∑
w
∈
V
f
(
u
,
w
)
=
0
{\displaystyle \forall u\in V-\{s,t\},\;\sum _{w\in V}f(u,w)\,=0}
一個顯示了流及容量的流網絡。
在右邊可以看到一個有以
s
{\displaystyle s}
標示的源點、以
t
{\displaystyle t}
標示的匯點及4個額外結點的流網絡。流及容量以
f
/
c
{\displaystyle f/c}
顯示。注意網絡怎樣保證斜對稱、容量限制及流守恆。由
s
{\displaystyle s}
到
t
{\displaystyle t}
的總流量為5,由此可簡單地觀察到源於
s
{\displaystyle s}
的所有向外流是5,也就是匯於
t
{\displaystyle t}
的向內流。我們知道在其它結點中沒有任何流出現或消失。
上面的流網絡的剩餘網絡,顯示了剩餘容量。
在下面你可以看到對既定的流的剩餘網絡。注意某些邊的剩餘容量是正數而原來的容量是零,如邊
(
d
,
c
)
{\displaystyle (d,c)}
。這道流不是一道最大流 。沿路徑
(
s
,
a
,
c
,
t
)
{\displaystyle (s,a,c,t)}
、
(
s
,
a
,
b
,
d
,
t
)
{\displaystyle (s,a,b,d,t)}
及
(
s
,
a
,
b
,
d
,
c
,
t
)
{\displaystyle (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
{\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}
。注意擴張路徑
(
s
,
a
,
b
,
d
,
c
,
t
)
{\displaystyle (s,a,b,d,c,t)}
在原來的網絡中並不存在,但你可以沿它傳送流,因此仍是一道正當的流。
假如這是一個真實的網絡,由
a
{\displaystyle a}
到
b
{\displaystyle b}
的2單位的流及由
b
{\displaystyle b}
到
a
{\displaystyle a}
的1單位的流事實上可能存在,但我們只維持淨 流。
將一連串的水管繪畫成一個網絡。每條水管有一特定的闊度,因此只可以保持一特定的水流量。當任何水管匯合,流入匯流點的總水量必須等於流出的水量,否則我們會很快地缺水,或者我們會團積水。我們有一個作為源點的入水口,和一個作為匯點的出水口。一道流便是一條由源點到匯點而使從出水口流出的總水量一致的可能路徑。直觀地,一個網絡的總流量是水從出口流出的速率。
流可以適用於交通網絡上的人或材料,或配電系統 上的電力。對於任何這樣的實物網絡,進入任何中途結點的流需要等於離開那個結點的流。這個守恆限制相當於基爾霍夫電流定律 。
在生態學 中也可找到網絡流的應用:當考慮在食物網 中不同組織之間養料及能量的流,網絡流便自然地產生。與這些網絡有聯繫的數學問題和那些液體流或交通流網絡中所產生的難題有很大分別。由Robert Ulanowicz 及其他人發展的生態系統網絡分析領域包含使用資訊理論 及熱力學 的概念去研究這些網絡隨時間的演變。
利用網絡流去找出最大流 是最簡單及最普通的問題,它提供了在一指定的圖中由源點到匯點的最大可能總流量。還有很多其它問題可以利用最大流演算法去解決,假設它們可以適當地塑造成流網絡的模樣,例如二分圖匹配 (Bipartite Matching)、任務分配問題 (Assignment Problem)和運輸問題 (Transportation Problem)。
在多物網絡流問題 (Multi-commodity Flow Problem)中,可以有多個源點和匯點,和各種各樣的由指定源點傳送到指定匯點的「物品(Commodities)」。例如這可能是不同的工廠生產的各種各樣的貨物經由「同一」運輸網絡運送到不同的消費者手上。
在最小費用最大流問題 (Minimum Cost Flow Problem)中,每條邊
u
,
v
{\displaystyle u,v}
都有特定費用
k
(
u
,
v
)
{\displaystyle k(u,v)}
。沿這條邊傳送
f
(
u
,
v
)
{\displaystyle f(u,v)}
的費用是
f
(
u
,
v
)
⋅
k
(
u
,
v
)
{\displaystyle f(u,v)\cdot k(u,v)}
。目標是要用最低的成本由源點傳送一特定數量的流到匯點。
在環流問題 (Circulation Problem)中,每條邊除了有上限
c
(
u
,
v
)
{\displaystyle c(u,v)}
外,還有下限
l
(
u
,
v
)
{\displaystyle l(u,v)}
。每條邊亦有一個費用。很多時,流守恆適用於環流問題中所有 結點,由匯點到源點亦有一條連結。這樣便能利用
l
(
t
,
s
)
{\displaystyle l(t,s)}
和
c
(
t
,
s
)
{\displaystyle c(t,s)}
支配總流量。這問題因流環繞網絡流動而得名。
在有增益網絡 或普遍化網絡 中,每條邊都有增益 ,一個實數(非零)使如果這條邊有一增益g 而有一流量x 的流在尾部流入,便有一流量gx 的流從頭部流出。
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 .