blossom · 缩花与展开

一般图最大匹配：blossom

到这一页为止，本系列的匹配都建在二分图上：二分图最大匹配把它归约成单位容量的流网络，带权二分匹配再给边加上权。归约到此为止。一般图的最大匹配没有等价的流模型，因为流网络的可行解天然带着「左右两侧」的结构，而一般图里根本没有两侧可分。

差别的源头只有一个：奇环。整个二分图匹配理论建立在「每个点到根的所有 alternating path 长度同奇偶」之上，奇环让这句话不再成立。本页先看它怎么把搜索带偏，再看 Edmonds 1965 年的修法。

1 · 奇环上失效的奇偶划分

无权匹配的搜索是这样进行的：从一个未配对的点出发，沿未匹配边走一步、再沿匹配边走一步，交替下去，长出一棵 alternating tree。

定义 1.1（even 点与 odd 点） 树上与根的距离为偶数的点称为 even，为奇数的称为 odd。even 点是搜索的前沿，它的每条出边都要检查；odd 点只被穿过，它唯一被用到的边是那条匹配边。找到一个未配对的 odd 位置就意味着一条 augmenting path。

这套划分在二分图上是自洽的：二分图无奇环，从根到任一点的所有路径长度同奇偶，一个点要么永远 even 要么永远 odd，不会两可。而奇环把两条奇偶不同的 alternating path 接到了同一个点上，于是同一个点既该是 even 又该是 odd，搜索却只能给它一个身份。

一个六点的例子把这件事压到最小：三角形 $C D E$ 挂在柄 $R - B - C$ 上，起手匹配是 $B - C$ 与 $D - E$ ，空位是 $R$ 与 $F$ ，而 $F$ 只连着 $D$ 。从 $R$ 搜下去， $C$ 是 even， $D$ 顺理成章被判成 odd， $D$ 的出边一条都不查，挂在它上面的空位 $F$ 永远轮不到。搜索报告「无 augmenting path」，可 $R - B - C - E - D - F$ 明明就是一条：它绕了三角形的另一侧，从 $E$ 沿匹配边进到 $D$ ，那一趟让 $D$ 变成了 even。

图 1-1 · 交替搜索的单步执行，缩花可开可关。可切到二分图样例对照：那里没有奇环，开关拨到哪一侧结果都一样。

关掉缩花究竟错得多厉害，是可以枚举清楚的。把 5 个点以内的全部图跑一遍，不缩花的搜索一次都没出错；6 个点上才出现反例，共 187 个（顶点带标号计），其中边数最少的是 7 条，形态都是两个三角形共用一条边、各挂一条尾巴。本页用的那张双三角形图就取自这一族：最大匹配是 3，不缩花的搜索停在 2。

警示 · 不缩花不等于必然出错。柄挂三角形的那个例子里，从 $R$ 出发会失败，但换成从 $F$ 出发，同一份不缩花的代码一步就走出 $F - D - E - C - B - R$ ，结果完全正确。写这一页时原以为「关掉缩花 = 停在次优解」，实测推翻了这个说法：它给出的是依赖起点的答案。Berge 定理要求的是「不存在 augmenting path」这一全局判据，而不缩花的搜索只对某些起点成立，缩花的意义正是让结论与起点无关。

2 · 把奇环缩成一个点

定义 2.1（blossom） 设 $M$ 是一个匹配。一个长度为 $2k+1$ 的环若含 $k$ 条匹配边，就称为一朵 blossom。环上唯一没有被环内匹配边覆盖的点称为它的 base。

blossom 的关键性质是它内部的自由度：对环上任意一点 $v$ ，都存在一条从 base 到 $v$ 的偶数长 alternating path。奇环两侧的长度一奇一偶，总有一侧走得通。换句话说，环上每个点都能以 even 的身份被到达，所以「这朵花该算 even 还是 odd」这个问题本身就问错了：它整体是 even 的。

Edmonds 的做法顺着这句话来：把整朵花缩成一个点，记作 $G/B$ ，环内的边随之消失，环上各点原有的对外的边都挂到这个缩点上。 $M$ 也跟着缩成 $M/B$ ：环内那 $k$ 条匹配边一并消失，base 原有的那条对外的匹配边（若有）保留。

定理 2.2 设 $B$ 是关于 $M$ 的一朵 blossom。若 $G/B$ 上存在关于 $M/B$ 的 augmenting path，则 $G$ 上存在关于 $M$ 的 augmenting path。

证明设 $P'$ 是 $G/B$ 上的一条 augmenting path。若 $P'$ 不经过缩点，它的每条边都是 $G$ 的边，直接就是 $G$ 上的 augmenting path。若 $P'$ 经过缩点，它在那里至多用两条边：一条来自 $M/B$ 、一条不属于 $M/B$ ，而来自 $M/B$ 的那条只能是 base 的对外匹配边。设不属于 $M/B$ 的那条边在 $G$ 中的实际端点为环上的 $u$ 。把 $P'$ 中的缩点替换成 base 到 $u$ 的那条偶数长 alternating path：它以未匹配边收尾于 $u$ ，与 $P'$ 在 $u$ 处接的那条非匹配边不冲突；它在 base 处以匹配边或路径端点收尾，与另一侧同样相容。替换后的点列在 $G$ 中匹配与非匹配交替，两端仍是未配对点，即一条 augmenting path。∎

反方向同样成立，即 $G$ 有 augmenting path 时 $G/B$ 也有，两边合起来才使缩花无损。那一半的论证要细致得多，也是 Edmonds 那篇论文的技术核心 [1]。

3 · 展开的代价

实现上的一个意外是：缩花要写代码，展开不用。算法并不真的构造 $G/B$ ，它只维护一个 base 数组，把环上各点的 base 全部指向同一个代表；「两端同 base 的边跳过」这一句就等价于删掉环内的边。原图的点和边一直都在，也就没有什么需要还原。

真正让展开发生的是 parent 指针。缩花那一步会把环上各点的 parent 沿绕行方向重写一遍，后来沿 parent 回溯出来的路径便自动是穿过环的那条偶数长的一侧。定理 2.2 证明里的「替换」在代码里没有对应的语句，它已经在缩花时提前做完了。

图 3-1 · 左右并排给出原图与缩图。缩花那一帧右侧的三个点并成一个，增广那一帧左侧展开出完整路径、右侧只剩一段，两条路径的对照就是「缩」与「展」的全部内容。

每次成功的增广让匹配数加一，故至多 $O(V)$ 轮；每轮的搜索最多缩 $O(V)$ 次花，每次缩花要扫一遍 base 数组。朴素实现是 $O(V^3)$ ，本页的引擎就写成这样，因为样例只有六个点，把 base 的更新写成一次全扫比写并查集更容易对着帧读。用并查集维护 base 可以降到 $O(VE\alpha(V))$ ；再往上是 Micali 与 Vazirani 的 $O(E\sqrt{V})$ [3]，它把 Hopcroft-Karp 的分阶段思想搬到了一般图上，代价是实现复杂度陡增。

4 · 存在性判据与构造算法

一般图的匹配理论有两条并行的线索，本页只走了其中一条。

matching · Hall / König / Tutte 那页给的是判据：Tutte 定理说 $G$ 有完美匹配当且仅当对任意顶点集 $U$ 都有 $o(G - U) \le |U|$ ，其中 $o(\cdot)$ 数的是奇数阶连通分支。它回答「有没有」，回答得干净利落，却不给出任何一个匹配；而且要用它证明「没有」，得先找出那个见证的 $U$ 。本页的缩花算法回答的是「拿出一个来」，它构造出最大匹配本身，顺带也就证明了存在性。两者的分工与 Hall 定理和 Kuhn 增广的分工是同一种。

奇环在这两条线索里造成的破坏也是同一处。König 定理在二分图上把最大匹配与最小点覆盖钉成相等，一个三角形就让它失效：最大匹配 1，最小点覆盖 2。同一个三角形在本页让 even 与 odd 的划分失效。二分图的种种好性质，追到底都是「没有奇环」这一条的推论。

5 · 参考文献

Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics, 17, 449–467.
Tutte, W. T. (1947). The factorization of linear graphs. Journal of the London Mathematical Society, s1-22(2), 107–111.
Micali, S., & Vazirani, V. V. (1980). An $O(\sqrt{|V|}\,|E|)$ algorithm for finding maximum matching in general graphs. Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 17–27.