增广路

增广路是"局部改进"思想在匹配问题上的具体化：给定一个还不够好的匹配，我们不推倒重来，而是寻找一条能让匹配变大一点的修改路径。沿增广路把匹配边与非匹配边整体翻转时，路径内部每个顶点原本恰有一条匹配边经过，翻转后仍恰有一条，不会产生冲突；而两个原本"空着"的端点各自获得一条新匹配边，净收益正好是一。真正不平凡的是 Berge 定理的反方向：它保证只要当前匹配不是最大的，这样的改进路径就一定存在——把当前匹配与某个更大的匹配作对称差，得到的图中每个顶点度数至多为二，因而分解为若干路径和交替圈，边数的盈余必然集中在某条以非 $M$ 边开头结尾的路径上，这就是一条增广路。于是"找不到增广路"不只是算法停机的信号，而是最优性的证明。

最短的增广路是一条单边：若边 $uv\in E$ 的两个端点都未被 $M$ 覆盖，则 $P=uv$ 就是长度为一的 $M$-增广路，翻转后直接把 $uv$ 加入匹配。再看一个长度为三的例子：设路径 $abcd$ 中 $bc\in M$，而 $a,d$ 未被覆盖，则 $ab,cd\notin M$，翻转后匹配由 $\{bc\}$ 变为 $\{ab,cd\}$，大小从一增到二。

交替但不增广的路径未必带来改进。翻转结果取决于首尾边是否属于 $M$：首尾均为非匹配边时，非匹配边比匹配边多一条，大小增加 $1$；一端为匹配边、另一端为非匹配边时，两类边数相等，大小不变；首尾均为匹配边时，大小减少 $1$。不过，若路径在某个已匹配端点以非匹配边进入，而该端点原有的匹配边不在路径上，翻转后该端点会关联两条匹配边，结果不再是匹配。交替偶圈的两类边数相等，翻转后仍是同样大小的匹配。增广路要求两端均未覆盖，正是为了排除端点冲突并保证净增益为一。

Berge 定理把“求最大匹配”归约为“反复寻找增广路”。二分图没有奇环，可直接在交替森林中搜索；一般图中层次会被奇交替环破坏，Edmonds blossom 算法公理库Edmonds blossom 算法Edmonds' blossom algorithm · Blossom algorithm通过识别并收缩奇交替环，在一般图中保持增广路存在性并求最大匹配的算法。通过收缩并 lift 增广路保持这一定理。Hopcroft–Karp 的分层批量增广、带权指派的顶点标号，以及二分匹配的网络流建模公理库经由网络流的二分图匹配Bipartite matching via maximum flow把二分图匹配编码为单位容量流网络并由最大流恢复匹配。都是不同求解结构；拟阵交公理库拟阵交定理Matroid intersection theorem · Edmonds matroid intersection theorem两个有限拟阵的最大共同独立集大小，等于一次底集切分上的两侧秩之和的最小值。则把交替增广提升为两套独立性交换关系上的有向路。