流量图的基本概念
设有向图 [math] D = (V, A, C)[/math]
其中[math] C_{ij} \geqslant 0 [/math] 为容量，[math] C_{ij} \in C [/math]，通过弧 [math](V_i, V_j)[/math] 的流的数量称为流量，记作 [math] x_{ij}[/math]，所有弧上流量的集合 [math]{x_{ij}}[/math] 称为网络 [math] D [/math] 的一个流，标注了流量和容量的有向图称为流量图。
- 发点：仅有出弧的点
- 收点：仅有入弧的点
- 中间点：除了发点和收点之外的点，称为中间点
最大流与增广链
对于每一条弧[math]
\begin {cases}
\text {前向弧：找那些还可以增加流量的弧} \\
\text {反向弧：找那些可以减少流量的弧}
\end {cases}
[/math]，注意在改变弧后仍要满足 [math] 0 \leqslant x_{ij} \leqslant C_{ij}[/math]。
若从 [math] V_s [/math] 增加 1 个单位，即 [math]\Delta = 1 [/math]，观察可发现，所有的前向弧上的流量 [math]+1 [/math]，而所有的反向弧上的流量 [math]-1 [/math]。
当我们能够找到一条增广链就说明当前还有优化的空间。换言之，可行流[math]x[/math]是最大流的充分必要条件是：不存在从[math]V_s[/math]到[math]V_t[/math]的关于流[math]x[/math]的一条增广链。
最大流解法——Ford Fulkerson算法
例 1. 某地区的输油网络和现有的输油计划 (初始流) 如图所示，问 (1) 现有的输油量是多少？(2) 输油量是否可以增加，若能增加，请给出最大输油量。
算法思路：
我们对于除发点外的任意一个顶点 [math] V_j [/math] 记作标号 [math](+V_i, \Delta_j)[/math]，在这里用‘[math]+[/math]’表示前向弧，用‘[math]-[/math]’表示反向弧，[math]\Delta_j [/math] 表示改变量，对于发点 [math] V_s [/math] 我们则直接记作 [math](0, +\infty)[/math]，即假定从原点有源源不断的输入。
对于所给的流量图，我们对齐进行如下步骤的标号和调整：
- 给发点 [math] V_s [/math] 标号 [math](0, +\infty)[/math]
- 取一个已标号的点 [math] V_i [/math]，对于 [math] V_i [/math] 一切未标号的邻接点 [math] V_j [/math] 按下列规则处理
- 如果有弧 [math](V_i, V_j) \in A [/math] 且 [math] 0 \leqslant x_{ij} \leqslant C_{ij}[/math]，那么给 [math] V_j [/math] 标号 [math](+V_i, \Delta_j)[/math]，其中增量 [math]\Delta_j = \min \{C_{ij} – x_{ij}, \Delta_i\}[/math]。
- 如果有弧 [math](V_j, V_i) \in A [/math] 且 [math] 0 \leqslant x_{ij} \leqslant C_{ij}[/math]，那么给 [math] V_j [/math] 标号 [math](-V_i, \Delta_j)[/math]，其中增量 [math]\Delta_j = \min \{x_{ij}, \Delta_i\}[/math]。
- 重复步骤 2，直到 [math] V_t [/math] 被标号或标号过程无法进行下去。若 [math] V_t [/math] 被标记，则有一条增广链，转调整过程；
若 [math] V_t [/math] 未被标记，而过程无法进行下去，这时可行流就是最大流。
上述步骤提到的调整过程如下：
设：[math]\Delta_1 = \min\{ C_{ij} – x_{ij}, \Delta_i \mid (V_i, V_j) \in \text {链} u \text {的前向弧} \}[/math]
[math]\Delta_2 = \min\{ x_{ij}, \Delta_i \mid (V_j, V_i) \in \text {链} u \text {的后向弧} \}[/math]
[math]\Delta = \min\{ \Delta_1, \Delta_2 \}[/math]
- 令[math]
x_{ij} =
\begin {cases}
x_{ij} + \Delta, & \text {链} u \text {的前向弧} \\
x_{ij} – \Delta, & \text {链} u \text {的后向弧} \\
x_{ij}, & \text {弧} \notin \text {链} u
\end {cases}
[/math] - 去掉所有标号，回到第一步，对可行流进行重新标号。
对于本题，实际解题步骤如下：
第一轮标号：
此时收点 [math] V_t [/math] 被标号，找到了一条增广链。即可行流 [math] 3 + 2 + 4 = 9 [/math] 不是最大流，可增加的量为 [math]\min (+\infty, 1, 1, 1) = 1 [/math]，增加后的流量为 [math] 9 + 1 = 10 [/math]。不难发现这条增广链上的弧都为前向弧，所以最终会使得该增广链上的每一条弧都 [math]+1 [/math] 。
第二轮标号：
原流量[math] 4 + 2 + 4 = 10 [/math]、最小改变量[math] \min ( +\infty, 1, 1, 1) = 1[/math]、增加后的流量为[math] 10 + 1 = 11 [/math]、又因为前向弧，故每条弧[math] +1 [/math]。
第三轮标号：
原流量 [math] 4 + 3 + 4 = 11 [/math]、最小改变量 [math]\min (+\infty, 1, 1, 1) = 1 [/math]、增加后的流量为 [math] 11 + 1 = 12 [/math]、又因为前向弧，故每条弧 [math]+1 [/math] 。
第四轮标号：
原流量 [math] 4 + 3 + 4 = 12 [/math]、最小改变量 [math]\min (+\infty, 5, 2, 2) = 2 [/math]、增加后的流量为 [math] 12 + 2 = 14 [/math]、又因为前向弧，故每条弧 [math]+2 [/math] 。
最终我们可以得到最大流量图：
