• Introduction
• max-cardinality matching problem
  • augmenting path
  • blossom
• max-weight matching problem
  • Theorem
  • Algorithm
• Q&A on MWM algorithm
  • Facts
  • Questions
• Reference

Introduction

最近由于读到旅行商问题的近似算法，其中用到了寻找图的最大权重 matching 可以在多项式时间解决的结论。于是想看下，实现这个的算法是什么，想不到结果表明这个结论的实现和证明比旅行商问题近似算法本身要复杂多了。虽然有一些资料讲解最大权重 matching 算法，但都没有给出伪代码，在某些细节上也有些语焉不详。因此决定自己亲自实现一遍，踩一遍坑，以对这一算法有更好的理解，于是有了这个工作：github repo。在这篇文章里，我将对自己初读算法时产生的一些疑问进行反思和解答，因此这里更多的是关注算法的正确性证明。至于实现的细节可以自己去上边的 repo 读代码。当然我自己的实现没有用诸如魔改的 heap 之类的数据结构进行优化，只利用了普通的 array 和 dict 记录相关信息，因此算法的复杂度并不是最优的，如果是生产环境需求请寻找其它更成熟的实现，本实现更多的是教学意义。

max-cardinality matching problem

所谓 matching 就是给定无向图的一些边，从而使得每个顶点的边不超过一条。而所谓 max-cardinality matching (MCM) 就是从 matching 中找出 cover 图顶点最多的一个 matching （显然可能不唯一）。解决这一问题的算法即是 Edmonds’ Blossom 算法。

augmenting path

首先我们需要引入 augmenting path 的概念。 augmenting path 是指的图中一系列相连的边组成的 path，该 path 的两个端点不在给定的 matching 内，而 path 的总共奇数条边按照不在 matching，在 matching，不在 matching 这样的顺序交替排列。显见当我们把这一 path 的所有边是否在 matching 进行交换时，我们就得到了一个新的 matching， 而且比之前的 matching 多 cover 了两个顶点，多包括了一条边。因此我们只需要在图里寻找 augmenting path，并交换 path 上边的 matching 属性，就可以逼近 MCM。

而想要靠这样做彻底得到 MCM，就需要证明 MCM 和图中没有 augmenting path 等价。其中 MCM 推导出没有 augmenting path 是显然的，否则通过该 path 交替生成的新 matching 包含的顶点更多，矛盾。想推导出没有 augmenting path 即为 MCM 则比较困难。我们证明其等价的逆否命题：若不是 MCM 的 matching，则一定有 augmenting path。做法是考虑现在非 MCM的 matching M 和 MCM M’ 的并集，这一并集中每个点的度数最大为2（两条边分别来自两个 matching）。考虑并集图中连通的各部分，每部分只有三种可能：

1. 偶数个边组成的在 M，M‘ 边交替的环。（当边数为 2 时，表示一条边既在 M 也在 M’）
2. 偶数个边组成的在 M，M‘ 边交替的路径。
3. 奇数个边组成的在 M，M‘ 边交替的路径。

注意的奇数个边组成的环是不可能的，这会导致某个顶点出发的两条不同的边同属于一个 matching，违背了 matching 的定义。考虑到 M’ 是 MCM，所包含的边总数严格大于 M，而各连通部分对应的处于 M 和 M’ 的边数相同，除非情况3打破这种对等。因此3一定出现，而3描述的恰好是 M 的 augmenting path。证毕。

于是我们只需要做一个循环，每一轮基于图现在的 matching 找到一条 augmenting path，如果存在，就交替更新 path 上的 matching 状态，如果不存在就 claim 找到了 MCM。而寻找 augmenting path，可以利用图的遍历搜索。一种简单的实现是，先将所有自由顶点（没被现在的 matching cover 的顶点）u 作为森林的树根，然后进行广度优先搜索。对于 u 的相邻顶点 v，如果其不在森林（意味着其处于现 matching），则将其加入森林，同时将其在 M 的边连接的顶点 w 加入森林。我们称 u 和 w 这种出现在树高偶数层（0，2）的顶点为偶顶点，而 v 则是奇顶点。沿着树生长的方向，所有偶奇边都不在 M，所有奇偶边都在 M，由此通过广度优先搜索（只将新的偶顶点压入待查队列中），自然形成了一系列类似 augmenting path 的树。直到我们尝试搜索某个偶节点时发现其对应的边连接到了森林中的另一颗树上，如被连接的顶点也是偶节点，则一条从树根通过跨树桥（不在M）到另一条树根的路径就形成了，这一路径符合 augmenting path 的所有定义。但如果我们搜索完所有节点，还没找到这样的 path，就代表现在的 M 即是 MCM。

blossom

以上想法，在解决 bipartite 图的 MCM 时就出现了，并且成功解决了 bipartite 图的 MCM 问题。但人们发现对于一般的图，以上简单的搜索存在错过 augmenting path 的可能性。人们发现把简单的广度优先遍历拿来寻找 augmenting path，在一般图的情形下，可能无法找到某些 augmenting path。

考虑如下的图，其中曲线代表现在的 matching，最下边的 s 是一个树根自由节点，图中的 S 和 T 对应我们上文的偶顶点和奇顶点（之后会混用这两种说法）。当我们的树根据搜索生长到节点 j 时，其作为 S 顶点，也要进行搜索，当其搜索到边 ji 时，由于刚才解决 bipartite 的想法对这种情形不予考虑，因此什么都不发生。但注意到顶点 e 作为 T 类顶点，不会进行搜索，那么我们实际上就漏掉了 sarbcdijeh 这一 augmenting path。

为了解决这一问题，Edmonds 最精彩的贡献就体现在算法的名字里，即引入了 blossom 的概念。如果我们搜索到 ji 边时，发现该边连接到了同属一棵树的 S 类节点，此时我们就将从 ij 两顶点最近的共同祖先开始的环打一个包，称作一个 blossom，在图中即为 B 圈起的部分。如果我们将给部分视为一个 effective 的顶点，由于该顶点是 S 类，打包后即可直接从该顶点继续搜索，那么很容易发现 saBh 这一 augmenting path，只需我们找到 path 后在将 blossom （这一过程可能迭代存在若干嵌套的 blossom）适当的“展开”，即可还原对应最初图的一条 augmenting path。事实上，通过对 bipartite 算法未处理的搜到已在森林中的顶点的可能性的简单列举，可以发现，只有 blossom （同树 SS 节点连接）这一种情形会产生原算法无法找到的 augmenting path。通过对 B 的观察，我们可以抽象出 blossom 的特点：包含的顶点形成奇数条边组成的环，其中边在 M 和不在 M 交替，除了唯一的一个顶点出发的两条边均不在 M，我们称该顶点为 blossom 的基点。

对于 blossom 以压缩展开处理的正确性依赖于以下定理：若 G‘ 是 G 压缩 blossom B 后形成的图，则 G 有 augmenting path 等价于 G’ 有 augmenting path。证明前，我们先明确一下 Blossom 压缩和展开的细节。压缩时，若原来存在边从 B 外到 B 内某点，则压缩后存在 B 外到 B 的边。一个细节就是，B 最多有一条在 M 中的边，注意压缩时对该边的保留。换句话说，压缩时可能存在边决定的歧义性，比如上图，如果本来从 a 到 b 有另一条边的话，那么压缩时就面临决定 ar 和 ab 谁来代表 G‘ 的新边 aB 的问题。这里我们引入第一个边合并原则：匹配边（即处于现在 matching 中的边，之后两概念混用）优先于未匹配边。如果希望压缩 B 后，搜索不从头再来，就还要处理树的结构，此时有第二个边的合并原则：树内边优于不在森林中的边，这是为了压缩后最大限度保持原来的树结构。

至于展开时，由于我们记录有基点的信息，因此其内部边的匹配性都可以复原，而其中顶点和 B 外部顶点的边的匹配性，只存在至多一个匹配边的复原问题，该边复原时对应的内部顶点只能是基点（其它点都有匹配边）。由此边的匹配性质在展开 B 时不会有任何问题。当然 B 内外边复原时，对于 augmenting path 究竟出现在哪条边上可以有一定的自由度，只要最后找到一条 augmenting path，这一自由度就不会造成什么困扰。而对于，augmenting path 的复原也比较简单。稍作思考就知道只有一条沿着环的路径可以插入到 G‘ 的 augmenting path 上。唯一需要指出的是，当 B 处于 G’ 的 augmenting path 的端点时，路径的复原到基点截止（这恰好是一个自由顶点）。最后注意到当图复杂到 blossom 出现嵌套时，展开和压缩都是迭代进行，本质上不会引入新的困难。

事实上，当我们上面详述完 blossom 的压缩展开规则，上面定理也基本证明完毕了。这一定理的证明实际上就是通过类似算法的构造性叙述证明的，该定理同时保证了 blossom 算法的正确性。至此就完全解决了 MCM 问题（更多数据结构上的复杂度优化不再赘述）。

max-weight matching problem

Theorem

当我们考虑无向图具有不同的边权重时，我们可以提出一个类似于 MCM 的优化问题，依旧是寻找 matching，而这次我们希望最大化在 matching 中所有边权重之和，这种 matching 称为 max-weight matching (MWM). 需要注意 MWM 并不一定是 MCM 中的一个，实现权重和最大并不总是同时实现了包含的顶点最多。以下叙述，都默认边权重为正数（weight 非正的边可以直接去除）。

想解决这一问题，需要一些线性规划对偶问题的启发，不过我们也可以直接定义一些量来解决问题，下面就来定义 MWM 问题中的核心变量 z。z 定义在所有的图顶点的奇数顶点的子集上（元素为1的子集即为这些顶点本身）。也就是说对于任何顶点的集合，只要元素数是奇数，我们就可以定义一个数，比如 \(z_v=2,z_B=3\) 其中 \((B=\{v_1,v_2,v_3\})\) 等。有了 z 我们还可以计算对应每条边上的 z 值，该值的定义是 \(z_{e=(u,v)}=z_u+z_v+\sum_{B:z\in B} z_B\)。也即边上 z 的定义是两个端点的 z 值加上所有包含改变的奇数集合上的 z 的和。我们可以证明以下三个条件同时满足时的 matching 就是 MWM：（定理）

1. \(z_e\geq w_e\) 对于任意边 e
2. \(z_e=w_e\) 对于 matching 的边 e
3. \(z_B =0\) 对于不在 matching 的顶点，和一切具有 2k＋1 顶点而匹配边小于 k 个的集合 B

证明很直接，对于任意 matching N：

\(\sum_{e\in N} w_e \leq \sum_{u\in V} z_u +\sum_{B:\vert B\vert>1} z_Bk_B\)，

而对于 MWM M：

\(\sum_{e\in M} w_e = \sum_{e\in M} z_e = \sum_{u\in V} z_u +\sum_{B:\vert B\vert>1} z_Bk_B\)。

连接两个式子即可得出 M 给出最大权。最后一个等号成立是因为，如果 M 没包含的节点，自动 z 为0，因此还是相当于对于所有 V 求和，第二项依旧是对于所有 B 的求和的分析相同，都是基于上面的条件 3。

z 的规范：从现在起我们考虑这样的 z 定义，对于一切非 blossom 结构的子集 B，如果 \(\vert B\vert>1\)，则 \(z_B=0\)。

基于以上关于 z 的规范，我们依旧保持 augmenting path 的定义不变，这里很容易证明，对于 augmenting path 的匹配未匹配边交换，依旧会导致 matching 总权重的增加，这一点在 blossom 存在时依旧成立。

Algorithm

算法开始，我们将所有的顶点的 z 值初始化为整个图最大权重的一半。再结合上面 z 的规范，可以看出 z 直接满足条件 1，2 和 3 的后半部分（blossom 中的匹配边一定是 k 个）。我们现在唯一违反的就是对于一切未匹配节点，z＝0 这一条件。通过算法保持其他条件的同时，实现这一条件，即找到了 MWM。

算法由一个循环部分组成，每次运行称为一个 phase，任务是找到一条 augmenting path 并且交替更新 matching。一个 phase 的第一部分和上面的 Edmonds’ 算法类似，但需要注意我们不能利用所有的边来生长树，因为匹配的边具有 \(z_e=w_e\) 的性质，要想保持该性质，就要使得 augmenting path 上的所有边都是“相等边”（满足 \(z_e＝w_e\)），因此存在在第一部分无法找到合适的 augmenting path 的可能。注意到由于相等边的 issue，当 phase 第一部分结束时，顶点除了处于 S 和 T 状态还可能在 F 状态，这种状态的节点不和任何树通过相等边连通，因此成为孤立点，由于森林顶点就是所有未匹配节点，则 F 顶点一定是已匹配顶点（注意区分孤立顶点和未匹配顶点，两概念恰好相斥）。

更重要的是，当找到 augmenting path 之后，与 MCM 算法先展开 blossom 之后交替更新 matching 不同，这里由于 z 值非0的 blossom 影响对边的 z 值的评估，因此只要 z 不为 0 的 blossom 始终保留。所以这里是保留 blossom 直接进行交替更新 matching，需要注意这样做之后， blossom 的基点可能发生了变化，这在 blossom 展开时要格外注意。由于 blossom 可以带到下一个 phase，虽然所有新产生的 blossom 都是 S 类型，但下一轮这一所谓的最外层的 blossom（因为其可能存在 blossom 的嵌套）就相当于 reduced 图的一个节点，因此 blossom 可以获得 S，T 或者 F 的标记。

phase 的第二阶段就是更新 z 值，这一步的终极目的是使得自由节点的 z 降到 0。做法是算出一个 \(\delta\) 值，然后使所有节点（所有最初始的节点，不管其是否被包括在 blossom 中从而已不在 reduced 图中）中的 S 节点 \(z_S = z_S-\delta\) ， T 节点 \(z_T=z_T+\delta\)。我们之所以对 S 节点进行减法，是因为未匹配顶点一定是 S，我们期望这些顶点的 z 到 0，因此做减法。同时，对于处在最外层的 blossom，若为 S，则 \(z_B = z_B+2\delta\)， T-blossom 则相反。这样的和所有原始顶点的反向操作，保证了所有处于 blossom 中的边依旧保持相等性。（注意到blossom 生成时其中的环上均为相等边）。原因在于，顶点的标记和最外层的 blossom 保持一致，对于一个 S-blossom，其中的边两个端点都为 S 顶点，因此该边的 z 根据边上 z 值的定义减少的部分（来自顶点）和增加的部分（来自 blossom）刚好抵消，使得 blossom 中的环上的边始终保持在相等边的状态。

最后我们给出 \(\delta\) 的计算规则。首先我们计算 \(\delta_1\) 到 \(\delta_4\)，然后取它们中的最小值。它们分别对应 (以下顶点均指原始图的顶点)

1. S 顶点 z 的最小值
2. 从 S 到 F 顶点的边，z-w 的最小值
3. 从 S 到 S 顶点的边，且该边不处于任何 blossom，(z-w)/2 的最小值
4. T-blossom，z/2 的最小值

当我们完成一次权重调整时，若是情况1最小，算法结束，claim MWM 已找到。若是 2，3最小，出现新的相等边，回到阶段一，继续树的生长，若是 4 最小，出现 z=0 的 T-blossom，展开，回到阶段一。对于这些的具体分析将在下一节进行。

最后还是一些 blossom 展开收缩的细节。首先每个 phase 结束，所有 z=0 的 S-blossom 会展开。所有计算结束，展开所有 z 非0 的 blossom，以显示完整的 matching。在 blossom 的压缩时，引入第三个边的合并原则：相等边优先于不等边。在该问题中展开或压缩 blossom，需要同时注意如何更新 z 值，匹配边，相等边，augmenting path，树的指针，是否搜索过的标记，S T F 的状态标记。这些量之间又相互影响制约，同时存在各种 corner case，使得 blossom 的压缩和展开（尤其是展开）正确实现起来比较困难，这部分的细节可以参考文章开头给出 repo 的代码。

Q&A on MWM algorithm

看了以上算法，你可能有很多疑惑。这节我将对一些常见的问题，进行详细的分析。

Facts

先列举一些事实。

1. 顶点匹配有去无回

   一个未匹配的节点在某个 phase 被包括进 augmenting path 更新后，不会再变回未匹配。因为通过 augmenting path 的方法，只会包括进新顶点。

2. 未匹配顶点总是 S，且 z 值始终保持一致，并且是 S 里最小的部分

   由于匹配顶点有去无回，那么任何时刻的未匹配顶点，总是来自最开始的未匹配顶点，它们始终保持在 S 状态，因此每次 z 值更新时，经历的变化都一样，因此 z 值始终一致。又由于 \(\delta>0\)，而 S 类型节点始终减去该值，因此未匹配顶点作为每次调整都是 S 的角色，自然 z 值是任意时刻任意顶点中最小的。

3. 所有顶点和 blossom 的 z 值总是非负的。

   权重调整保证了这一点。尤其是 \(\delta_1,\delta_4\)。

4. 每个 phase，F 顶点变非 F 不可逆。

   显然。

5. 所有 blossom 产生压缩时都是 S-blossom。

   根据树的生成过程，显然。

Questions

现在看一些问题：

1. 两个算法为什么非得考虑 blossom？

   答案在第一部分叙述过了，因为不然注定会漏掉 augmenting path。

2. 为何 MWM 算法 blossom 的基点会变，而 MCM 算法不会？

   因为根据 augmenting path 更新 matching 和展开 blossom 的顺序反过来了，这是为了继续保留 z 非 0 的 blossom 用于图的边上 z 的评估。

3. 初始顶点 z 的初始化可不可以按照自己发射边的最大权的一半来做？

   看起来每个顶点的 z 都取成全图最大权重的一半有点浪费，实际上只取成自己连接边的最大权的一半，就满足了条件 1和2，并且似乎离正解更近些。但这样是不行的！请返回看事实3。所有未匹配顶点的 z 值始终一样，是我们最后成功的关键，否则很难将它们的 z 分别降到 0。

4. 为何只用相等边分析？

   根据定理条件2，不是这种边没有成为matching的资格，选了一旦更新 matching，条件 2 就违反了。

5. 为何遇到一次 \(\delta_1\)，算法就结束？

   回看事实3，一旦 \(\delta_1\) 最小，所有 S 的 z 减去该值，则所有未匹配顶点的 z 为 0，鉴于这是以前唯一违反定理的条件，现在被满足，则根据定理说明 MWM 已找到。

6. 为何是偏偏是这四个\(\delta\)？

   好问题！事实上，我们只想要第一个 \(\delta_1\)，这是我们满足定理条件努力的方向。但同时记得我们要保持其他定理的条件不被违反。考虑不同类型的边 TS （z 调整后不变），TT （只可能出现在同一最外层 blossom 中，z调整后不变），TF（这种边调整不会违反条件1，但存在把相等边变为不相等的可能，但这个边不在匹配上，也不违反任何原则），FF （z 不调整），这样还可能有影响的只剩下 SF 和 SS。为了使这两种边上的 z 不违背定理条件，我们定义了 \(\delta_2,\delta_3\)。或者 z=0 的 blossom 是没有保留的意义的，我们也很乐意把对应的 blossom 展开。

7. 那为何 \(\delta_4\) 只考虑 T-blossom? S 呢？

   因为只有 T-blossom 的 z 才在更新时减小，S 型 blossom 不可能权重调整后 z 变 0。

8. 那什么时候展开其他类型的 z＝0 的 blossom 呢？

   在每个 phase 结束，找到一条 augmenting path 并更新 matching 后，展开所有 z＝0 的 S-blossom。F-blossom 呢？F 一定在某个之前的 phase 变为 F 之前是 T 或 S blossom，那时没被展开，说明 z 非0。而变为 F 后，z 不再调整，因此z一定不是 0，不用展开。T-blossom 呢？分析同理，之前一定是 S ，当时没被展开，说明 z 非0。而此时该 phase 中唯一可以归0的权重调整过程已过，如果归 0 那时就展开了，既然没有，说明 phase 结束时 T-blossom 的 z 也非0。

9. 为何这算法一定会结束？

   考虑到每个 phase 对 matching 的更新会导致两个顶点成为匹配顶点，因此算法至多 n／2 （n为顶点数目）phase 就会结束（此时可能四个 \(\delta\) 均无定义，实际上相当于未匹配顶点为 z＝0 自动满足）。对于每一个 phase，考虑权重调整这一过程可以出现的总次数。每次 \(\delta_2\) 最小，都会出现一个新标记为 T。每次 \(\delta_3\) 最小，要么直接 phase 结束，要么生成一个 S-blossom。每次 \(\delta_4\) 最小，都会减少至少一个 T-blossom。由于 reduced graph 最多有 n 个顶点，而上述的展开 T-blossom，生成 S-blossom （S 不会在 phase 中转为 T-blossom）都不可逆，因此最多 \(O(n)\) 次权重再调整一定能结束一个 phase。

10. 如果 \(\delta_{2,3,4}\) 中有一个给出0，岂不陷入死循环了？

    好问题！逐个考察，2 是 SF 边，这种边一定不是相等边，否则直接把 F 和其匹配顶点插入到 S 树上即可，F标记变为T。3 是 SS 边，一定也不是相等边，否则 SS 直接就是 augmenting path，不需要拖到权重调整阶段。因此 2，3 给出的最小值一定大于 0。至于 \(\delta_4\)，如果更新前 z 就是0，那么该 blossom 已经应该被展开了，不会存在，因此最小值也大于 0。

11. 算法结束时一定没有 z 非零的 Blossom 吗？

    否。可以有，只需最后展开，还原全部 matching 即可。此时的展开，除了 matching 还原外，其他属性都可以不管了。

12. 算法复杂度是多少？

    参考问题 9 的分析，对于存在多少phase，每个 phase 有多少再调整数数手指就差不多了。当然每一步不同的数据结构，可能导致复杂度有区别，反正是多项式级就是了。我的最粗糙实现是 \(O(n^2m)\)。

Reference

• Paths, Trees and Flowers (Edmonds’ original work)
• Edmonds’ Blossom Algorithm: project report
• Edmond’s Blossom Algorithm: demo and explain
• Advanced Data Structures and Algorithms
• Weighted Matching Lecture
• Maximum matching implementation
• Efficient Algorithms for Finding Maximum Matching in Graphs

EOF