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$ 后，当前匹配在外部仍合法。

收缩不变量是

先看从收缩图到原图的 lift。若增广路不含 $\beta$，原样保留。若包含它，路径在 $\beta$ 的一条外边非匹配，记其原端点为 $v\in B$。环上从 base $b$ 到 $v$ 有唯一的偶长度交替路线，非空时首边非匹配、末边匹配；$v=b$ 时取空路线。若 $\beta$ 是未匹配端点，则 $b$ 也未匹配，直接从 $b$ 沿这条路线接出去；若 $\beta$ 位于路径内部，其另一条外边必为匹配边，并且只能接在 $b$，仍能交替接合。收缩图中的路径简单，所以外部部分不会与环内顶点重复。

反方向的存在性证明还要处理 stem，不能只把任意路径的所有进出压成一个点。沿偶长度 stem 翻转得到 $M^{\prime }=M\mathrm{△}E(stem)$，匹配大小不变，base 变为未匹配点；环内匹配保持，故 $|M^{\prime }/B|=|M/B|$。若 $M$ 非最大，则 $M^{\prime }$ 也非最大，由 Berge 定理有一条 $M^{\prime }$-增广路。若它不碰 $B$，可直接留在收缩图；若碰到 $B$，从一个位于 $B$ 外的未匹配端点走到第一次进入 $B$ 为止，便得到通向未匹配超级点的增广路。进入边非匹配，因为 $M^{\prime }$ 中的环内顶点只在环内匹配，base 则未匹配。于是 $M^{\prime }/B$ 非最大，同大小的 $M/B$ 也非最大，再由 Berge 定理得到所需的收缩图增广路。

算法在收缩图继续搜索，按收缩的逆序 lift，再沿原图增广路翻转；每次匹配大小增加一，至多增广 $\lfloor n/2\rfloor$ 次。经典 $O(n^3)$ 实现隐式维护 blossom 的 base 代表、交替父链与待扫描顶点：一次搜索扫描 $O(n^2)$ 对端点，至多 $O(n)$ 次收缩各花 $O(n)$ 更新代表与父链，从而每阶段为 $O(n^2)$。每次收缩都复制并重新搜索整张图的朴素递归版本，不能直接继承这个实现界。上述隐式稠密实现保存 $O(n^2)$ 个邻接项，以及共 $O(n)$ 个 base、parent、match 和队列记录；顶点标识与索引各占一个机器字时，这也给出相应的字空间界，无需另存逐层复制的收缩图。