Edmonds blossom 算法

形式陈述 ​

输入是有限无向图 $G=(V,E)$ 与当前匹配公理库匹配Matching in a graph任意两条边都不共享端点的边集合。 $M$；一个阶段要么找到一条 $M$-增广路，要么证明不存在。算法从所有未匹配顶点建立交替森林：根为 outer 顶点；从 outer 顶点只沿非匹配边扩展，首次到达的新顶点成为 inner，再沿其唯一匹配边把 mate 加为 outer。若非匹配边连接两棵不同树中的 outer 顶点，两条根路径与该边组成增广路。

若非匹配边连接同一棵树中的两个 outer 顶点 $u,v$，令 $b$ 为它们到根路径的最低公共祖先。从 $b$ 到 $u$、边 $uv$、再从 $v$ 回到 $b$ 形成奇数长度的交替环 $B$，称为 blossom，$b$ 是 base；根到 $b$ 的交替路径是 stem。环上除 base 外的顶点由 $M$ 成对匹配，故把整个 $B$ 收缩为超级点 $\beta$ 后，当前匹配在外部仍合法。

收缩不变量是

$$G\text{ 中存在相对 }M\text{ 的增广路}⟺G/B\text{ 中存在相对 }M/B\text{ 的增广路}.$$

正向证明把增广路与 $B$ 的多次进出简化为至多一次通过，再压成 $\beta$；奇环的两条 base—入口路线奇偶性相反，恰有一条与外部路径交替性相容。反向 lift 时，若收缩图路径不含 $\beta$ 可原样使用；若含 $\beta$，根据进入与离开 blossom 的外边，在环内选择唯一奇偶正确的交替路线连接，并保留端点未匹配。算法递归处理收缩图，lift 后沿增广路翻转匹配边；每次增广使 $|M|$ 增一，至多增广 $\lfloor |V|/2\rfloor$ 次。经典直接实现可达 $O(V^3)$ 时间。

直觉 ​

二分图的交替 BFS 可以给顶点稳定标出奇偶层；一般图中的奇环会让两个 outer 顶点突然相连，同一个区域似乎同时要求两种层次。Blossom 收缩把这段局部奇偶冲突暂时封装成一个点，继续寻找全局出口；找到路线后再按入口位置展开。

不是任意奇环都能收缩。它必须相对于当前匹配和交替森林形成上述 blossom，base、stem 与环上匹配模式共同保证收缩前后增广路等价。

例子与边界 ​

设未匹配根为 $s$，stem 为非匹配边 $s-a$、匹配边 $a-b$。从 outer 顶点 $b$ 沿五环依次走

$$b-c-d-e-f-b,$$

其中 $(c,d),(e,f)\in M$，其余环边不在 $M$。边 $fb$ 连接同树 outer 顶点 $f,b$，形成 base 为 $b$ 的 blossom。若另有未匹配顶点 $t$ 与 $f$ 以非匹配边相连，收缩图中路径 $s-a-\beta -t$ 是增广路；lift 时选择 $b-c-d-e-f$ 这条交替路线，得到 $s-a-b-c-d-e-f-t$。

若从 $b$ 到出口沿错误的短边 $bf$ 展开，stem 末端的非匹配边、环边和出口边可能出现连续两个非匹配边，路径不再交替。Lift 不是任意把超级点换回一圈，而要由入口、出口和 base 的奇偶关系选路。

平行边、自环和嵌套 blossom 需要实现层明确处理；标准简单图版本可忽略前两者，但嵌套收缩仍会出现。每次增广后交替森林和 blossom 结构依赖新匹配，必须重建或等价更新，不能沿用旧层次标签。

推论与应用 ​

由 Berge 定理公理库增广路Augmenting path相对于当前匹配，边在未匹配与已匹配之间交替且两个端点均未匹配的路径。，某阶段若在所有合法收缩后仍找不到增广路，当前匹配即为最大匹配。算法因此把“寻找一般图增广路”的困难全部集中在 blossom contraction 与 lifting 证书上。

二分图没有奇环，outer–outer 同树边不会形成 blossom，算法退化为普通交替森林搜索。加权一般匹配还需要对偶变量、紧边与 blossom 约束；它不是在本页算法上给边排序即可得到。

参考资料

• Jack Edmonds, “Paths, Trees, and Flowers,” Canadian Journal of Mathematics 17, 1965, pp. 449–467.
• Alexander Schrijver, Combinatorial Optimization, Springer, 2003, Chs. 24–25.