流网络—最大流问题（Maximum-flow problem）

流网络（Flow Networks）指的是一个有向图 G = (V, E)，其中每条边 (u, v) ∈ E 均有一非负容量 c(u, v) ≥ 0。如果 (u, v) ? E 则可以规定 c(u, v) = 0。流网络中有两个特殊的顶点：源点 s （source）和汇点 t（sink）。为方便起见，假定每个顶点均处于从源点到汇点的某条路径上，就是说，对每个顶点 v ∈ E，存在一条路径 s --> v --> t。因此，图 G 为连通图，且 |E| ≥ |V| - 1。

下图展示了一个流网络实例。

设 G = (V, E) 是一个流网络，其容量函数为 c。设 s 为网络的源点，t 为汇点。G 的流的一个实值函数 f：V×V → R，且满足下列三个性质：

• 容量限制（Capacity Constraint）：对所有顶点对 u, v ∈ V，要求 f(u, v) ≤ c(u, v)。
• 反对称性（Skew Symmetry）：对所有顶点对 u, v ∈ V，要求 f(u, v) = - f(v, u)。
• 流守恒性（Flow Conservation）：对所有顶点对 u ∈ V - {s, t}，要求 Σ_v∈Vf(u, v) = 0。

f(u, v) 称为从顶点 u 到顶点 v 的流，流的值定义为：|f| =Σ_v∈Vf(s, v)，即从源点 s 出发的总流。

最大流问题（Maximum-flow problem）中，给出源点 s 和汇点 t 的流网络 G，希望找出从 s 到 t 的最大值流。

满足流网络的性质的实际上定义了问题的限制：

• 经过边的流不能超过边的容量；
• 除了源点 s 和汇点 t，对于其它所有顶点，流入量与流出量要相等；

上面的图中描述的流网络可简化为下图，其中源点 s = 0，汇点 t = 5。

上图的最大流为 23，流向如下图所示。

Ford-Fulkerson 算法是一种解决最大流的方法。