网络流

如果带权有限的有向图${\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 \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}$

利用網絡流去找出最大流是最簡單及最普通的問題，它提供了在一指定的圖中由源點到匯點的最大可能總流量。還有很多其它問題可以利用最大流演算法去解決，假設它們可以適當地塑造成流網絡的模樣，例如二分图匹配（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的流從頭部流出。