「from CommonAnts」无向图最大匹配

liu_cheng_ao 2017-05-28 10:42:38 2019-10-23 14:09:29

本文主要内容是带花树算法及判断点/边是否可能/一定在最大匹配中的讲 (kou) 解 (hu)

欢迎转载,荣幸之至。

以下是吐槽,建议跳过


以前一直不会一般图最大匹配(被带花树相关的江湖传说吓怕了),直到冬令营听了假老师讲的线性代数一般图匹配…… 当时我 Naïve 地认为带花树不用学了……直到 CTSC 的时候,我试图写这个东西,才发现原来是个大坑……

线性代数一般图匹配虽然听起来高端,但由于它把问题一般化了很多,导致出现了一些麻烦……

  • Tutte矩阵有特殊性质,然而很难利用
  • 是个蒙特卡洛算法,需要拼 RP
  • 带权的情况下复杂度会卡到指数级(和权值相关)
  • 常数比带花树大几十倍到上千倍,UOJ上「一般图最大匹配」模板题中,最慢的带花树(#70415 1315 ms)比最快的线性代数做法(#127383 5346 ms)快 4 倍多
  • 全是矩阵带模运算,调试困难
  • 代码比带花树长

调了一下午输出方案都没弄出来的蒟蒻表示玩不动线性代数做法,只好去学带花树了。

当然线性代数做法在可扩展性上优势还是很大的(比如求某条边/某个点是否一定/可能在最大匹配中,以后再说)。
不过图论做法也可以求这个……


#### 以上是吐槽,建议跳过

以下是正文

好,我们开始正题:带花树。

前置技能:基础集合知识;基础图论知识。

带花树算法(Blossom algorithm)是用来求解一般图最大匹配的(废话)。

我们首先重申几个定义和符号:
对于一个无向图 G=(V,E) ,匹配 M 是一个边集,满足:

  • M\subset E
  • M 中任意两条边没有公共顶点。

G 的最大匹配指使得 |M| 最大的匹配。

一个点 v 称为匹配点,当且仅当存在一条边 e\in M 使得 v e 的一个端点。反之,称 v 为未匹配点。
S(M) 表示 M 的匹配点集合。

交替路是一条非空路径 P ,满足:对于 P 中任意两条有公共顶点的边,都有恰好一条属于匹配 M
增广路是一条交替路 P ,满足: P 两端的点都是未匹配点。
交替环是一个环 R ,满足:对于 R 中任意两条有公共顶点的边,都有恰好一条属于匹配 M

集合运算符号 对称差(俗称:异或并 二元运算,由恰好属于两个集合其中之一的元素组成的集合) \Delta A \Delta B=(A \setminus B)\cup (B \setminus A)

关于图的匹配,有一个基础的定理:
引理 1 增广路引理(Berge's lemma) 匹配 M 是无向图 G 的一个最大匹配,当且仅当 G 中不存在增广路。
证明:
必要性:若 G 中存在一条增广路 P ,则取 M'=M\Delta P ,可知 |M'|=|M|+1 ,与 M 是最大匹配矛盾。
充分性:若 G 中存在一个匹配 M' 满足 |M'|>|M| ,则取 M''=M'\Delta M ,则可知 G 的子图 G'=(V,M'') 中每个点的度不超过 2,且相邻两条边必分别属于 M M' ,故 G' 中仅存在偶环,独立点和链。独立点和偶环中属于 M' 和属于 M 的边数相等,又由 |M'|>|M| ,至少存在一条长为奇数的路径(链) P 使得两端的边均属于 M' ,则两端点对于 M 均是未匹配点,故 P M 的一条增广路。
这个引理是以下匹配算法的基础。

由该引理及证明可以得到几个推论:
推论 1 若最大匹配 M 中有一条偶数长度的交替路或交替环 P ,则可由此构造一个最大匹配 M'=M\Delta P 。证法同上。
推论 2 M M' 是两个最大匹配,则 M\Delta M' 由交替环和偶数长度交替路组成。证法同上。
推论 3
e 属于所有最大匹配,当且仅当对于某一个最大匹配 M (任何一个都可以), e\in M 且不存在含 e 的偶数长度交替路或交替环。
e 不属于任一最大匹配,当且仅当对于某一个最大匹配 M (任何一个都可以), e\notin M 且不存在含 e 的偶数长度交替路或交替环。
e 可能但不一定属于最大匹配,当且仅当对于某一个最大匹配 M (任何一个都可以),存在含 e 的偶数长度交替路或交替环。
证法同上。
推论 4
v 在所有最大匹配中是匹配点,当且仅当对于某一个最大匹配 M (任何一个都可以), v\in S(M) 且不存在以 v 为一端的偶数长度交替路。
v 不是任一最大匹配中的匹配点,当且仅当对于某一个最大匹配 M (任何一个都可以), v\notin S(M) 且不存在以 v 为一端的偶数长度交替路。
v 可能但不一定是最大匹配中的匹配点,当且仅当对于某一个最大匹配 M (任何一个都可以),存在以 v 为一端的偶数长度交替路。
证法同上。
**这样,我们可以通过构造出任意一组匹配方案,来判断某条边(或某个点)是否一定/可能/不可能在最大匹配上(或是最大匹配中的匹配点)。**方法在后面介绍。

根据增广路引理,我们可以得到求无向图最大匹配的增广路算法:

输入:图 G=(V,E)
输出: G 的一个最大匹配 M

函数 最大匹配(无向图 G=(V,E) )
M=\emptyset
\forall v\in V 执行
如果 v\notin S(M) \exists 一端为 v 的增广路 P
M\leftarrow M\Delta P
结束 如果 结束 执行
返回 M
结束 函数 最大匹配

这个算法正确是因为对于一个匹配 M 和一条增广路 P ,设 M'=M\Delta P ,则有 G(M)\subset G(M') ,具体来说, G(M')=G(M)\cup P 的端点。
故一个已匹配的点不会被扔出匹配,每个点只需遍历 1 次。

现在的问题在于如何找一端为点 v 的增广路。

一个朴素的想法是从点 v 开始搜索,使得搜索树上交替出现匹配边和未匹配边。如果搜到了一个未匹配点,我们就找到了一条增广路。
我们把这棵搜索树称为交替树,如图(本文中的图,如不特殊说明,用粗线表示匹配边,用实心点表示匹配点,反之用细线和空心点表示):
match1.png
图中用红线标出了一条增广路。
首先我们可以发现交替树的一个性质:由于匹配边没有公共点,交替树的所有分叉都在偶数层
我们把交替树上除根以外偶数层(根算第 1 层)的点称为 S 型点(未盖点,即不是通过匹配边找到的点),偶数层的点称为 T 型点(已盖点,即通过匹配边找到的点)
显然, T 型点是匹配点,而一个未匹配的 S 型点的到根路径都是增广路。

那么,是不是只要有从根出发的增广路,就一定能找到一个未匹配的 S 型点呢?如果是,我们只要直接搜就好了。
显然对这个问题的答案有影响的只可能是非树边。由于从一个点出发至多有一条匹配边,从 S 型点出发不可能有非树边。
考虑从 T 型点出发的边:如果另一端是 S 型点,则我们找到了一个偶环(交替环),设为 R 如果存在一条增广路 P 包含这条边,则 P'=P\Delta R 也是交替路,且 P' 没有包含这条非树边,也没有引入其它非树边。故这条非树边对是否能找到一条增广路没有影响,如图。
match2.pngmatch3.png

G 是二分图,只有偶环,故交替树搜索中出现的所有非树边都是从 T 型点连向 S 型点,这时我们可以忽略所有非树边,直接搜索,若找到未匹配的 S 型点,则该点到根路径就是增广路,否则增广路不存在。
这个算法称为匈牙利算法(Hungarian algorithm)
时间复杂度:设 |V|=n,|E|=m ,最多增广 O(n) 次,每次搜索复杂度 O(n+m) ,总复杂度 O(n^2+nm)=O(nm) 。(为了简便我们认为 m=\Omega(n)
这样,我们有了一种解决二分图匹配的算法。

如果非树边是从 T 型点连向 T 型点呢?直接忽略?
match4.png
直接忽略考虑不到这样的增广路,这可怎么办?

可以发现:对于这样的环(交替树上的奇环),如果存在一条从环上一点出发的到未匹配点(不包括根)的奇交替路,一定存在一条增广路
match5.png
首先,如果这条路径再次经过了这个环,则只要取其最后一次离开这个环之后的部分即可(显然仍是到未匹配点(不包括根)的奇交替路)。现在只要考虑离开这个环之后不会再次经过的情况。

  1. 路径从环的根(搜索树上环中最浅的点)出发。则这个环没有影响。(参见上图蓝色部分)
  2. 否则,考虑两条从根到奇交替路离开环的点的路径,必有一奇一偶,取偶数长度的一条与奇交替路和根到环的根的路径取并,就得到一条增广路。(参见红色和橙色部分)

反之,如果存在一条经过这个环的增广路,取其最后一次离开这个环之后的部分即得到一条从环上一点出发的到未匹配点(不包括根)的奇交替路。故这二者的存在性等价。
从一点出发到未匹配点(不包括根)的奇交替路与过该点的增广路存在性等价这是 T 型节点的性质特征。故,交替树上的奇环等价于一个 T 型节点
从而,我们可以进行缩点,再继续匹配。比如上面的图会缩成这样:
match7.png
根据上面的证明方法,搜索树上奇环的缩点是可以叠加的,如图:
match8.png
于是我们可以得到一个一般图上找从 v 起始的增广路的算法(这里是广度优先搜索):


输入:图 $G=(V,E)$,点 $v$,一个匹配 $M$ 输出:不存在增广路,或一条增广路 $P$

函数 找增广路(无向图 G=(V,E) ,点 v\in V ,匹配 M )
v 放入点队列 q ,标记 v T
q 非空时 执行
取出 q 队首的点 r
\forall i\in V 使得 \exists e\in E=(r,i) 执行
如果 i 没有标记
标记 i S
如果 i 有与之匹配的点
设该点为 u ,将 u 放入点队列 q ,标记 u T
否则
展开搜索树上缩的点
返回搜索树上 i v 的路径
结束 如果
否则,如果 i T 型且 i r 不是缩点后的同一点
l i r 在搜索树上的最近公共祖先
将搜索树上 i r l 路径上的点缩点
将被缩的 S 型点放入队列 q ,并标为 T
结束 如果
结束 执行
结束 执行
返回 不存在增广路
结束 函数 找增广路


这个算法被称为**带花树算法(Blossom algorithm,Edmonds' algorithm)**。 时间复杂度:设 $|V|=n,|E|=m$,最多增广 $O(n)$ 次,每次搜索复杂度 $O(n+m)$,总复杂度 $O(n^2+nm)=O(nm)$。 这样我们得到了一种能够解决一般图最大匹配问题的算法。

上述算法的优化:通过建出完整的 BFS 树然后多路增广的方法可以将匈牙利算法的时间复杂度降至 O(m\sqrt n) 。这被称作 Hopcroft–Karp 算法,其过程等同于用最大流解决二分图问题时的Dinic算法。据说,带花树算法也可以优化到这个时间复杂度,但我不知道是否是同样的方法。

现在来看另一个问题:给出一个点 v ,判断它是否可能在最大匹配中,是否一定在最大匹配中;给出一个边 e ,判断它是否可能在最大匹配中,是否一定在最大匹配中。
根据引理 1 的推论 3 和推论 4,首先预处理出一组最大匹配 M ,然后只要判断是否存在一个以 v 为一端的偶交替路 P ,及是否存在一个偶交替路或交替环 P 使得 e\in P
下面是基于这两个推论的几种做法:

法 1 (点)

v\notin S(M) ,则当且仅当 v 的度为 0 时不存在这样的偶交替路。因为由最大匹配不存在增广路,对于任意与 v 相邻的点 u v,u,u 的匹配点这 3 个点之间的路径就是偶交替路。
v\in S(M) ,则按照增广路的思路可以删去点 v 并从 v 原来的匹配点开始找增广路,复杂度 O(m) ,总复杂度 O(nm)

法 2 (二分图)

另一个做法:建立一个新无向图 G'=(V,E') ,对于每组 (u,w)\in M,(w,v)\in E\setminus M ,在 E' 中连边 (u,v) ,允许重边。
可以发现: G 中的非简单交替环与 G' 中的环一一对应, G 中的非简单偶交替路与 G' 中一端为原来的未匹配点的路径一一对应。
非简单会出现问题。但对于二分图而言,这是没有关系的。因为每条边在原图中长为 2,所连的点必定在二分图 G 的同侧。那么 G' 中的简单路径在 G 中不会经过重复的边。
所以,对于二分图,要判断是否存在一个以 v 为一端的偶交替路 P ,只需要判断在 G' 中这个点是否与一个未匹配点在同一个连通块内,预处理复杂度 O(nm+\sum \deg v)=O(nm) ,查询复杂度 O(1) 。同样地,判断是否存在一个偶交替路或交替环 P 使得 e\in P 可以分别判断 e 是否和未匹配点在同一连通块中(偶交替路),以及含 e 的边是否属于 G' 中的某个点/边双连通分量(交替环)。对于交替环,具体而言,若 e\in M ,只需判断 G' e 是否有一个端点所在点/边双连通分量大小超过 1,否则只需判断 G' 中含有 e 的边(不超过 2 条)是否属于 G' 中的某个点/边双连通分量,预处理复杂度 O(nm+\sum \deg v)=O(nm) ,查询复杂度 O(1)

法 3 (一般图)

点的问题在法 1 中已经有了一个解决方法,现在的问题是边。
首先,可以得到以下两个引理:
引理 2 删去一个交替环或偶交替路中的一条匹配边 e 后,会出现一条从这条边一端开始的增广路。
引理 3 对于一个交替环或偶交替路中的一条非匹配边 e\notin M ,至少存在一条与之相邻的匹配边 e'\in M ,使得删除 e' 后会出现一条一端为 e 的增广路。
一个朴素的想法是:对于边 e\in M ,将其删去后从每个端点处开始找增广路;当且仅当找到了增广路时,存在一个交替环或偶交替路包含该边。这个方法也可以看作是看删去这条边后是否还能构造一组最大匹配。
对于边 e\notin M ,将其相邻的所有匹配边 e'\in M (显然不超过2条)做如下操作:删除 e' 后从 e e' 的公共点开始,第一层只通过 e 找增广路;当且仅当找到了增广路时,存在一个交替环或偶交替路包含该边。
这样做的话,单次时间复杂度 O(m) ,总复杂度 O(m^2)
O(m^2)>O(nm) ,超过了找匹配的复杂度,我们还需要优化这个算法。
尽管 m=\Omega(n) ,但可以注意到 |M|=O(n) ,也就是,对于边 e\in M 的讨论可以在 O(nm) 时间内完成。另外,在对于边 e\notin M 的讨论中我们的方法也是删去 M 中的边,这启示我们,如果在讨论匹配边时就把非匹配边的答案也算出来,就可以做到 O(nm) 的时间复杂度了。
引理 4 对于一条非匹配边 e\notin M ,它存在于某一个交替环或偶交替路中,当且仅当存在一条与之相邻的匹配边 e'\in M ,使得删除 e' 后会出现一条一端为 e 的增广路。
充分性显然,必要性由引理 3 可证。
这样,我们需要解决的问题是:给出一个点 v ,如何在 O(m) 时间内求出,对于每个以 v 为一端的边 e ,是否存在从 v e 开始的增广路?

这个问题我并没有搞清楚,但相关的研究已经解决了该问题并给出了在 O(nm) 时间内求解的方法。请查阅相关资料。

参考资料:
[1]Wikipedia, the free encyclopedia.Blossom algorithm.https://en.wikipedia.org/wiki/Blossom_algorithm
[2]Wikipedia, the free encyclopedia.Berge's lemma.https://en.wikipedia.org/wiki/Berge's_lemma
[3]Wikipedia, the free encyclopedia.Matching (graph theory).https://en.wikipedia.org/wiki/Matching_(graph_theory)
[4]陈胤伯.浅谈图的匹配算法及其应用.2015年信息学奥林匹克中国国家队候选队员论文集.2015.
[5]杨家齐.基于线性代数的一般图匹配.2017年信息学奥林匹克中国国家队候选队员论文集.2017.