在圖論 中，網絡流 （英語：Network flow 容量 （Capacity）的有向圖 分配流 ，使一條邊的流量不會超過它的容量。通常在运筹学 中，有向图称为网络。顶点 称为节点 （Node）而边称为弧 （Arc）。一道流必須符合一個結點的進出的流量相同的限制，除非這是一個源點 （Source）──有較多向外的流，或是一個匯點 （Sink）──有較多向內的流。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網絡中遊動的任何事物。
如果带权有限的有向图
G
=
(
V
,
E
)
{\displaystyle G=(V,\,E)}
网络流图 (或容量网络 ):
有且仅有一个结点
s
∈
V
{\displaystyle s\in V}
源点 。
有且仅有一个结点
t
∈
V
{\displaystyle t\in V}
汇点 。
∀
(
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)\}}
容量网络 的一个网络流 。
在容量网络 中满足以下条件的网络流 称为可行流 :
容量限制（Capacity Constraints） :
f
(
u
,
v
)
≤
c
(
u
,
v
)
{\displaystyle f(u,v)\leq c(u,v)}
流守恒（Flow Conservation） : 除非
u
=
s
{\displaystyle u=s}
u
=
t
{\displaystyle u=t}
∑
w
∈
V
f
(
u
,
w
)
=
0
{\displaystyle \sum _{w\in V}f(u,w)=0}
伪流 是一种与可行流 相对的概念，如果一个网络流 只满足容量限制条件，不满足流守恒条件，那么这个网络流就是一个伪流。
边的剩餘容量（Residual Capacity） 简称为残量 ,是
c
f
(
u
,
v
)
=
c
(
u
,
v
)
−
f
(
u
,
v
)
{\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}
由所有边均为其残量的
G
f
(
V
,
E
f
)
{\displaystyle G_{f}(V,E_{f})}
残量网络（Residual Network） 或剩余网络 .它显示可用的容量的多少。留意就算在原网络中由
u
{\displaystyle u}
v
{\displaystyle v}
u
{\displaystyle u}
v
{\displaystyle v}
v
{\displaystyle v}
u
{\displaystyle u}
u
{\displaystyle u}
v
{\displaystyle v}
对于一个网络流图 ，它最大的可行流 即为它的最大流
增广路（Augmenting Path） 是一条路径
(
u
1
,
u
2
,
⋯
,
u
k
)
{\displaystyle (u_{1},u_{2},\cdots ,u_{k})}
u
1
=
s
{\displaystyle u_{1}=s}
u
k
=
t
{\displaystyle u_{k}=t}
c
f
(
u
i
,
u
i
+
1
)
>
0
{\displaystyle c_{f}(u_{i},u_{i+1})>0}
G
f
{\displaystyle G_{f}}
在任意时刻，
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)}
从一个结点
u
{\displaystyle u}
v
{\displaystyle v}
v
{\displaystyle v}
u
{\displaystyle u}
∀
u
,
v
∈
V
,
f
(
u
,
v
)
=
−
f
(
v
,
u
)
{\displaystyle \forall u,v\in V,\;f(u,v)=-f(v,u)}
对于
G
{\displaystyle G}
u
{\displaystyle u}
∀
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}
f
/
c
{\displaystyle f/c}
s
{\displaystyle s}
t
{\displaystyle t}
s
{\displaystyle s}
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}
b
{\displaystyle b}
a
{\displaystyle a}
淨 流。
將一連串的水管繪畫成一個網絡。每條水管有一特定的闊度，因此只可以保持一特定的水流量。當任何水管匯合，流入匯流點的總水量必須等於流出的水量，否則我們會很快地缺水，或者我們會團積水。我們有一個作為源點的入水口，和一個作為匯點的出水口。一道流便是一條由源點到匯點而使從出水口流出的總水量一致的可能路徑。直觀地，一個網絡的總流量是水從出口流出的速率。
流可以适用于交通網絡上的人或材料，或配电系统 上的電力。對於任何這樣的實物網絡，進入任何中途結點的流需要等於離開那个結點的流。这个守恒限制相当于基爾霍夫電流定律 。
在生態學 中也可找到网络流的應用：當考慮在食物網 中不同組織之間養料及能量的流，网络流便自然地產生。與這些網絡有聯繫的數學問題和那些液體流或交通流網絡中所產生的難題有很大分別。由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
