1. 引言
在计算机科学中，“增广路径”（Augmenting Path）这一概念出现在两个不同的场景中：匹配理论（Matching Theory）和最大流问题（Maximum Flow Problem）。
在这两个问题中，我们都可以利用增广路径来提升已有解的规模，从而逐步逼近最优解。
本文将分别从这两个场景出发，讲解增广路径的定义、作用以及相关算法。
2. 匹配理论中的增广路径
2.1 定义
在图的匹配问题中，一个匹配（Matching）是图中的一组边，满足：任意两条边都不共享同一个顶点。
如果一个匹配在所有可能的匹配中规模最大，我们称它为最大匹配（Maximum Matching）。如果一个顶点被匹配中的某条边所连接，我们就说它是已匹配（Matched）顶点；否则就是未匹配（Unmatched）顶点。
2.2 增广路径的作用
在匹配理论中：
增广路径是指：从一个未匹配顶点出发，交替经过“非匹配边”和“匹配边”，最终到达另一个未匹配顶点的路径。
例如下图中，路径 a → a' → b → b' → c → c' 就是一个增广路径（绿色高亮）：
我们可以利用增广路径来扩展当前匹配。具体方法是：对当前匹配集合与增广路径上的边进行对称差（Symmetric Difference）操作。
对称差操作的含义是：
- 移除匹配中与增广路径重合的边；
- 添加增广路径中不在匹配中的边；
- 保留匹配中与增广路径无关的边。
例如，下图展示了如何通过增广路径 a → a' → b → b' → c → c' 扩展初始匹配：
✅ 结论：只要不断寻找并应用增广路径，就能从任意初始匹配出发，最终获得最大匹配。
2.3 利用增广路径求解最大匹配的经典算法
- 匈牙利算法（Hungarian Algorithm）：适用于二分图（Bipartite Graph）的最大匹配问题。
- 花算法（Blossom Algorithm）：适用于一般图（General Graph）的最大匹配问题。
这些算法通常使用深度优先搜索（DFS）或广度优先搜索（BFS）来查找增广路径。
3. 最大流问题中的增广路径
3.1 基本概念
在最大流问题中，我们处理的是流网络（Flow Network）：
- 是一个有向图，每条边有容量（Capacity）。
- 图中有两个特殊节点：源点（Source）和汇点（Sink）。
- 流必须满足两个约束：
- 边上流量不超过容量；
- 除源点和汇点外，每个节点的流入等于流出（流量守恒）。
目标是：从源点到汇点传输尽可能多的流量。
3.2 残留网络（Residual Network）
为了查找增广路径，我们需要构造残留网络（Residual Network）：
- 每条边都有一个残留容量（Residual Capacity）：
- 正向边：原容量减去当前流量；
- 反向边：当前流量（允许“回流”）。
- 如果某条边的流量为0，则其反向边不会出现在残留图中。
例如，原图中有一条边 (s, v1)，容量为16，当前流量为11：
- 残留图中将出现：
- 正向边
(s, v1)，残留容量为5； - 反向边
(v1, s)，残留容量为11。
- 正向边
3.3 增广路径的定义
在最大流问题中，增广路径是从源点到汇点的一条路径，存在于残留网络中。
路径上的每条边都必须有正的残留容量，表示我们可以“增广”这条路径来提升总流量。
例如下图中红色路径即为一条增广路径：
我们可以沿该路径增加最多4个单位的流量。这会：
- 增加
(s, v2)和(v3, t)的流量； - 减少
(v3, v2)的流量。
⚠️ 注意：增广路径不仅可以增加边上的流量，也可以减少某些边的流量。
3.4 利用增广路径求解最大流的经典算法
Ford-Fulkerson 算法：
- 只要残留图中存在增广路径，就不断增广当前流。
- 最终当残留图中没有增广路径时，当前流就是最大流。
- 时间复杂度取决于增广路径的选择方式。
Edmonds-Karp 算法：
- 是 Ford-Fulkerson 的一个实现，每次使用 BFS 找到最短增广路径。
- 时间复杂度为
O(VE²)。
Dinic 算法：
- 每次构建层次图（Level Graph），然后寻找阻塞流（Blocking Flow）。
- 阻塞流可以一次处理所有长度相同的增广路径。
- 时间复杂度为
O(V²E)，性能更优。
4. 总结
本文从两个角度介绍了增广路径：
| 场景 | 增广路径的作用 | 相关算法 |
|---|---|---|
| 匹配理论 | 扩展当前匹配以获得最大匹配 | 匈牙利算法、花算法 |
| 最大流问题 | 在残留图中寻找路径以提升总流量 | Ford-Fulkerson、Edmonds-Karp、Dinic |
✅ 核心思想：增广路径的本质是通过局部调整来逼近全局最优解。
掌握增广路径的原理，是理解图论中许多经典算法的关键一步。