网络流#

源汇点#

在有向图 $G = (V, E)$ 中，钦定 $s \in V$ 和 $t \in V$ 分别作为源点和汇点，$s \ne t$．

对于 $V$ 的划分 $\{S, T\}$，若 $s \in S$ 且 $t \in T$，则称 $\{S, T\}$ 为 $G$ 的 $s$-$t$ 割．

容量#

函数 $c: V^2 \rightarrow \R$ 满足

• $\forall\, (u, v) \in V^2$，$c(u, v) \ge 0$，当且仅当 $(u, v) \notin E$ 时，等号成立．

此时称 $c$ 为容量．

流#

对于函数 $f: V^2 \rightarrow \R$，以下是一些记号：

1. $u$ 的净流量 $f(u) = \sum_{v \in V \setminus \{u\}} f(u, v)$．
2. $U$ 的净流量 $f(U) = \sum_{u \in U}\sum_{v \in V \setminus U} f(u, v)$．

若 $f$ 满足

1. (流动无损耗) $\forall\, (u, v) \in V^2$，$f(u, v) + f(v, u) = 0$．
2. (流动有限制) $\forall\, (u, v) \in V^2$，$f(u, v) \le c(x, y)$．
3. (流不可存储) $\forall\, u \in V \setminus \{s, t\}$，$f(u) = 0$．
4. (源汇点) $f(s) = -f(t) = |f| > 0$．

则称 $f$ 为流，$|f|$ 为总流量．

TIP

$f(u, v)$ 表示 $v$ 从 $u$ 接受的流．容量非负，但流可负．

容易看出，点集的总净流量等于各点净流量之和．

$$\begin{aligned} \sum_{u \in U} f(u) &= \sum_{u \in U}\sum_{w \in V \setminus \{u\}} f(u, w) \\ &= \sum_{u \in U}\sum_{v \in V \setminus U} f(u, v) + \sum_{u \in U}\sum_{v \in U \setminus \{u\}} f(u, v) \\ &= \sum_{u \in U}\sum_{v \in V \setminus U} f(u, v) = f(U) \end{aligned}$$

对于 $s$-$t$ 割，由于流不可存储，可见

$$f(S) = \sum_{u \in S} f(u) = f(s) = |f|$$

对于 $s$-$t$ 割，记

1. 容量 $c(S, T) = \sum_{u \in S}\sum_{v \in T} c(u, v)$．
2. 流量 $f(S, T) = \sum_{u \in S}\sum_{v \in T} f(u, v)$．

显然 $f(S, T) = f(S) = |f|$，容易得到且更重要的是：任给一个 $s$-$t$ 割，都有

IMPORTANT

这说明：受容量函数影响，总流量存在上界．很显然，由于 $s$-$t$ 割法有限，右式存在最小值，即最小割的容量．问题来了：等号能否成立？换句话说，最大流的流量是否等于最小割的容量？

由于所有流的流量都不会超过所有割的容量，我们只需寻找一个流量能够等于一个割的容量（不必证明是最小割）的流．

TIP

这相当于给你两个实数闭区间 $A$ 和 $B$．已知 $A \le B$，那么只需要 $\exists\, a \in A$，满足 $a \in B$，我们便能得知 $\max A = \min B$，因为 $\forall\, a \in A$，$\nexists\, b \in B$，$b < a$．

残量网络#

称函数 $c_f = c - f$ 为剩余容量，记 $c_f(S, T) = \sum_{u \in S}\sum_{v \in T} c_f(u, v)$．

当 $c_f(u, v) = 0$ 时，我们称 $(u, v)$ 满流；当 $f(u, v) = 0$ 时，我们称 $(u, v)$ 空流．

TIP

$\forall\, (u, v) \in V^2, c_f(u, v) = c(u, v) - f(u, v) \ge 0$，即剩余容量非负．

我们根据原图 $G$ 构建新图 $G_f = (V, E_f)$，其中 $E_f = \{(u, v) | c_f(u, v) > 0\}$，称 $G_f$ 为残量网络．

Ford–Fulkerson 增广#

在 $G_f$ 中，我们称起点为 $s$、终点为 $t$ 的迹 $P \subset E_f$，为 $G_f$ 的增广路．

IMPORTANT

1. 途径 (walk)：途径是边列 $((v_0, v_1), (v_1, v_2), \cdots)$，点和边都有可能相同．
2. 迹 (trail)：迹是边互不相同的途径．回路 (circuit) 是起点和终点相同的迹．
3. 路径 (path)：路径是点互不相同的迹．圈 (cycle) 是除了起点和终点以外，点互不相同的路径．自环 (loop) 是两个端点相同的边．

取当前的残量网络 $G_f$ 中的一条增广路 $P$，构建新流 $f': V^2 \rightarrow \R$，满足

从而构建出新的残量网络 $G_{f'}$，这个过程称为增广．

1. 我们发现，由于 $P \subset E_f$，总有 $f'(u, v) > f(u, v)$．
2. 记 $C = \min_{(u, v) \in P} c_f(u, v)$，我们发现 $c_f'(u, v) = c_f(u, v) - C$，$c_f'(v, u) = c_f(v, u) + C$．

最大流最小割定理#

我们将证明：一个残量网络不存在增广路（无法增广），当且仅当存在 $s$-$t$ 割，使得 $c_f(S, T) = 0$．

充分性显然，下面证明必要性．

考虑其逆否命题：若任取 $s$-$t$ 割，都有 $c_f(S, T) > 0$，则存在增广路．

我们进行构造性证明：设初始 $s$-$t$ 割 $\{\{s\}, V \setminus \{s\}\}$．对于每一步的 $s$-$t$ 割 $\{S, T\}$，由于 $c_f$ 非负，我们总能取满足 $c_f(u, v) > 0$ 的 $(u, v) \in S \times T \subset E_f$．将其加入迹 $P$，更新 $s$-$t$ 割为 $\{S \cup \{v\}, T \setminus \{v\}\}$．由于 $V$ 是有限集，构造将终止，显然最终的迹 $P$ 为增广路．

重点来了，$c_f(S, T) = 0$ 意味着 $|f| = f(S, T) = c(S, T)$，总流量等于一个 $s$-$t$ 割的容量．我们不仅找到了最大流，而且证明了最大流最小割定理：最大流的流量等于最小割的容量．

NOTE

我们只要让一个残量网络无法增广，就能得到最大流．那是不是不断增广残量网络，就能找到最大流？

如果流量和容量都是整数，由于每次增广都至少让总流量 $+1$，那么最多需要 $|f|$ 次增广，每次增广都使用时间复杂度为 $O(|E|)$ 的朴素方法寻找增广路，因此总复杂度为 $O(|E||f|)$，$f$ 为最大流．

但如果不是整数，且使用朴素的方法进行增广，那么无法保证每次增广给总流量带来的增量存在最小值，无法保证增广能够终止．