第7章 补给线之战：网络流与匹配

第 7 章 · 补给线之战：网络流与匹配

章节摘要：远征队深入敌后，补给成了生命线。前线的仓库与后方的物资基地之间隔着容量受限的通道网络——每条路每小时只能通过有限吨位，整张网一昼夜最多能送多少？这是网络流问题；反过来，敌军想切断补给，最少炸掉哪几条路？这是最小割问题。本章把这一对对偶问题讲透：Ford-Fulkerson 方法在残余网络里反复找增广路，Edmonds-Karp 用广度优先给它装上终止性保险，最大流最小割定理为两边盖章等值。收官一节进入二分图匹配：任务与兵力一一配对，匈牙利算法与最大流的视角互相印证。这是全册算法战役的高潮，也是组合优化优雅性的巅峰展示。

本章知识点清单

下列考核点覆盖本章内容：

1. 给出流与割的形式化定义（容量约束、流量守恒、割的容量），并说明可行流构成的单纯形。
2. 解释残余网络与增广路的构造，手推一张小图的增广全过程。
3. 说明 Ford-Fulkerson 为何可能跑很久甚至不终止，Edmonds-Karp 如何用广度优先修复。
4. 陈述并运用最大流最小割定理，完成"运力上限 = 切断代价"的对偶论证。
5. 把二分图匹配转写成最大流问题，并实现匈牙利算法的增广思路。
6. 用匹配、覆盖、独立集之间的对偶关系分析任务分配类问题。

核心概念速览

金句：运力的上限与切断的代价是同一个数——对偶性是组合优化给世界的最深情的承诺。

子章节导航

第 1 节"最大流：补给线的极限运力"从铁路调度的历史现场切入，建立流的形式化模型，推演残余网络与增广路这对核心机制，给出 Edmonds-Karp 的完整实现与复杂度论证。

第 2 节"最小割：切断补给的最低代价"把视角翻到敌方：容量最小的割是网络的命门所在。本节完成最大流最小割定理的证明拼图，并演示这枚定理在连通度、图像分割、瓶颈分析里的惊人多面性。

第 3 节"二分图匹配：任务与兵力的配对"处理"一一配对"问题：左边的任务、右边的队员、中间的胜任关系。增广路的思路与最大流一脉相承，匈牙利算法由此诞生，二分图的对偶结构（匹配与顶点覆盖）也在此收拢。

三节之间的战场衔接

一句话论点：最大流问"送多少"，最小割问"断哪里"，匹配问"怎么配"——前两者互为对偶同值，后者是前者的特款特解。

  容量网络
     │ 形式化
     ▼
  最大流 ←──对偶同值──→ 最小割
     │ 左右各添源汇       │ 命门诊断
     ▼                    ▼
  二分图匹配           连通度/分割
     │ 增广路
     ▼
  匈牙利算法（分配问题生产线）
​

前置知识与后续延伸

前置：第 2 章的存储结构与第 3 章广度优先（Edmonds-Karp 的选路引擎）、第 5 章的"松弛"语汇（残余边权的更新与它神似）。二分图的基本概念来自第 1 章的图类家族。

后续延伸：匹配与独立集、顶点覆盖的对偶关系直接铺向第 8 章的收尾攻坚；网络流的建模能力是运筹学、交通工程、芯片设计的通用底座，第 10 章的工程检阅会看到它的调度化身。若继续深造，费用流、环流等更深的模型都建立在本章的残余网络世界观之上。学习本章最易犯的错是"记结论不记模型"：最大流最小割的值等关系只是终点，真正要带走的是"翻译"的能力——把一个陌生场景翻译成源、汇、容量三件套。每读完一节，建议自问：这个问题的网络是什么？源和汇放在哪？容量编码了什么资源？三问答得利索，本章的兵法才算真正入库。