Edmonds blossom 算法 | Codeboy's Blog

形式陈述

输入是有限无向图 $G=(V,E)$ 与当前匹配 $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{ 的增广路} \Longleftrightarrow 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 与环上匹配模式共同保证收缩前后增广路等价。

Edmonds blossom 从五环收缩为 β，再把 s-a-β-t 提升为增广路 — Blossom 收缩与 lift

例子与边界

设未匹配根为 $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 定理，某阶段若在所有合法收缩后仍找不到增广路，当前匹配即为最大匹配。算法因此把“寻找一般图增广路”的困难全部集中在 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.

形式陈述 ​

反向链接

形式陈述