残存网络#

我们可以想象一个输水管道 $(u,v)$，它的容量是 $c(u,v) = 10$ 升/秒。目前，你决定往里灌了 3 升/秒的流 ($f=3$)。现在问：还能不能再多送一点？

如果路径上每条边都还有 剩余容量 (Forward Edge)，那我们就能沿着这条边再推送一些流量

显然，此时管道的剩余容量为 $10 - 3 = 7$ 升/秒。我们可以用 $u \to v$ 的边，权重为 7 来表示。

但是我们在分配流的时候，发现刚才那 3 升水送错了，导致别的地方堵死了。此时可以通过这条反向边，把这 3 升水“推回去”，退还给 $u$，让 $u$ 把水送去别的更有用的路径。此时反向边的 $v \to u$，权重为 3。

这种能够”撤销”之前的错误决定的机制形成的流网络就是 残存网络 (Residual Network) $G_f$。

在残存网络中，边 $(u,v)$ 的值不在是 $f(u,v)/c(u,v)$，而是使用该方向上的 残存容量 (Residual Capacity)，用来表示还能额外传递的流的容量。我们用数学语言来定义它可以得到：

Defination - Residual Capacity

给定流网络 $G$ 和流 $f$，边 $(u,v)$ 的残存容量定义为：

$c_f(u,v) = c(u,v) - f(u,v), (u,v) \in E$

此外，我们还需要添加反向边，用于表示 “撤销” 的能力。

如果 $f(u,v) > 0$，那么反向边 $(v,u)$ 的残存容量是：

$c_f(v,u) = f(u,v)$

1
┌─────────────────────────────────────────────────────────────────┐
2
│                                                                 │
3
│   原图中的一条边:        残存网络中变成:                          │
4
│                                                                 │
5
│        c = 10                    c_f = 10 - 3 = 7               │
6
│   u ──────────▶ v           u ──────────────────▶ v           │
7
│        f = 7                                                    │
8
│                                  c_f = 3 (反向边)               │
9
│                             u ◀────────────────── v            │
10
│                                                                 │
11
│   含义：                                                        │
12
│   • 正向还能再流 3                                               │
13
│   • 反向可以"撤销" 7                                             │
14
│                                                                 │
15
└─────────────────────────────────────────────────────────────────┘

这样重新构造的网络，即 残存网络 (Residual Network) $G_f$ 可以定义为：

Defination - Residual Network

给定流网络 $G = (V, E)$ 和流 $f$，残存网络 $G_f = (V, E_f)$ 定义为：

$E_f = \{(u,v) \in V \times V : c_f(u,v) > 0\}$

残存网络包含所有” 还有容量 “的边（无论是正向剩余还是反向撤销）。

增广#

如下图 (a) 是一个流网络 $G$ 及其流 $f$。(b) 则是该图的残存网络 $G_f$。其中以阴影部分为例子，残存容量 $c_f(s,v_2) = c(s,v_2) - f(s,v_2) = 13 - 8 = 5$，$c_f(v_2,v_3) = f(v_3, v_2) = 4$，$c_f(v_3,t) = 20 - 15 = 5$。对于残存容量为 0 的边则不会画出。

对于一条这样的 $s \to t$ 的路径，如图 (b) 阴影部分：$s \to v_2 \to v_3 \to t$，我们可以最多推送 $\text{min}(c_f(s,v_2), c_f(v_2,v_3), c_f(v_3,t)) = 4$ 的流。

那么对于残存网络 $G_f$，在 $G_f$ 中寻找一条从 $s$ 到 $t$ 的简单路径，这个路径就是 增广路径 (Augmenting Path)。刚才例子中，$s \to v_2 \to v_3 \to t$ 就是一条增广路径 $p$。

我们称在一条增广路径 $p$ 上能够为每条边增加流量的最大值为路径 $p$ 的残存容量，表示为：$c_f(p) = \min\{c_f(u,v):(u,v) \in p\}$

它会被路径 $p$ 上能推送的流的最小值决定。

我们较为规范地定义增广公式：

Defination - Augmentation

若我们有原始流网络 $G$ 中的一个流 $f$，残存网络 $G_f$ 中的一个流 $f'$，定义 $f \uparrow f'$（读作 “f augmented by f prime”）为流 $f'$ 对流 $f$ 的 增广 (Augmentation) 函数：

$$(f \uparrow f')(u,v) = \begin{cases} f(u,v) + f'(u,v) - f'(v,u) & \text{if } (u,v) \in E \\ 0 & \text{otherwise} \end{cases}$$

这个公式看着都吓人，我们可以逐步解析它：

回忆一下，残存网络 $G_f$ 中的边有两种来源：

• 类型 1：正向边 $(u,v)$ 表示 还能再增加多少流，残存容量 $c_f(u,v) = c(u,v) - f(u,v)$ 当 $c(u,v) - f(u,v) > 0$ 时存在。
• 类型 2：反向边 $(v,u)$ 表示 可以撤销多少流，残存容量 $c_f(v,u) = f(u,v)$，当 $f(u,v) > 0$ 时存在。

假设在残存网络 $G_f$ 中，$f'$ 是一个从 $s$ 到 $t$ 的流。对于原图中的边 $(u,v) \in E$：

• $f'(u,v)$ = 在残存网络中，沿正向边 $(u,v)$ 流过的量 → 意味着：我们想 增加 原图中 $(u,v)$ 的流量。
• $f'(v,u)$ = 在残存网络中，沿反向边 $(v,u)$ 流过的量 → 意味着：我们想 撤销 原图中 $(u,v)$ 的流量。

所以增广公式的含义是：$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u)$

1
             原来的流量    增加的量     撤销的量
2
                 │           │           │
3
                 ▼           ▼           ▼
4
新流量 (u,v) = f(u,v)  +  f'(u,v)  -  f'(v,u)

下面是一个例子：

原图 G 中：

1
u ─────────────────▶ v
2
    容量 c(u,v) = 10
3
    当前流 f(u,v) = 7

残存网络 $G_f$ 中：

1
u ─────────────────▶ v      正向边，残存容量 = 10 - 7 = 3
2

3
u ◀───────────────── v      反向边，残存容量 = 7

• 如果我们打算 增加 2 容量的水，$f'(u,v) = 2$，$f'(v,u) = 0$。那么新流量 = $f(u,v) + f'(u,v) - f'(v,u) = 7 + 2 - 0 = 9$。此时 原来流 7，现在多流 2，变成 9。
• 如果我们打算 撤销 3 容量的水，$f'(u,v) = 0$，$f'(v,u) = 3$。那么新流量 = $f(u,v) + f'(u,v) - f'(v,u) = 7 + 0 - 3 = 4$。此时 原来流 7，撤销 3，变成 4。
• 如果我们打算 增加 1 容量的水，同时 撤销 2 容量的水，那么等价于 撤销 1 容量的水，$f'(u,v) = 1$，$f'(v,u) = 2$。那么新流量 = $f(u,v) + f'(u,v) - f'(v,u) = 7 + 1 - 2 = 6$。此时 增加 1，撤销 2，净效果是减少 1。

那么根据我们的定义，可以得到一个重要的引理：

Defination - Augmentation Lemma 1

$f \uparrow f'$ 是图 $G$ 的一个增广流，其值为 $|f \uparrow f'| = |f| + |f'|$

• |f| 的值表示图 $G$ 原本的流的值。
• |f’| 的值表示残存网络 $G_f$ 的流的值。

当我们找到一条增广路径 $p$ 时，实际上是在残存网络中构造了一个特殊的流 $f'$，我们定义为 $f_p$。我们有这样的另一条引理：

Defination - Augmentation Lemma 2

设图 $G_f$ 是图 $G$ 的残存网络，$p$ 为残存网络 $G_f$ 中的一条增广路径，则定义 $f_p$ 是残存网络的一个流：

$$f_p(u,v) = \begin{cases} c_f(p) = \min\{c_f(u,v):(u,v) \in p\} & \text{if } (u,v) \in p \\ 0 & \text{otherwise} \end{cases}$$

其中 $c_f(p)$ 是路径 $p$ 的瓶颈容量。

此时要求其值：$|f_p| = c_f(p) > 0$

我们可以把引理2代入到引理1中得到：

流 $f$ 增加 $f_p$ 的量，将会获得一个新的流 $f \uparrow f_p$，这个流的值更接近于 最大流。

回到我们之前的一个例子中，图 (a) 是一个流网络 $G$，此时 $|f| = 11 + 8 = 19$，图 (b) 则是它的残存网络 $G_f$。我们增加了图 (c) 和图 (d)。

图 (c) 中 $G$ 使用了沿着增广路径 (图 (b) 阴影部分) $p$ 增加而导出的流。我们在之前计算过它的残存容量 $c_f(p) = \text{min}(c_f(s,v_2), c_f(v_2,v_3), c_f(v_3,t)) = 4$，所以此时图 (c) 的流就是一个增广流，其值为：$|f \uparrow f_p| = |f| + |f_p'| = 19 + 4 = 23 = 11 + 12$，$12 = 8 + 4$ 是因为增加了残存容量 $4$，而 $11$ 不变因为没有采用包含它的增广路径。对于没有残存容量的边，例如 $(v_2,v_3)$，图中则不会显示。

我们将此时的图 (c) 重新转换为残存网络可以得到图 (d)。

基本 Ford-Fulkerson 算法#

现在我们可以描述完整的 Ford-Fulkerson 方法了，他的逻辑非常简单：

1. 初始化流量为 0。
2. 循环 (在残留网络 $G_f$ 中存在一条从 $s$ 到 $t$ 的增广路径 $p$)：
   • 找出路径 $p$ 上的瓶颈容量（即路径上最小的剩余容量）。
   • 沿着这条路径增加流量（更新正向流，同时也更新残留网络中的反向边）。
3. 当找不到增广路径时，算法结束，当前流即为最大流。

基本 Ford-Fulkerson 算法使用了 DFS 去查找增广路径，其时间复杂度为 $O(E · |f*|)$，其中 $E$ 是边的数量，$|f*|$ 是最大流的值。

1
FORD-FULKERSON(G, s, t):
2
    初始化所有边的流量 f(u,v) = 0
3

4
    while 残存网络 Gf 中存在 s→t 的路径 P:
5
        // 找瓶颈
6
        Δ = min{ cf(u,v) : (u,v) ∈ P }
7

8
        // 增广
9
        for each edge (u,v) in P:
10
            if (u,v) 是原图中的边:
11
                f(u,v) = f(u,v) + Δ
12
            else:  // (u,v) 是反向边，对应原图的 (v,u)
13
                f(v,u) = f(v,u) - Δ
14

15
        更新残存网络 Gf
16

17
    return f

我们通过一个例子来模拟一次这个过程：假设有如下的流网络图 $G$

1
        s
2
       / \
3
     10   10
4
     /     \
5
    ▼       ▼
6
    a ─────► b
7
    |   1    |
8
     \      /
9
     10    10
10
       \  /
11
        ▼
12
        t

1. 初始状态，所有边的流量初始化为 0：当前流 $|f| = 0$。它的残存网络和原图一样。

2. 第一次增广，假设选择了增广路径为：$s → a → b → t$。瓶颈值 $Δ = min(10, 1, 10) = 1$。我们更新网络：

   • $f(s,a) = 1$
   • $f(a,b) = 1$
   • $f(b,t) = 1$

   此时流量是 $|f| = 1$。

   图 $G$:

   1
        s
   2
       / \
   3
    1/10 0/10
   4
     /     \
   5
    ▼       ▼
   6
    a ─────► b
   7
    |  1/1   |
   8
     \      /
   9
    0/10  1/10
   10
       \  /
   11
        ▼
   12
        t
   

   残存图 $G_f$:

   1
        ——> s
   2
        |  / \
   3
      1 | 9   10
   4
        |/     \
   5
        ▼       ▼
   6
        a ◄────  b
   7
        |   1    |
   8
         \      /↑
   9
         10    9 |
   10
           \  /  | 1
   11
            ▼    |
   12
            t ———|
   

3. 第二次增广，假设选择了增广路径为：$s → b → t$。瓶颈值 $Δ = min(10, 9) = 9$。我们更新网络：

   • $f(s,b) = 9$
   • $f(b,t) = 1 + 9 = 10$

   此时流量是 $|f| = 1 + 9 = 10$。

   图 $G$:

   1
        s
   2
       / \
   3
    1/10 9/10
   4
     /     \
   5
    ▼       ▼
   6
    a ─────► b
   7
    |  1/1   |
   8
     \      /
   9
    0/10 10/10
   10
       \  /
   11
        ▼
   12
        t
   

   残存图 $G_f$:

   1
        ——> s <——
   2
        |  / \  |
   3
      1 | 9   1 | 9
   4
        |/     \|
   5
        ▼       ▼
   6
        a ◄────  b
   7
        |   1    ↑
   8
         \       |
   9
         10      | 10
   10
           \     |
   11
            ▼    |
   12
            t ———|
   

4. 第三次增广，假设选择了增广路径为：$s → a → t$。瓶颈值 $Δ = min(9, 10) = 9$。我们更新网络：

   • $f(s,a) = 1 + 9 = 10$
   • $f(a,t) = 9$

   此时流量是 $|f| = 10 + 9 = 19$。

   图 $G$:

   1
        s
   2
       / \
   3
    10/10 9/10
   4
     /     \
   5
    ▼       ▼
   6
    a ─────► b
   7
    |  1/1   |
   8
     \      /
   9
    9/10 10/10
   10
       \  /
   11
        ▼
   12
        t
   

   残存图 $G_f$:

   1
        ——> s <——
   2
        |    \  |
   3
     10 |     1 | 9
   4
        |      \|
   5
        |       ▼
   6
        a ◄────  b
   7
        |    1   ↑
   8
        ↑\       |
   9
     9  | 1      | 10
   10
        |  \     |
   11
        |   ▼    |
   12
        |—— t ———|
   

5. 第四次增广，假设选择了增广路径为：$s → b → a → t$ （注意：增广路径是残存图中的，而不是原图中的）。瓶颈值 $Δ = min(1, 1, 1) = 1$。我们更新网络：

   • $f(s,b) = 9 + 1 = 10$
   • $f(a,b) = 1 - 1 = 0$: 注意，这里走了一个反向边，所以是减 1，意味着”撤回”之前 $a → b$ 的流量。
   • $f(a,t) = 9 + 1 = 10$

   当前流量 $|f| = 19 + 1 = 20$

   图 $G$:

   1
        s
   2
       / \
   3
    10/10 10/10
   4
     /     \
   5
    ▼       ▼
   6
    a ─────► b
   7
    |  0/1   |
   8
     \      /
   9
   10/10 10/10
   10
       \  /
   11
        ▼
   12
        t
   

   残存图 $G_f$:

   1
        ——> s <———
   2
        |        |
   3
     10 |        | 10
   4
        |        |
   5
        |        |
   6
        a ────►  b
   7
        ↑   1    ↑
   8
        |        |
   9
     10 |        | 10
   10
        |        |
   11
        |        |
   12
        |—— t ———|
   

通过这个过程可以看出，反向边 = “后悔药” = “重新分配的机会”。当你走反向边 $(v,u)$ 时，实际含义是：我决定少用一点 $(u,v)$ 这条边，把配额让给更好的路径。

割与最大流最小割定理#

我们已经了解了 Ford-Fulkerson 方法的过程了，但是它有一个很明显的缺陷：最后找的最大流是真的最大流吗？我们目前还不知道，接下来就需要引入割的概念。

从一个幽默的例子开始吧：假设你是敌方间谍 🕵️，想要切断城市的供水，你需要 最少 切断多大容量的管道，使得水厂的水完全无法到达城市？

我们称这样的问题是 最小割 (Min-cut) 问题。

在图论里，割 (Cut) 就是一种把图一分为二的分类法。我们同样通过数学语言进行定义：

Defination - Cut

流网络 $G = (V, E)$ 的一个割 $(S, T)$ 是对顶点集 $V$ 的一个划分，满足：

• $s \in S$（源点在 $S$ 中）
• $t \in T$（汇点在 $T$ 中）
• $S \cup T = V$ 且 $S \cap T = \emptyset$

你可以想象，拿出一把红色的剪刀，在纸上的流网络图中间随意画一条线，把 $s$ 和 $t$ 彻底隔开。这条线切断的所有管道，就是这个“割”所涉及的边。

如下图是一个割的例子，它将图分成了：$S = \{s, v_1, v_2\},\ T =\{v_3, v_4, t\}$

对于同一个割 $(S, T)$，有两个不同的度量标准：

Defination - Cut Capacity and Flow

1. 割 $(S, T)$ 的容量定义为所有 从 $S$ 到 $T$ 的边 的容量之和：

   $c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v)$

   这是瓶颈的理论上限。注意：它 只计算从 $S$ 指向 $T$ 的边的容量之和。

2. 给定流 $f$，跨越割 $(S, T)$ 的净流量定义为：

   $f(S, T) = \sum_{u \in S} \sum_{v \in T} f(u, v) - \sum_{u \in S} \sum_{v \in T} f(v, u)$

   它表示当前流的状态，数值上 (等于从 $S$ 流向 $T$ 的实际流量) 减去 (从 $T$ 流回 $S$ 的实际流量)。

我们之前提到的图片中，割的容量 $c(S,T) = c(v_1,v_3) + c(v_2,v_4) = 12 + 14 = 26$

对于当前割，它的净流量 $f(S,T) = f(v_1,v_3) + f(v_2,v_4) - f(v_3,v_2) = (12 + 11) - 4 = 19$

我们发现了一个巧合：$f$ 是图 $G$ 的一个流，$|f| = 11 + 8 = 19$，对于当前割，它的净流量 $f(S,T) = |f| = 19$。这其实是对任意割都成立的，我们有这样的引理：

Defination - Cut Lemma 1

对于任意流 $f$ 和任意割 $(S, T)$：

$f(S, T) = |f|$

这现象第一眼感觉很反直觉，但是仔细想想确实如此。想象一条宽阔的河流（流网络）。

• 你在源头测流速，是 100。
• 你在中游随便找个截面切一刀（割），测流过截面的净水量，肯定也是 100。
• 你在入海口测，还是 100。

无论你怎么切这一刀（哪怕切得很歪，绕来绕去），只要把 $s$ 和 $t$ 分开了，流过这条线的净流量永远守恒，等于总流量。

此外，我们再考虑一下流的限制问题，很容易得到：对于任意割，实际流过去的量（净流量），不可能超过这个割原本的物理容量。这是我们的第二个引理。

Defination - Cut Lemma 2

对于任意流 $f$ 和任意割 $(S, T)$：

$f(S, T) = |f| \leq c(S, T)$

那既然总流量不能超过任意一个割的容量，那它肯定也不能超过容量最小的那个割（最小割）。

Ford-Fulkerson 算法结束时，意味着在残存网络 $G_f$ 中，已经找不到从 $s$ 到 $t$ 的路了。

此时，我们来构造一个特殊的割 $(S, T)$：

• 集合 $S$：在残存网络 $G_f$ 中，从 $s$ 出发能走到的所有节点。
• 集合 $T$：在残存网络 $G_f$ 中，从 $s$ 出发走不到的所有节点。（$t$ 肯定在这里，因为如果能走到 $t$，算法就不该结束）

在这个特殊割 $(S, T)$ 上：

1. 对于所有 $S \to T$ 的正向边 $(u, v)$：在残存网络里断了（不能走，因为能走的话会归到 $S$ 里）。这意味着 $c_f(u, v) = c(u, v) - f(u, v) = 0$。$f(u, v) = c(u, v)$。 所有正向边都满载了！
2. 对于所有 $T \to S$ 的反向边 $(v, u)$：在残存网络里也没有边（不能倒着流回来，否则 $v$ 就在 $S$ 里了）。这意味着 $f(v, u) = 0$。 所有反向边都是空的！

在这个特殊的割上：

所以，当 Ford-Fulkerson 结束时，我们找到了一个流和一个割，它们的数值相等。

因为割的引理2告诉我们，流 $\le$ 容量：对于任意割，实际流过去的量（净流量），不可能超过这个割原本的物理容量。即 $|f| \le c(S, T)$。

既然在这个点上流碰到了割的天花板，流不可能更大了（这就是最大流），割也不可能更小了（这就是最小割）。

所以我们可以得出一个结论：一个网络的最大流量，等于该网络最小割的容量。

我们将这个过程用数学语言写出来，就成为了 最大流最小割定理 (Max-Flow Min-Cut Theorem)。

Defination - Max-Flow Min-Cut Theorem

设 $f$ 是流网络 $G = (V, E)$ 中的一个流，源点为 $s$，汇点为 $t$。 以下三个条件等价：

1. $f$ 是 $G$ 的一个最大流
2. 残存网络 $G_f$ 中不存在增广路径
3. 存在某个割 $(S, T)$，使得 $|f| = c(S, T)$

其实这三个条件就是 Ford-Fulkerson 方法结束时的情况。

我们通过一个例子去验证这个结论对不对，下面是一个流网络执行 Ford-Fulkerson 方法到最后一步时的流网络图 $G$。

我们来验证它是否是最小割：

1. 我们将其转换为残存网络：

   1
                   10 (<)
   2
        ———> a <——————————————> b
   3
        |   /    ↖  2 (>) ↗    ↖  7
   4
     5  | ↙  10   \     /         \
   5
        s    5 (↖)  \ /   3 (↗)    t
   6
         ↖          / \           ↗  3 (↗)
   7
      4    \      7 (<)   7 (↙) ↙
   8
            c  <——————————————> d
   9
                  3 (>)
   

   边	流
   $a \to s$	10
   $s \to a$	5
   $a \to b$	2
   $b \to a$	10
   $c \to s$	4
   $c \to b$	3
   $c \to d$	3
   $d \to a$	5
   $d \to c$	7
   $d \to t$	3
   $t \to b$	7
   $t \to d$	7

2. 我们构建特殊的割：$S = \{s, a, b\}$, $T = \{c, d, t\}$。

3. 计算特殊割的残存容量，它是原图中所有 $S$ 到 $T$ 边的容量：$c(S,T) = c(s,c) + c(b,t) + c(b,c) = 4 + 7 + 3 = 14$

4. 比较当前流的值是否等于割的容量：$|f| = 10 + 4 = 14 = c(S,T)$。所以当前割是最小割，当前流是最大流。

并且此时我们发现，割的净流量 $f(S,T) = f(s,c) + f(b,t) + f(b,c) - f(d,a) = 4 + 7 + 3 - 0 = 14 = c(S,T)$，$S \to T$ 的边都是满的，$T \to S$ 都是空的。