最大流最小割定理 · 强对偶

最大流最小割定理

最大流与残量网络跑完 Ford-Fulkerson，末态那张图留了一个伏笔：从源点在残量网络里仍可达的点集 S（绿）与其余点 T 之间的那几条边，容量之和恰好等于最大流。这不是巧合，而是网络流最深刻的结论——max-flow = min-cut：一张网能输送的最大流量，等于把源、汇彻底切开所需付出的最小代价。本页把「割」严格定义清楚，先证弱对偶（任意流 ≤ 任意割），再证强对偶（最大流 = 最小割），最后在 cut 网上可自行推算这条等式。

1 · s-t 割：定义与割容量

一个 s-t 割 (cut) 是把全部节点划成两个不相交的集合 (S, T)，要求源点 $s \in S$ 、汇点 $t \in T$ 。任何这样的划分都是一个合法的割——它代表「把网络从 s 一侧到 t 一侧物理切断」的一种方案。

割的容量 (capacity) c(S, T): 所有从 S 指向 T 的边的容量之和：

c(S, T) = Σ { c(u, v) | u ∈ S, v ∈ T }。

关键在于只数正向——即起点在 S、终点在 T 的边。反方向（从 T 回到 S）的边一概不计入割容量。直觉上，割容量衡量的是「从源侧流向汇侧最多能漏过去多少」，逆向边不构成这种泄漏。

以 cut 网为例( $s\to a=4, s\to b=3, a\to b=2, a\to t=2, b\to t=3$ )，取末态最小割 S = {s, a, b}、T = {t}，逐条边判断它是否跨越割：

边	方向	是否计入 c(S,T)	贡献
$s\to a$	S → S	否（两端都在 S）	—
$s\to b$	S → S	否（两端都在 S）	—
$a\to b$	S → S	否（两端都在 S）	—
$a\to t$	S → T	计入（正向跨割）	`2`
$b\to t$	S → T	计入（正向跨割）	`3`

于是 c(S, T) = 2 + 3 = 5。注意 $a\to b$ 虽然横在中间，但两端同属 S，不跨割、不计入。换一个划分（比如 S = {s}）会得到另一个割容量( $c(s\to a) + c(s\to b) = 4 + 3 = 7$ )，通常更大。最小割 (min-cut) 就是在所有合法划分里，割容量最小的那个。

2 · 弱对偶：任意流 ≤ 任意割

第一个、也是较容易的方向：对任意合法流 f 与任意割 (S, T)，都有 $|f| \le c(S, T)$ 。即任何流的值，都被任何割的容量从上方卡住。这一条不需要算法，只靠流量守恒就能得到。

直觉： 流要从 s 一路抵达 t，而 $s \in S$ 、 $t \in T$ ，所以全部流量都必须穿过割——从 S 跨到 T。跨割的运力上限就是这些正向边的容量之和 c(S, T)，流自然超不过它。

一句话证明。 把流值 |f| 沿割重新记账：可以证明 $|f| = f(S, T) - f(T, S)$ ，即流值等于净穿过割的流量——从 S 流向 T 的总流量 f(S, T)，减去从 T 逆流回 S 的总流量 f(T, S)。

这一步靠流量守恒：把 S 里每个点（除 s）的「流入 = 流出」逐点相加，内部边（两端都在 S）成对抵消，只剩跨割项。于是

$|f| = f(S, T) - f(T, S) \le f(S, T) \le c(S, T)$ 。

第一个 $\le$ 因为 $f(T, S) \ge 0$ （流量非负），第二个 $\le$ 因为每条正向边 $f(u, v) \le c(u, v)$ （容量约束）。证毕。

弱对偶有一个立刻可用的推论：只要你找到某个流和某个割，它们的值相等，二者就分别是最大流与最小割。 因为任何流都 ≤ 这个割容量，所以没有流能更大；任何割都 ≥ 这个流值，所以没有割能更小。这把「证明最优」从「搜遍所有方案」降成「找到一对相等的见证」——强对偶要做的，正是保证这样的一对总是存在。

3 · 强对偶：最大流最小割定理

最大流最小割定理 (max-flow min-cut theorem): 在任意流网络中，最大流的值 = 最小割的容量。弱对偶已给出 $\max |f| \le \min c(S, T)$ ，强对偶补上反向不等式，把它逼成等号。证明的标准形式是下面三个命题彼此等价:

对一个合法流 f，以下三者等价：

其一： f 是最大流。
其二： 残量网络中不存在 $s \to t$ 的增广路(augmenting path)。
其三： 存在某个割 (S, T)，使得 c(S, T) = |f|。

其中「其一 ⇒ 其二」是显然的（若还有增广路，就能再推流，f 不是最大）；「其三 ⇒ 其一」由弱对偶给出（等值的流与割互为最优见证）。真正有内容、也最简洁优雅的是**「其二 ⇒ 其三」的构造**：从「没有增广路」这个事实，直接造出一个容量恰等于 |f| 的割。

其二 ⇒ 其三：从残量网络里读出割。 设残量网络中已无 $s \to t$ 增广路。令 S = 「残量网络里从 s 仍可达的点集」，T 为其余点。由「无增广路」，t 不可达，故 $t \in T$ ,(S, T) 是合法割。现在逐条考察跨割的原边：

其一（正向边 $u\to v$ , $u\in S, v\in T$ ）必饱和： 若它没满(f(u,v) < c(u,v))，则其正向残量 > 0,v 就能从 u 在残量网络里被到达，于是 $v \in S$ ——与 $v \in T$ 矛盾。故 f(u, v) = c(u, v)。

其二（逆向边 $v\to u$ , $v\in T, u\in S$ ，即从 T 回流到 S 的原边）必零流： 若 f(v, u) > 0，则它对应的反向残量边 $u\to v$ 残量 > 0,v 又能从 u 到达，同样得 $v \in S$ ，矛盾。故 f(v, u) = 0。

代回弱对偶里的恒等式： $|f| = f(S, T) - f(T, S)$ 。前一项每条边都饱和，所以 f(S, T) = c(S, T)；后一项每条边都零流，所以 f(T, S) = 0。于是

$|f| = c(S, T) - 0 = c(S, T)$ 。

这个割的容量恰好等于流值，既证了 f 是最大流，也证了 (S, T) 是最小割。证毕。

这套构造也解释了最大流与残量网络末态那张图为何「正好」：Ford-Fulkerson 停在「无增广路」，而停下来的同时，残量网络里 s 的可达集就自动给出了最小割。算法不需要额外去找割——割是「跑完最大流」这件事的副产品。Edmonds-Karp 用 BFS 找增广路，保证迭代次数有限、从而该构造对任意整数容量网络都成立，这也补全了「最大流一定存在」的存在性。

4 · 单步运行：求最小割

在 cut 网上用 Edmonds-Karp（BFS 找增广路）跑到底。前几步是普通增广，流量逐步上涨；最后一步无增广路时，渲染器把残量网络里 s 的可达集 S 染绿、其余点 T 染灰，跨割的边 $a\to t$ 、 $b\to t$ 标红加粗，流量表里对应行也高亮。下方等式条会把「最大流 = 割容量」这条恒等式逐项展开。

读图。 末态里割边 $a\to t$ 与 $b\to t$ 都已饱和(flow = cap)：这正是「其二 ⇒ 其三」里证的「跨割正向边必满」。而从 T 回到 S 的原边在本网里没有（cut 网无逆向跨割边），逆向项天然为 0。于是割容量 2 + 3 = 5 与最大流 5 严丝合缝。换任何别的划分，割容量都不会更小。

注意： 最小割可能不唯一（不同划分可能并列最小），但最小割容量唯一，且永远等于最大流。本页用的是 Edmonds-Karp 停机时 s 的可达集给出的那个特定割。

5 · 为什么人们想求最小割

最大流常被当作「手段」，真正想要的答案往往是最小割——大量组合优化问题的目标，化归后就是「在某张构造出来的网络上求最小割」：

图像分割 (image segmentation): 计算机视觉里把像素分成前景 / 背景，建成「源 = 前景、汇 = 背景」的网络，最小割即代价最小的分割边界。
项目选择 (project selection): 有收益的项目与有成本的前置资源之间建图，最小割对应「放弃的收益 + 必付的成本」最小的取舍方案，割两侧即「做 / 不做」。
网络可靠性 (reliability): 要切断 s 与 t 的连通，最少需移除的边容量，正是最小割——衡量网络抵抗破坏的「咽喉」强度。

这些归约的具体建模（如何摆源汇、边容量取什么）放在问题建模详述；而「为什么最大流 = 最小割」这条对偶，其实是更一般的**线性规划对偶 (LP duality)**的一个特例——这个视角见LP 对偶。