前言

群会,我会但不完全会

本学习笔记基本参考:
【IOI2015 论文集】陈胤伯,浅谈图的匹配算法及其应用。
【IOI2017 论文集】杨家齐,基于线性代数的一般图匹配。

二分图最大匹配

匈牙利算法,懂的都懂。$\text{Dinic}$ 求最大匹配,懂的都懂。

但是我不懂,这里大致说明一下 $\text{Dinic}$ 求最大匹配的复杂度为啥是 $\mathcal{O}(m\sqrt{n})$。

首先,$\text{Dinic}$ 一开始的 $\text{BFS}$ 是 $\mathcal{O}(m)$;$\text{DFS}$ 是 $\mathcal{O}(nm)$,但是由于是单位流量,所以 $\text{DFS}$ 是 $\mathcal{O}(m)$。

对于前 $\sqrt{n}$ 轮,总复杂度是 $\mathcal{O}(m\sqrt{n})$;

对于 $\sqrt{n}$ 轮之后,由于每次 $\text{Dinic}$ 重新建分层图的时候,其 $S,T$ 的最短路径长度严格递增,所以每条增广路长度都 $\ge \sqrt{n}$。每次会把一条增广路消掉,所以至多还剩 $\sqrt{n}$ 条增广路,这里还是 $\mathcal{O}(m\sqrt{n})$。

于是最后的复杂度是 $\mathcal{O}(m\sqrt{n})$。

二分图最大匹配关键点

关键点指一定在最大匹配中的点。一个很简单的想法是每次删除这个点,重新跑一遍最大匹配,如果答案减小了,则说明该点一定在最大匹配中。但是这样太慢了,有一种更好的方法:

由于已经是最大匹配了,所以图上不存在增广路,只有交错路。我们现在只考虑左部点中的关键点(右部点类似),则对于左部点 $u$,如果存在一条从 $u$ 出发的,以匹配边开始的交错路,到达一个非匹配点 $v$,则 $u$ 不是关键点。

这是因为,将 $u\rightarrow v$ 上的边状态翻转,$u$ 就不是匹配点了。

考虑倒过来做,每次找到一个非匹配点,考虑这个非匹配点能把哪些匹配点给标记成“不是关键点”。将非匹配边定向为从左到右,匹配边定向为从右到左,则从每一个非匹配点 $\text{DFS}$ 到的匹配点都不是关键点。

由于只关心可达性,所以复杂度是 $\mathcal{O}(n+m)$。

二分图最大匹配关键边

关键边指一定在最大匹配中的边。

考虑一条匹配边 $e$,当前匹配为 $M$,若当前边不是关键边,则可以找到另一个匹配 $M'$ 使得 $e$ 不在最大匹配中。考察 $M \oplus M'$,即两者的对称差。

首先,$e$ 一定在 $M\oplus M'$ 中,又两个匹配都是最大匹配,所以一定会形成一些链、环。由于是二分图,所以一定是若干偶交替链和偶交替环。

对于偶交替链,链的一段一定是未匹配边,也就是链有一个端点是未盖点,这说明 $e$ 的两个端点中,存在一个能够通过以匹配边为开始的交替路,走到一个未盖点,这就是非关键点。因此,首先需要判断 $e$ 的两个端点是否存在非关键点。

对于偶交替环,只需要判断 $e$ 是否在一个环中即可,如果在一个交替环上,则可以通过将环上边取反使当前点变为没有被选择。于是可以将匹配边设为从左往右,未匹配边设为从右往左,跑 $\text{Tarjan}$ 缩点,即可判断。

时间复杂度 $\mathcal{O}(n+m)$。

二分图最大独立集

独立集指一个点集,集合内任意两个点之间没有连边。最大独立集指所有独立集中大小最大的。

对于一张二分图,求出其最大匹配 $M$,由于 $M$ 中边的端点不重合,且一条边两个端点至多只有一个在最大独立集中,所以最大独立集大小 $\le n-|M|$。现在给出一种方法,使得最大独立集大小 $=n-|M|$。

首先,对于一组最大匹配 $M$,所有未盖点都必须在最大独立集中,对于匹配边,两端的点恰好选择一个。每次,从已经决定是否选择的点开始,将还没有考虑的边的状态进行更新,即更新与一个已经确定状态的点相连的所有点的状态。如果没有这样的点,则随意选择一个点的状态,然后继续做。

这样会出现冲突的话,只有以下情形:

冲突

其中红色边是匹配边,深蓝点是已经选入最大独立集的未盖点。注意到这样实际上意味着出现了一条增广路,与 $M$ 是最大匹配矛盾,于是不会出现冲突。

于是,只需要每次从一个确定了状态的节点开始,更新其他点的状态即可。一个点只会被确定一次,所以复杂度是 $\mathcal{O}(n + m)$。

当然,也可以直接最小割。

二分图最小点覆盖

点覆盖指一个点集,使得任意一条边的两个端点中,都至少有一个点在该集合中。

根据定义可得,任何点覆盖的补集都是独立集,任何独立集的补集都是点覆盖。于是最小点覆盖 $=n-$ 最大独立集 $=$ 最大匹配。

二分图最小字典序完备匹配

设 $\text{match}_i$ 是二分图中与左部点 $i$ 匹配的右部点。最小字典序完备匹配要求最小化序列 $\text{match}_1,\text{match}_2...$。

套用对于这种字典序最小问题常用的贪心思想,每次考虑第一个元素最小是多少。

首先,容易说明对于两个完备匹配 $M$ 和 $M'$,其对称差一定形如若干交替环。从小到大考虑当前点的某一条边是否能加入匹配,如果这条边已经是匹配边了,显然在完备匹配中;如果这条边在一个交替环中,也可以通过将环上边取反来将当前边加入完备匹配。

判断这条边是否在一个交替环里,还是可以使用 $\text{Tarjan}$ 缩强连通分量,然后判断当前边的两个端点是否在同一个强连通分量中。

选定一组匹配之后,为了不再被影响,可以将这两个点从图中删除。容易发现剩下的部分仍然是剩下的图的完备匹配。因此复杂度是 $\mathcal{O}(nm)$。

一般图最大匹配

他来力

带花树算法

一般图问题在于有奇环,就会出现下面这种情况:

一般图奇环

这样我绕一下奇环,走回同一条边的时候这条边的选取状态就会出现问题。于是就需要带花树了!

其主要思想就是将奇环直接缩成一个点,然后做二分图匹配的内容。具体过程是:

首先,记录 $\text{pre}$ 数组表示当前点的前驱节点是谁,找到增广路之后,将顺着前驱节点进行增广,且后续在缩环的时候对 $\text{pre}$ 的修改也是很关键的一个步骤。

从一个未盖点 $s$ 开始匹配,每次交替拓展,也就是拉出一棵交替树。将点奇偶标号,根是偶点,注意到每次选择一个奇点之后,他会自动将自己匹配的点拉进来,成为一个偶点。

设当前偶点是 $x$,枚举出点 $y$。

若 $y$ 没有被访问过:若 $y$ 是未盖点,则已经找到增广路;否则将其匹配的点拉入,继续进行。

若 $y$ 被访问过:则说明当前边是交错树的非树边。如果 $y$ 是偶点,则说明找到一个偶环,其正确性和二分图类似;否则,即若 $y$ 是奇点,说明找到一个奇环,则需要将这个环缩起来。

缩环

考虑这样一张图,$s$ 到 $h$ 是一条交错路,其中 $s$ 是未盖点。这里我们就找到了一个奇环。容易得出:$s$ 到 $h$ 路径上,连接 $h$ 的边一定是匹配边,且这个环上只有 $h$ 连接的两条边都是未匹配边,除了 $h$ 外从环外连向环上点的所有边都是未匹配边。

注意到不论从哪个点进入环,总有一种合法的方案能够走到 $h$,而且显然只能从 $h$ 走出去——因为只有 $h$ 与环外的边是匹配边。

于是,我们可以调整这个环上的 $\text{pre}$,使得不管从什么地方进来,都有一种方案能够引他走向 $h$。例如我们将 $\text{pre}_u$ 设置为 $v$,则当某条交替路从 $u$ 的匹配点走进环,$u$ 就会被自动拉入,然后顺着 $\text{pre}_u=v$ 从环的一侧走向 $h$。

至于找 $h$ 这个点,注意到他一定是 $u,v$ 的 $\text{LCA}$,又图一直可能变化,所以只能暴力跳父亲来找。缩点可以直接并查集。

一轮增广是 $\mathcal{O}(n^2)$,要从每个点开始增广一次,所以时间复杂度是 $\mathcal{O}(n^3)$。

模板

基于线性代数的一般图匹配算法

完美匹配的存在性

$\text{Tuttle}$ 定理

定义无向图 $G$ 的 $\text{Tuttle}$ 矩阵是一个 $n\times n$ 的矩阵 $\tilde{A}(G)$,满足:

$$ \tilde{A}(G)_{i,j}= \left \{ \begin{matrix} x_{i,j} && (i,j)\in E,i<j\\ -x_{j,i} && (i,j)\in E,i>j\\ 0 && \text{otherwise} \end{matrix} \right. $$

其中 $x_{i,j}$ 是一个独立的变量。

$\text{Tulle}$ 定理:图 $G$ 有完美匹配 $\iff \det\tilde{A}(G)\ne 0$。

证明:

首先,一张图有完美匹配,当且仅当他可以被“偶环覆盖”,即可以通过若干偶环覆盖所有的点,使得每个点恰好在一个偶环中。构造方式很简单,只需要将偶环上的边交替选择即可。

考虑 $\det$ 的意义,实际上就是选择了一个环覆盖,如果环覆盖中存在奇环,容易发现翻转这个环后,前面的 $(-1)^{\tau(p)}$ 系数翻转,两个权值相加为 $0$。显然能构造一一对应关系,于是 $\det \tilde{A}(G)\ne 0\iff G$ 有偶环覆盖 $\iff G$ 有完美匹配。

随机化

由于 $\text{Tuttle}$ 矩阵中有很多个变量,所以直接求解行列式显然是不够快的。注意到我们只需要知道 $\det \tilde{A}(G)$ 是否为 $0$ 即可,而 $\det \tilde{A}(G)$ 实际上是一个 $m$ 元多项式 $P(x_1,x_2,\cdots x_m)$,则我们的目标就是判断 $P$ 是否恒为 $0$。

简单的想法是给每个变量随机一个权值,看其取值是否为 $0$,从而判断 $P$ 是否恒为 $0$。这个事情的正确性可以通过以下引理说明:

$\text{Schwartz-Zippel}$ 引理:对于域 $\mathbb{F}$ 上一个不恒为 $0$ 的 $n$ 元 $d$ 度多项式 $P(x_1,x_2,\cdots x_n)$,设 $r_1,r_2,\cdots r_n$ 是 $n$ 个在 $\mathbb{F}$ 中独立选取的随机数,则:

$$ \text{pr}[P(r_1,r_2,\cdots r_n)=0]\le \dfrac{d}{|\mathbb{F}|} $$

可以简单理解为,如果这个多项式不恒为 $0$,则随机选到一些变量,导致多项式取值为 $0$ 的概率很小。具体证明可以归纳 但是我鸽了

我们知道,$\det \tilde{A}(G)$ 的度是 $\mathcal{O}(n)$ 级别的,所以只需要选取 $\mathcal{O}(n^2)$ 级别的质数 $p$,在 $\bmod p$ 意义下进行上述过程,其错误概率 $\le \dfrac{1}{n}$。当然,可以多随几次来提高正确率。

标签: 网络流, 二分图, 匈牙利算法, KM, 带花树

添加新评论