最大流最小割定理 | Codeboy's Blog

形式陈述

沿用最大流的有限原弧记录模型： $A$ 是原弧集合，每条记录有确定的尾点、头点及有限非负实容量 $c(a)$ ，平行弧和反平行弧分别计数； $s\ne t$ 。对源侧 $S\subseteq V$ ，要求 $s\in S,t\notin S$ ，记

\delta^+(S)=\{a:\operatorname{tail}(a)\in S,\operatorname{head}(a)\notin S\},

\delta^-(S)=\{a:\operatorname{tail}(a)\notin S,\operatorname{head}(a)\in S\}.

割容量只加从源侧向外的原弧容量：

c(S,V\setminus S)=\sum_{a\in\delta^+(S)}c(a).

最大流最小割定理断言

\max_{f\text{ 可行}}|f|=\min_{S\ni s,\ t\notin S}c(S,V\setminus S).

更具体地，对任一可行流，以下条件等价：它是最大流；正残量图中不存在源汇路；存在一个与它等值的割。

净跨割恒等式与弱对偶

对 $S$ 内每个顶点的“流出减流入”求和。内部原弧在尾点出现正号、在头点出现负号，恰好抵消；自环也如此。跨割原弧则按方向剩下正号或负号。 $S$ 不含汇，除源外的顶点都守恒，故左边只剩源的净流出，得到

|f|=\sum_{a\in\delta^+(S)}f(a)-\sum_{a\in\delta^-(S)}f(a).

流量非负使第二项不大于零，而每条向外原弧流量不超过其容量，所以

|f|\le\sum_{a\in\delta^+(S)}f(a)\le c(S,V\setminus S).

这是弱对偶：每份可行流给最大值的下界，每个合法割给上界。若一对流、割取等，其他流都不可能更大，其他割都不可能更小，两者同时最优。这里按弧记录求和，因此不需要排除平行弧，也没有把反平行原弧与残量反向记录混在一起。

无增广路为何产生等值割

每条原弧 $a:u\to v$ 对应正向残量 $c(a)-f(a)$ 与反向残量 $f(a)$ 。若存在正残量的简单 $s$ - $t$ 路，取路上最小残量 $\Delta>0$ ，经过正向记录就给原弧加 $\Delta$ ，经过反向记录就减 $\Delta$ 。瓶颈保证各原弧仍在容量区间内；每个内部顶点的一入一出改变量相消，守恒保持；源净流出增加 $\Delta$ 。因此最大流不可能还有增广路。

反过来，若没有这种路，取 $S$ 为残量图中从 $s$ 可达的顶点。 $s\in S$ 而 $t\notin S$ ，它确实定义一个割。对 $a\in\delta^+(S)$ ，若 $f(a)<c(a)$ ，正向残量就能从 $S$ 到外面，与可达集定义矛盾，所以这些原弧全饱和。对 $a\in\delta^-(S)$ ，若 $f(a)>0$ ，其反向残量同样能从 $S$ 到外面，仍矛盾，所以这些原弧流量全为零。代回恒等式即得

|f|=\sum_{a\in\delta^+(S)}c(a)-0=c(S,V\setminus S).

弱对偶遂证明流最大、割最小。这同时证明了上述三个条件的等价，而没有预先假设增广算法会停机。

实容量的存在性与整数算法的终止性

一般实容量下，零流保证可行域非空；有限个约束 $0\le f(a)\le c(a)$ 与守恒等式定义闭且有界的有限维集合。Heine–Borel 定理给出紧性，连续函数 $|f|$ 再由极值定理取得最大值。取达到最大值的流，它不能有增广路，上一段便构造出等值割。这证明了实容量定理，与某种选路规则能否有限终止是两件事。

整数容量则还能给出算法式证明。零流整数；若当前流整数，正反残量及路径瓶颈也整数，更新后仍整数。每次成功增广至少使流值增加 $1$ ，而流值不超过源出原弧容量和这个有限整数，故从零流开始必有限终止，终态由可达割证明最优。这证明存在整数最大流，也证明精确整数增广会产生它；不保证每一个实值最大流都整数。

直觉

任意源汇割都像一道横截面。流可以多次进入或离开源侧，所以应计算净跨割流，而不是把所有跨边流量直接相加。容量则只限制向外通道能送出多少；往回送只会降低净流值。

增广失败把“似乎送不进去”变成可检查的瓶颈：源能到达的区域，其每条向外原弧已经用满，每条向内原弧又没有可撤销的流。于是这一道横截面的容量恰好等于已经送出的流量，上下界相遇。

例子与边界

值为五的流与割

图中原弧为 $s\to a,s\to b,a\to b,a\to t,b\to t$ ，容量依次为 $4,2,1,2,3$ ，流量依次为 $3,2,1,2,3$ 。在 $a$ 处，入流 $3$ 等于出流 $1+2$ ；在 $b$ 处，入流 $2+1$ 等于出流 $3$ ，故流可行且 $|f|=3+2=5$ 。

$s\to a$ 尚有一单位正残量，所以 $a$ 可达；但 $s\to b,a\to b,a\to t$ 都已饱和，残量搜索不能离开 $S=\{s,a\}$ 。其余反向记录也不能把搜索带到 $b,t$ 。因此 $T=\{b,t\}$ ，且

c(S,T)=c(s,b)+c(a,b)+c(a,t)=2+1+2=5=|f|.

这个流最大、割最小。源出弧的容量和却为 $6$ ；只看源割只能得到较松的上界，必须找对瓶颈才能闭合证明。

最大流及其残量可达集给出的最小割 — 边标注为流量/容量；蓝色虚线分开 S 与 T，蓝色实线是从 S 指向 T 的三条割边。

反向原弧不能从割容量中扣除

设只有原弧 $s\to t$ （容量 $2$ ）和 $t\to s$ （容量 $7$ ）。令前者流 $2$ 、后者流 $0$ ，得到值 $2$ 的最大流。唯一源侧为 $\{s\}$ ，割容量为 $2$ ，并非 $2-7$ 。净流恒等式减去的是反向原弧上的实际流量，不是其容量。即使把后者的流量改成 $1$ ，所得可行流值也只是 $1$ ，不影响容量上界 $2$ 。

整数性同样是存在命题。例如原弧 $s\to u,u\to a,u\to b,a\to t,b\to t$ 的容量均为 $1$ 。令 $s\to u$ 流一单位，其余四弧各流半单位，得到非整数最大流，值为 $1$ ，由源割容量 $1$ 证明最优；沿 $s\to u\to a\to t$ 送一单位则是同值的整数最大流。实容量下定理仍成立，但任意选路的 Ford–Fulkerson 可能无限增广；存在最优解并不推出任意求解过程终止。

推论与应用

独立核验最优性

证书可以只含各原弧的流量和源侧位向量。检查器先验证记录数量与数值格式，再逐弧确认容量约束、累计各顶点的净流出，并检查所有内部顶点为零；同时确认源侧包含 $s$ 、不包含 $t$ ，逐原弧计算割容量。最后要求 $|f|=c(S,V\setminus S)$ 。可靠性直接来自弱对偶，检查器不需要相信求解器的残量搜索或选路策略。

在精确算术的单位成本模型下，证书长度为 $O(|V|+|A|)$ 个条目，检查耗时 $O(|V|+|A|)$ ，辅助累加空间 $O(|V|)$ 。若容量与流以二进制整数或有理数编码，还应计入数值位长及精确加法、比较成本；任意实数并没有自动获得有限机器编码。浮点近似相等也不能直接替代这里的严格等值证书。

匹配以及其他调用

经由网络流的二分图匹配用单位容量确保整数增广每次增加一对。删去其算例中的 $c3$ 后，值为 $3$ 的流对应源侧 $\{s,a,b,c,1,2\}$ ，三条割弧为 $s\to d,1\to t,2\to t$ 。该页进一步证明可达左点的完整邻集恰为可达右点，从而把这份割译成 Hall 障碍及同大小顶点覆盖；任意单位网络最小割都能这样直接翻译的说法并不成立。

定理为 Ford–Fulkerson、Dinic 与 Push–Relabel 提供最优性依据，也用于 Menger 定理、项目选择和图像分割。流分解解释可行流由哪些路径和环组成，但仅有分解不证明最优，仍需同值割等上界证书。从线性规划角度看，流与割体现原始、对偶最优值相等；整数容量的整数最优解则由上面的整数不变量另行保证。

全局最小割去掉指定源汇，图稀疏化希望近似保存许多割，Gomory–Hu 树在无向图中压缩所有点对的割值。这些目标不能由一次固定源汇计算代替。最小割也不必唯一；找到任意一个与可行流同值的合法割，就足以核验该流的最优性。

一般有噪网络的切面不再只是独立边容量相加。网络切集信息上界用 $I(X_S;Y_{S^c}|X_{S^c})$ 约束跨界信息流，将同侧节点完全合作作为放宽条件。它在独立无噪链路上恢复割容量，但在一般中继网络上通常只是外界；还需匹配的可达协议才有容量等号。

参考资料

Kevin Wayne，Algorithm Design, Chapter 7: Network Flow，©2005 Pearson–Addison Wesley，课件第 14–17、24–26、29 页：净跨割恒等式、弱对偶、残量割、整数性及无理容量边界。本页按原弧记录展开求和以容纳平行弧与反平行弧。
MIT OCW，Lecture 11–12: Network Flows and Matching，PDF 首页日期 2022-03-18，托管于 18.200 Spring 2024；PDF 第 7 页，定理 2 及证明：整数增广、终止与可达割。
L. R. Ford Jr.、D. R. Fulkerson，Maximal Flow Through a Network，Canadian Journal of Mathematics 8，1956，pp. 399–404，§1、定理 1。原文使用链流与断开集表述；现代有向残量证明见上述课件。

形式陈述 ​

净跨割恒等式与弱对偶 ​

无增广路为何产生等值割 ​

实容量的存在性与整数算法的终止性 ​

值为五的流与割 ​

反向原弧不能从割容量中扣除 ​

独立核验最优性 ​

匹配以及其他调用 ​

反向链接