第4章 最大流
第 4 章 · 最大流
章节摘要：最大流问题研究容量网络中"从源点最多能向汇点输送多少流量"。本章自底向上搭建全套概念：流网络的容量约束与流量守恒、残存网络与"允许反悔"的反向边、增广路径与瓶颈容量；随后给出整章的理论顶点——最大流最小割定理（最大流的值等于最小割的容量）；再落实到 Ford-Fulkerson 框架与 Edmonds-Karp 的 BFS 增广实现；最后扩展到二分图匹配、多源多汇、节点容量等变体与现实应用。水利管网是贯穿本章的物理原型。
上手前先明确
阅读完本章，你应当能够：
- 写出合法流的两个约束（容量上限、流量守恒）并据此校验一个流；
- 构造给定流的残存网络，解释反向边为何是"撤销通道"；
- 陈述并直观论证最大流最小割定理；
- 实现 Ford-Fulkerson 框架与 Edmonds-Karp，说明后者多项式复杂度的来源；
- 把任务分配、交通调度等问题建模为流网络，识别最小割的"瓶颈诊断"价值。
核心概念速览
最大流的一切聪明，都藏在"反向边允许反悔"这一个小设计里。
最大流概念阶梯
子章节导航
4.1 流网络、流与残存网络
定义容量网络与合法流，重点拆解残存网络与反向边——"撤销已有分配"的能力是增广类算法的灵魂。
4.2 最大流最小割定理
整章的理论顶点：割的容量如何定义、为什么"最大流 = 最小割"、这个等式给工程带来的瓶颈诊断能力。
4.3 Ford-Fulkerson 与 Edmonds-Karp
从框架到实现：前者定义"找增广路、增广、重复"的循环，后者用 BFS 选最短增广路，换来多项式复杂度保证。
4.4 最大流的应用与扩展
二分图匹配、交通调度、网络资源分配等经典落地，以及多源多汇、节点容量、费用流等扩展方向。
子章节之间的逻辑关系
本章是严格的金字塔：没有残存网络（4.1）就无法定义增广，没有增广就无法证明定理（4.2），定理又是算法终止与正确性的定心丸（4.3），而应用（4.4）里"最小割指出瓶颈"的用法直接消费定理的结论。
容量与守恒 (4.1) → 残存网络 → 增广路径 ↓ 最大流最小割定理 (4.2) ←—— 无增广路径时流最大 ↓ Ford-Fulkerson 框架 → Edmonds-Karp 实现 (4.3) ↓ 应用与扩展 (4.4)：匹配 调度 资源分配 瓶颈诊断
常见疑问解答
最大流是三大问题里最难的部分吗？
概念密度上是。它有五个环环相扣的抽象（流网络、合法流、残存网络、增广路径、割），比最短路径的"松弛"单一概念多了一层结构。破局点在 4.1 节的反向边——把"撤销已分配流量"的机制想通，后面的一切都是水到渠成。建议第一次学习时放慢 4.1 的节奏，亲手画一遍残存网络的演化。
学最大流必须先学线性规划吗？
不必。最大流确实可以表述为线性规划、最小割也确实是它的对偶，这条理论脉络很优美，但本章的展开完全不需要它——全部论证都基于构造与直观交换论证。有兴趣的话，学完本章再回头读对偶理论，会有"原来如此"的复利。
这一章的面试权重如何？
在国内大厂与算法竞赛向的岗位里，二分图匹配（4.4 的转化）是高频考点，Edmonds-Karp 的手推也不罕见；一般应用岗则更常考"你能不能把一个资源分配问题识别成流模型"。识别能力比手写能力更稀缺，4.4 的三问判定法值得背下来。
本章的自测清单
五题自查：默写合法流的两条铁律；给一个具体流构造残存网络（含反向边容量）；陈述最大流最小割定理并给出构造性读法；解释 Edmonds-Karp 复杂度的来源；把"任务分配"问题一步步转成流网络。任何一题卡壳，回到对应小节把概念链条补齐——最大流的概念是一根环环相扣的链条，断一环则后面全松。
章末的一句提醒
本章的概念链条最长，学习时建议守住一条主线：一切为了"反悔"——残存网络为反悔提供场地，反向边提供通道，增广提供动作，定理为"何时不必再反悔"盖章。抓住这条主线，五个抽象就是一个整体；丢了它，每个概念都会变成孤立的名词。
前置知识与后续延伸
- 前置：第 1 章的有向图与 BFS（Edmonds-Karp 的增广路搜索就是 BFS）；第 2 章的"松弛—修正"迭代思维与本章的"增广—反悔"一脉相承。
- 为后续铺垫：4.4 的费用流、匹配等扩展是进一步学习网络流算法的入口；第 5 章的性能视角会回顾增广类算法的复杂度与实现要点。