4.2 最大流最小割定理

4.2 最大流最小割定理

本节摘要：割是把顶点集分成"含源点的一侧"与"含汇点的一侧"的划分，割容量是横跨两侧的边容量之和；最大流最小割定理断言——流网络中最大流的值恰好等于最小割的容量。它同时给出三件事的等价判定（流最大、残存网络无增广路、存在割被流恰好填满），是最大流算法正确性与终止性的理论根基，也让"找系统瓶颈"变成了一个可计算的问题。

先说结论

阅读完本节，你应当能够：

1. 给出割与割容量的定义，手算小图的所有割；
2. 陈述最大流最小割定理与三条件等价；
3. 用"对流的上界 + 构造性达到"的论证直观证明定理；
4. 从最终残存网络读出最小割，解释其瓶颈诊断价值。

一、问题与直觉：天花板在哪里

继续水利原型。无论调度多么聪明，系统的输水上限受制于一件事：任何把水库与城市隔开的"截面"上，管道的总容量。想象用一把剪刀横剪管网，把顶点分成"水库侧 S"与"城市侧 T"——水从 S 流向 T 只能走被剪断的那几条管，它们的容量之和就是这个割的容量。每个割都是流量的天花板：流要穿过每个割，值不可能超过任何割的容量。

割的正式定义：顶点集的一个二分（S 与 T 互补），源点在 S、汇点在 T。割容量：所有从 S 指向 T 的边的容量之和（注意只算正向边——T 指向 S 的边不载"净流量过割"）。最小割：容量最小的那个割，即所有天花板里最低的那一个。

于是有天然的不等式链：任何流的值 ≤ 任何割的容量 ≤ 最小割的容量。最大流能不能顶到这块最低的天花板？定理回答：恰好能。

二、定理与三条件等价

最大流最小割定理：流网络中，以下三个命题等价——

1. 流 f 是最大流；
2. 残存网络中不存在从源点到汇点的增广路径；
3. 存在一个割，其容量恰好等于 f 的值。

论证梗概（三步循环互推，证一等价于全部）：

• 1 推 2：若残存网络还有增广路，沿它增广就能得到更大的流，矛盾于 f 最大。
• 2 推 3：设残存网络中从源点可达的顶点集为 S，其余为 T。汇点必在 T（否则有增广路）。考察横跨割的每条边：其残存容量必为 0，否则终点会被划入 S——所以这些边全部满载；再看从 T 指回 S 的边，其流量必为 0，否则反向残存边会让起点进入 S。于是穿过割的净流量恰好等于割容量，而这个净流量正是 f 的值。
• 3 推 1：前述不等式链说流的值不超过任何割的容量，如今等于某个割，自然就是最大。

这份论证的漂亮之处在于构造性：它不但证明了等式，还告诉我们"算法跑完后的残存网络里，从源点做一次可达性标记（BFS/DFS），标记边界就是一张最小割"。

三、一个完整的手算例子

用一个小网络走完全程（原始文集同款结构）：源点 A，汇点 D，边为 A 到 B 容量 4、A 到 C 容量 2、B 到 D 容量 5、C 到 B 容量 7、C 到 D 容量 5（沿用原始文集中"残存网络"一节的算例数值：A 到 B 残存 4、A 到 C 残存 2 等）。

逐轮增广：
第1轮 路径 A-B-D 瓶颈 min4 5 为4 增广4
第2轮 路径 A-C-D 瓶颈 min2 5 为2 增广2
第3轮 残存网络中 A的出边全部归0 无增广路 停
最大流 = 4加2 = 6
最小割 残存网络中从A可达的只有A本身 割为 A 与 其余
割容量 = A到B的4 加 A到C的2 = 6 与最大流吻合
​

关键观察：最终从源点可达的集合恰好只有源点自己——因为它的两条出边都被"灌满"了。这就是"割被流填满"的直观样子：最小割就是被最大流顶住的那块天花板。

割与流的对照

四、定理的工程红利：瓶颈诊断

定理的日常价值不止"算最大流"，更在**"指出该改哪里"**：

• 网络扩容决策：算出最小割后，横跨割的满载边就是瓶颈管段。预算有限时，加粗最小割上的边（哪怕只加一条）才可能提升总流量；加粗别的边一分钱效果都没有。
• 团队沟通语言："瓶颈割容量 23"比"最大流 23"更能传达"改哪能涨"的信息——前者自带位置（割的两侧），后者只是数字。
• 可靠性评估：最小割的容量也度量了"断掉多少容量能让源汇彻底断流"，与图的连通度分析一脉相承。

一个容易忽略的对偶视角：最大流是最优调度问题（怎么安排流量），最小割是最脆弱截面问题（哪里是软肋）。定理说这两个看似无关的优化问题共享同一个数值——运筹学里这类"对偶"结构屡见不鲜，线性规划的对偶定理正是它的一般形式。

⚠️ 常见坑：把"T 指向 S 的边"也算进割容量。割容量只数"从源侧指向汇侧"的边；反向边在"净流量过割"的账目里做减项。另一个坑：以为最小割的"割"是删边——它是顶点集的划分，割容量只是对划分的一个计量，不必真的删。

💡 关键直觉：把割想成"工资总账"：流是每月开销，任何月份的开销都不超过账上任何一个账户的余额上限；定理说，总有一笔账（最小割）恰好被开销顶满——想让开销再涨，只能先给那笔账加钱。

五、深入一层：对偶的世界观

"最大流等于最小割"是线性规划对偶在最流问题上的具象：最大流是"在约束下最大化目标"的原问题，最小割是"用权重给约束定价"的对偶问题。对偶的最优值相等（强对偶性），于是同一个数字有了两副面孔：调度者看到"还能再送多少"，审计者看到"哪里是最窄的门"。这个视角帮你预测一类现象：凡是"最大化某种输送"的问题，通常都藏着一个"最小化某种切断"的影子问题——遇到其一，主动去找其二，常能白拿一个解题入口。

工程上这个对偶还给了"灵敏度分析"的快捷通道：最小割上的边是"紧约束"（满了），割外的边是"松约束"（有余量）。扩容紧约束的边才能提升总流，扩容松约束的边纯属浪费——这套语言与运筹学、甚至经济学的"影子价格"完全同构。

常见疑问解答

最小割一般有几个？会不唯一吗？

可能不唯一（多个割并列最小），算法输出哪一个取决于可达标记的细节。并列时业务上可按次级标准（施工难度、拆迁成本）挑选。判定"所有最小割"有专门算法，但多数场景拿到任意一个就够用。

"割"为什么不数从 T 指回 S 的边？

割容量定义为"从源侧指向汇侧的边容量和"，衡量的是"流过这个划分的净输送上限"。反向边承载的是回流，在净流量的账目里做减项；若把它也计入，得到的量不再对应任何流的上界，定理失效。

怎么从算法结果里"读出"最小割？

最大流跑完后，在最终残存网络上从源点做一次 BFS 或 DFS 标记可达集 S，其余为 T；横跨 S 到 T 的原网络边（此刻全部满载）即构成一个最小割。建议把它做成最大流接口的默认输出，诊断价值极高。

定理对"多源多汇"或"无向图"还成立吗？

成立，但先做标准化：多源多汇用超级源汇归一（4.4 节）；无向边可拆成两条有向边（容量平分或各设全容量，按语义定）。标准化之后的网络原封不动地享受定理。这说明定理的适用面由"容量加守恒"结构决定，与表面的图形态无关。

动手实验：穷举一个小图的全部割

取四顶点网络（源、汇各一，中间两点），割的总数是"中间点的子集划分"，共四个。逐个计算割容量，找出最小者；再跑一遍 Edmonds-Karp 求最大流，验证两数相等；最后按"残存网络可达标记"读出最小割，与穷举结果对照。整个过程不超过十五分钟，但"最大流等于最小割"从定理变成了你亲手验证过的事实。进阶一步：把某条边的容量改小，重跑全流程，观察最小割如何"跳"到包含新瓶颈的位置。

定理的面试表述模板

被要求口述定理时，一个稳妥的三段式：先说结论（最大流的值等于最小割的容量）；再给直观（每个割都是流的天花板，最小割是最低的天花板，而最大流恰好顶住它）；最后补构造（算法终止后从源点标记可达集即得最小割）。三句话有结论、有直觉、有操作，比背长定义更能体现理解层次。

定理能推广到"最小费用最大流"吗？

不能直接推广——费用版的两个目标（流最大、费最小）没有同样简洁的"等于某个割"刻画，取而代之的是"沿最短增广路增广即可达到最小费用"的算法性结论。但这不妨碍对偶思想继续工作：最小费用流同样存在线性规划对偶，其形式涉及"点势"与"约简费用"——Johnson 重赋权的势函数概念在此再次登场，图论的大概念就这么一以贯之。

顺带一个命名澄清：文献里"割"有时写作 s-t cut 以强调源汇分居两侧，与无向图里的"边割集"概念不同名同义之外有别；读资料时认准"源在 S、汇在 T"这一条即可避免混淆。

温故知新

• 割的定义：顶点二分，源汇分居；割容量只计源侧指向汇侧的边。
• 天花板关系：任何流值不超过任何割容量，因此不超过最小割。
• 定理内容：最大流值等于最小割容量，且"流最大、无增广路、存在被填满的割"三条件等价。
• 构造性读法：算法终止后在残存网络上从源点做可达标记，边界即一张最小割。
• 满载即瓶颈：横跨最小割的边必然满载，这些边就是升级改造的靶点。
• 对偶视角：最大流是调度问题，最小割是脆弱性问题，一个数值连接两个世界观。
• 本章枢纽：定理既收口 4.1 的增广过程，又托底 4.3 的算法正确性。

定理在手，下一节把 4.1 的"增广"和本节的"停止条件"组装成可运行的算法——Ford-Fulkerson 框架与它的多项式化改造 Edmonds-Karp。