网络最大流最小割定理的Ford-Fulkerson算法正确性证明

理解核心概念

绘制 或想象一个流网络。它由节点和有向边组成。识别两个特殊节点：源点（通常称为 S）和汇点（通常称为 T）。

每条边 (u, v) 有一个容量，记为 c(u, v)，代表这条边能通过的流量上限。一个流 是一个在边上赋值的函数 f(u, v)，代表实际通过的流量。任何流必须满足两个条件：

1. 容量限制：对于任意一条边 (u, v)，流 f(u, v) 不能超过它的容量 c(u, v)，即 0 ≤ f(u, v) ≤ c(u, v)。
2. 流守恒：除了源点和汇点，对于其他任何节点，流入的总流量等于流出的总流量。

定义 流量值 |f|，它等于从源点 S 出发的总流量，或等于流入汇点 T 的总流量。

定义 割。割是将网络节点分为两个不相交集合 S 和 T 的一个划分，其中源点属于 S 集合，汇点属于 T 集合。一个割的容量 c(S, T) 是所有从集合 S 指向集合 T 的边的容量之和。

理解 最大流问题就是找到一个流 f，使其流量值 |f| 达到最大。理解 最小割问题就是找到一个割 (S, T)，使其容量 c(S, T) 达到最小。

最大流最小割定理指出：网络的最大流量值等于其最小割的容量。

描述Ford-Fulkerson算法

Ford-Fulkerson算法是一个通过寻找增广路径来逐步增加流量的迭代过程。其核心思想是：在残量网络中不断寻找从 S 到 T 的路径，并沿此路径增加流量。

1. 初始化 流量。将网络中所有边的流量 f(u, v) 初始化为 0。
2. 构建 残量网络。残量网络 G_f 是基于当前流 f 构造的一个新网络。对于原网络中的每条边 (u, v)：
   • 如果 f(u, v) < c(u, v)，则在残量网络 G_f 中添加一条边 (u, v)，其残量容量 c_f(u, v) = c(u, v) - f(u, v)，代表还能正向增加的流量。
   • 如果 f(u, v) > 0，则在残量网络 G_f 中添加一条反向边 (v, u)，其残量容量 c_f(v, u) = f(u, v)，代表可以回退或抵消的流量。
3. 搜索 在残量网络 G_f 中是否存在一条从 S 到 T 的路径。这样一条路径称为增广路径。
4. 判断。如果找不到任何增广路径，算法终止，当前流 f 即为最大流。
5. 计算 增广路径 P 上所有边的残量容量 c_f(P) 的最小值，记为 Δ = min {c_f(e) | e ∈ P}。Δ 是沿这条路径可以一次性增加的瓶颈流量。
6. 更新 流量。沿增广路径 P 上的每条边增加流量 Δ：
   • 对于路径上的正向边 (u, v)，增加 其流量 f(u, v) += Δ。
   • 对于路径上的反向边 (v, u)（在残量网络中对应原网络中一条 f(v, u) > 0 的边），减少 其流量 f(v, u) -= Δ。这相当于使用反向边的容量来“撤销”部分流量。
7. 返回 步骤 2，用更新后的流 f 重新构建残量网络，并继续寻找下一条增广路径。

证明正确性：弱对偶性

在证明算法找到最大流之前，先证明一个更基础的结论：任意流的值不超过任意割的容量。

证明：
考虑任意一个流 f 和任意一个割 (S, T)。计算 从源点集合 S 流出的净流量。
一方面，根据流守恒，除了源点 S 本身，S 集合内部其他节点的净流量为 0。因此，从 S 流出的总净流量就等于从源点 S 发出的流量，即 |f|。
另一方面，从集合 S 流出的总净流量，可以看作所有从 S 指向 T 的边的流量之和，减去所有从 T 指向 S 的边的流量之和。即：

|f| = ∑_{u∈S, v∈T} f(u, v) - ∑_{u∈T, v∈S} f(u, v)

因为 f(u, v) ≤ c(u, v) 且 f(v, u) ≥ 0，所以有：

|f| ≤ ∑_{u∈S, v∈T} f(u, v) ≤ ∑_{u∈S, v∈T} c(u, v) = c(S, T)

因此，|f| ≤ c(S, T) 对任意流 f 和任意割 (S, T) 成立。这意味着最大流的值一定不超过最小割的容量。

证明正确性：算法终止时找到最小割

现在证明当 Ford-Fulkerson 算法终止时，找到的流 f 是最大流，并且其流量值等于某个割的容量。

设定：假设算法因为找不到增广路径而终止。此时的流为 f*。

1. 构造割 (S*, T*)。

   • 在最终的残量网络 G_{f*} 中，定义 S* 为所有从源点 S 出发可以到达的节点集合（包括 S 自身）。
   • 定义 T* 为所有其他节点，即 T* = V - S*。显然，汇点 T 属于 T*，因为找不到从 S 到 T 的路径。

2. 证明 这个割的容量等于当前流的值。

   • 观察 对于任何一条从 S* 中的点 u 指向 T* 中的点 v 的原始边 (u, v)，在残量网络 G_{f*} 中，正向边 (u, v) 一定不存在。
     • 原因：如果存在正向边 (u, v)，那么 u 可以从 S 到达，并且可以通过边 (u, v) 到达 v，这与 v ∈ T*（不可达）矛盾。
     • 这意味着，在原始网络中，这些边 (u, v) 的流量已满，即 f*(u, v) = c(u, v)。
   • 观察 对于任何一条从 T* 中的点 v 指向 S* 中的点 u 的原始边 (v, u)，在残量网络 G_{f*} 中，反向边 (u, v) 一定不存在。
     • 原因：反向边 (u, v) 存在的前提是 f*(v, u) > 0。如果 f*(v, u) > 0，那么 v 可以通过这条反向边 (u, v) 从 S 到达（因为 u ∈ S*），这与 v ∈ T* 矛盾。
     • 这意味着，这些边 (v, u) 的流量为零，即 f*(v, u) = 0。
   • 计算 流量值 |f*|。
     根据之前的流值计算公式：
     |f*| = ∑_{u∈S*, v∈T*} f*(u, v) - ∑_{u∈T*, v∈S*} f*(v, u)
     由上述两点可知：
     ∑_{u∈S*, v∈T*} f*(u, v) = ∑_{u∈S*, v∈T*} c(u, v)
∑_{u∈T*, v∈S*} f*(v, u) = 0
     因此，|f*| = ∑_{u∈S*, v∈T*} c(u, v) = c(S*, T*)。

3. 得出结论。

   • 根据步骤 2，我们找到了一个割 (S*, T*)，其容量 c(S*, T*) 等于当前流 f* 的值 |f*|。
   • 根据弱对偶性（|f| ≤ c(S, T)），对于任意流 f，都有 |f| ≤ c(S*, T*) = |f*|。
   • 因此，f* 是一个最大流，且最大流的值等于这个最小割 (S*, T*) 的容量。

证明正确性：算法终止性（当容量为整数时）

当所有边的容量都是整数时，Ford-Fulkerson 算法能在有限步内终止。

1. 分析 每次增广。

   • 每次找到一条增广路径，瓶颈流量 Δ 至少是 1（因为容量是整数，残量容量也是整数，最小值 Δ ≥ 1）。
   • 每次增广至少使总流量值 |f| 增加 1。

2. 确定 流量上界。

   • 根据弱对偶性，最大流的值不超过从源点 S 出发的所有边的容量之和，记为 C。
   • C 是一个有限的正整数。

3. 推断 步数。

   • 流量值 |f| 从 0 开始，每次至少增加 1，最大不超过 C。
   • 因此，增广次数（算法的主要循环次数）最多为 C 次。
   • 算法必然在有限步内终止。