增广路径
增广路径是最大流和二分匹配算法的核心操作对象——在残差网络中沿增广路径增广可增大流量，在匹配中沿增广路径做对称差可增大匹配。
定义
形式化定义
最大流中的增广路径：在残差网络 中，一条从源 到汇 的简单路径 称为增广路径。其残差容量为： 沿 增广后，流值恰好增加 。
匹配中的增广路径：给定图 和匹配 ：
- M-交替路径：一条简单路径，其边在 和 之间交替出现
- M-增广路径：一条M-交替路径，且其第一条边和最后一条边都不属于 。增广路径的两个端点都是未匹配顶点，且包含奇数条边（非匹配边比匹配边多1条）
核心性质
| 性质 | 描述 |
|---|---|
| 最大流判据 | 中不存在增广路径 是最大流（引理24.2） |
| 最大匹配判据 | 不存在 -增广路径 是最大匹配（Berge定理） |
| 增广效果（流） | 沿增广路径增广后，流值增加 |
| 增广效果（匹配） | 沿增广路径做对称差 ，匹配大小增加1 |
| 路径长度单调性 | Edmonds-Karp和Hopcroft-Karp中，增广路径长度单调不减 |
关系网络
graph LR A["增广路径"] --> B["最大流中<br/>残差网络 s→t 路径"] A --> C["匹配中<br/>连接两个未匹配顶点的交替路径"] B --> D["增广 → 流值增大"] C --> E["对称差 → 匹配增大"] D --> F["无增广路径 = 最大流"] E --> G["无增广路径 = 最大匹配<br/>Berge定理"]
章节扩展
第24章：最大流
在24.2节中，增广路径定义在残差网络 上，是从源 到汇 的简单路径。Ford-Fulkerson方法的核心循环就是反复在 中寻找增广路径并沿路径增广。
增广路径的残差容量 决定了本次能增加的流量。沿路径增广时：
- 正向边 ： 增加
- 反向边 ： 减少 （即撤销部分流量）
Edmonds-Karp算法通过BFS选择最短增广路径，保证路径长度单调递增（引理24.4），从而获得 的多项式时间复杂度。
第25章：二部图匹配
在25.1节中，增广路径的定义从残差网络转移到匹配的交替路径框架。
M-增广路径是一条连接两个未匹配顶点的M-交替路径，包含奇数条边。非匹配边有 条，匹配边有 条，因此非匹配边比匹配边多1条。沿增广路径做对称差操作 ，将 中原属于 的边移出、原不属于 的边加入，得到 。
Berge定理建立了增广路径与最大匹配之间的充要关系： 是最大匹配 不存在 -增广路径。这是所有基于增广的匹配算法（简单增广、Hopcroft-Karp）的理论基础。
补充
补充说明
增广路径在最大流和匹配两个领域中扮演着相同的结构性角色——它们都是”当前解不是最优”的证书，也是”改进当前解”的操作对象。这种统一性不是巧合：二分匹配可以通过归约为最大流来求解，而匹配中的增广路径恰好对应流网络中残差网络的增广路径。两种定义在流网络归约框架下是完全一致的。