形式陈述

给匹配 $M$，$M$-增广路是一条边在 $E\setminus M$ 与 $M$ 间交替、且两个端点均未被 $M$ 覆盖的简单路径。沿路径取对称差

$$M^{\prime }=M\mathrm{△}E(P)$$

后仍是匹配，且 $|M^{\prime }|=|M|+1$。Berge 定理断言：匹配 $M$ 最大当且仅当不存在 $M$-增广路。

直觉

交替翻转不会使中间顶点获得两条匹配边，却在两个空端点各增加一条匹配边。

例子与边界

一条连接两个未匹配顶点的未匹配边就是最短增广路。交替偶环翻转后匹配大小不变，因此不是增广路。

推论与应用

它是二分图匹配、Hopcroft–Karp、网络流和许多局部改进算法的共同机制。

参考资料

• Reinhard Diestel, Graph Theory, 6th ed. (2025), matchings and augmenting paths.
• Douglas B. West, Introduction to Graph Theory, 2nd ed. (2001), Berge theorem.