匹配算法

Published: by Creative Commons Licence

  • Tags:

Berge定理

定理:图G的匹配M是最大匹配的充分必要条件是G中不存在M可扩展路。

证明:

必要性:

如果存在可扩展路,我们可以将可扩展路上的原本选中的边剔除出M,并加原本未选中的边加入M,从而我们的M的基数增大了1。

充分性:

设M不是最大匹配,且M中不存在可扩展路。设M'为最大匹配。那么记新的匹配$H=M\oplus M'=M\cup M' - M\cap M'$。此时H中被匹配顶点的度数非1即2(被M或M'匹配),H中任意连通分支必然是仅来自M中的边和仅来自M'中的边形成的交替路。如果有环出现,那么环一定是偶环,我们可以将其缩为一个顶点。考虑到$|M'|>|M|$,因此H中来自M'的边一定多于来自M的边,这意味着在H中必定存在一个连通分支,其对应长度为奇数的一条路径,并且最两端的边均来自M'。这样我们就找到了一条可扩展路。

Berge定理为我们提供了一种寻找最大匹配的方法。

最大流算法求最大匹配

对于E的一个子集,若子集中的任意两条边都没有公共顶点,那么称该子集为图G的一个匹配。如果不存在比某个匹配更大的匹配,则称该匹配为G的最大匹配。

我们向图中加入两个顶点s,t,分别作为源点和终点,从s到所有L中顶点建立一条容量为1的边,从R中所有顶点到t建立一条容量为1的边。之后在图上跑最大流算法就可以得到最大覆盖了,一个边如果流量为1,则边为最大匹配的一部分。

很显然这样得到的一组边集是一个匹配,而对于任意一个匹配,匹配中的每一条边都能为最大流算法提供1的流量。因此最大流算法得出的最大流与最大覆盖的大小等同,而我们得到的边集的大小等同于最大流的大小,因此该覆盖是最大匹配。

Dinic求最大匹配

Dinic的思路是通过BFS得到图的分层,之后增广到无法继续增广。

命题:用Dinic求最大匹配的时间复杂度为$O(m\sqrt{n})$,其中$n$是顶点数目,$m$是边数目。

证明:

每次分层加增广的时间复杂度为$O(m)$。考虑经过$\sqrt{n}$次增广后,那么图中最短增广路的长度至少为$\sqrt{n}$,这是因为每次分层后最短增广路严格递增。

假设M是当前得到的匹配,而M‘是最大匹配,那么考虑$M\oplus M'=M\cup M' - M\cap M'$。其中的每个强连通分量要么是偶环,要么是长度大于$\sqrt{n}$的交替路,因此最多有$n/\sqrt{n}=\sqrt{n}$条增广路可以继续增广,即之后最多还有$\sqrt{n}$次分层,总的分层次数不会超过$2\sqrt{n}$,总的时间复杂度为$O(m\sqrt{n})$。

匈牙利算法

匈牙利算法也是一个求最大匹配的算法,时间复杂度与EK算法类似,同样是$O(E(V+E))$,但是由于是二分图专用的,因此实际效果非常好,个人实测有将近10倍的差距。

算法的思路与EK算法类似,也是沿着残存网络中的边进行增广。

/**
* 要求node释放自己的同伴,成功返回true,失败false
*/
boolean release(Node node){
    if(node.visited)
    {
        return false;
    }
    node.visited = true;
    if(node.partner != null && bind(node.partner))
    {
        node.partner = null;
    }
    return node.partner == null;
}
/**
* 要求node重新寻找一个新的同伴,成功返回true,失败false
*/
boolean bind(Node node)
{
    if(node.visited)
    {
        return false;
    }
    node.visited = true;
    for(Node nearby : node.edges)
    {
        if(!release(nearby))
        {
            continue;
        }
        node.partner = nearby;
        nearby.partner = node;
        return true;
    }
    return false;
}

最小顶点覆盖

对于V的一个子集,若对于任意E中的一条边,其至少一个顶点属于该子集,那么称该子集为图G的一个顶点覆盖。所有顶点覆盖中最小的顶点覆盖,称为图G的最小顶点覆盖。

Konig定理:二分图中的最大匹配数等于这个图的最小顶点覆盖数。

证明:

假设我们找到了最大匹配Y。

我们称Y中所有边的两个端点为被Y所匹配。我们遍历所有R中没有被Y匹配的顶点,寻找所有长度为偶数的路径,路径中匹配边和未匹配边交替出现。事实上不存在长度为奇数的路径,不然我们就找到了一个增广路径。我们将L中被标记过的顶点和R中未被标记的顶点合成一个新的点集合X,我们接下来证明X是最小顶点覆盖。

首先先说明X是顶点覆盖,即所有边至少有一个端点属于X。假设存在一条边e,e的两个端点$l\in L$,$r\in R$均不属于X,这意味着l未被标记而r被标记过了。但是这是不可能的,因为r被标记意味着存在这样一个顶点序列$r_0,l_0,r_1,l_1,\ldots,r$,其中路径$(r_i,l_i) \notin Y$且$(l_i,r_{i+1}) \in Y$。我们可以在路径尾部追加$l$得到更长的一条奇数路径,l必定被Y匹配,因此存在另外一条边$(l,t)\in Y$,即路径$r_0,l_0,r_1,l_1,\ldots,r,l,t$是一条合法路径,其上所有顶点都会被标记,因此不存在这样的边,X是顶点覆盖。

之后说明X最小。显然每个Y中的边至少需要一个顶点覆盖,因此最小顶点覆盖数至少为|Y|。我们接下来证明$|X|=|Y|$。

很显然,X中的顶点必定都被Y所匹配(回忆下X是由哪些顶点组成的)。而如果一条$Y$中的边e,两个端点$l\in L$,$r\in R$都属于X,这意味着l被标记而r未被标记,这是不可能的,因为我们同样可以构建一个合法的标记路径。因此我们知道$Y$中的每一条边只有一个顶点属于$X$,到此,我们证明了$|X|=|Y|$。

最小边覆盖

对于E的一个子集,若对于任意V中的一个顶点v,一定能在子集中找到一个边e,使得v是e的某个端点,那么称该子集是图G的一个边覆盖。所有边覆盖中最小的称为最小边覆盖。

最小边覆盖数等于$|V|-|Y|$,其中,其中$Y$是最大匹配。

证明:

假设X是最小边覆盖,我们可以保证,X中每条边都至少独立覆盖了一个顶点(不然我们可以将这条边删除得到更小的一个边覆盖)。我们不断从X中删除仅独立覆盖一条顶点的边,假设共删除了k个顶点。留下的$|X|-k$条边都独立覆盖了两个顶点,可以发现此时条边都独立覆盖了两个顶点,可以发现此时条边都独立覆盖了两个顶点,可以发现此时条边都独立覆盖了两个顶点,可以发现此时X同样也是G的一个匹配。由此得出下面不等式:

因此我们可以得出最小边覆盖的大小至少为$|V|-|Y|$。下面我们讲述如何得到最小边覆盖。

记边集X初始为Y。由于X覆盖了2X个顶点,记这些顶点集合为U,我们为每个不属于U的顶点,找到一个以其为端点的边并加入到Y中。完成上述操作后,X的大小正好为$|V|-|Y|$。此时。此时。此时。此时X为图G的一个边覆盖。

二分图最大独立集

对于V的一个子集,若子集中任意两个不同顶点之间都没有边,那么称该子集为G的一个独立集。独立集中最大的称为最大独立集。

二分图最大独立集的大小等于$|V|-|M|$,其中M为最大匹配。

证明:

要计算最大独立集,我们可以换种理解。我们记X为最大独立集,而Y=V-X。要获取最大独立集,我们实际上要从V中移除一些由边连接的顶点。对于任意边的两个端点,我们至少需要从V中移除一个顶点。换言之,每个边的都有至少一个端点属于集合Y。容易发现Y是一个顶点覆盖,同样的任意一个顶点覆盖,其对于V的补集一定也是一个独立集。由于$|X|=|V|-|Y|$,要让X最大,等价于Y最小,因此Y实际上是一个最小顶点覆盖,而我们之前已经讨论过最小顶点覆盖和最大匹配等大,因此公式$|X|=|V|-|M|$。

二分图最大团

对于V的一个子集,若子集中任意两个顶点之间都有边,那么称该子集为G的一个团,团中最大的称为最大团。

二分图G=(V,E)中的团,对应G的补图中的一个独立集。而最大团对应的就是补图中的最大独立集,之前已经讨论过最大独立集的求法了,这里不赘述。

最小路径覆盖

我们将$V$分成若干个子集$X_1,X_2,\ldots,X_k$,其中每个子集都对应G中的一条无环路径,且所有子集的并集为V,那么称顶点子集族${X_1,X_2,\ldots,X_k}$为$G$的路径覆盖。最小的路径覆盖称为最小路径覆盖。如果所有子集彼此之间交集为空,那么称子集族为G的不相交路径覆盖,否则称为相交路径覆盖。

我们将有向无环图$G=(V,E)$中每个顶点$v$拆成两个顶点$v_l$,$v_r$,而对于E中每一条边$(u,v)$,我们对应的建立一条边$(u_l,v_r)$。这样我们就建立了一个二分图$G'$。图$G$的最小不相交路径覆盖的大小等于$|V|-|M|$。其中$M$表示$G'$的最大匹配。

证明:

在初始的时候对于每个顶点$v$,我们都可以建立一条不相交路径$(v_l,v_r)$,因此一开始我们可以建立$|V|$条不相交路径。

对于任意一个匹配,对于匹配中每一条边$(u_l,v_r)$,我们将以$v$开始的路径与以$u$结尾的路径通过$(u,v)$合并在一起。显然每次合并后,任意一个结点出现且仅出现在一条路径中。因此我们可以得到一个大小为$|V|-|M|$的路径,我们将其中的$u_l$和$u_r$结点合并为一个结点$u$后就得到了原图G中的一条大小为$|V|-|M|$的不相交路径覆盖。这里我们证明了最小不相交路径覆盖的大小的上界为$|V|-|M|$,但是还未证明不存在更小的不相交路径覆盖。

同样的,对于任意一个不相交路径覆盖$P$以及其对应的边集$T$,我们将其中每个顶点$v$拆成两个顶点$v_l$和$v_r$。之后我们将$T$中所有边$(u,v)$,作为$(u_l,v_r)$加入到$G'$中,很显然这些边是图$G'$的一个匹配(因为任意顶点在$P$中仅出现一次)。而$|P|+|T|=|V|$,因此$|P|\geq |V|-|M|$。这里证明了最小不相交路径覆盖的大小的下界同样为$|V|-|M|$。

对于有向无环图G=(V,E),如果顶点u到v存在一条路径,则我们向图中加入一条边$(u,v)$,这样我们得到了图$G'$。$G$中的最小相交路径覆盖与$G'$最小非相交路径覆盖是等大的。

证明:

对于图$G'$中的最小非相交路径覆盖$P$,对于P中的任意边$(u,v)$,我们知道$u$和$v$在原图$G$中一定是有路径连接的,我们用路径替换边$(u,v)$,就可以得到$G$中的一条相交路径覆盖。

同样的对于图$G$中的一条相交路径覆盖,我们可以其中的所有重复路径,替换为一条边。之后就能得到图$G'$中的一条不相交路径覆盖。

霍尔定理

对于二分图$(A,B)$,存在一种匹配,使得$A$中所有顶点都被匹配,当且仅当对于任意$A$的子集S,记与其相邻的所有顶点的集合为$N(S)$,有$|S|\leq |N(S)|$。

题目1:在一条直线上,我们放置一些男士和女士,男士面朝右,女士面朝左,如果男士和女士面朝彼此,那么就认为二人相互有好感。有好感的人我们可以送入婚姻殿堂。现在有$n$个请求,请求分三类:第一类,在某个点上放置或移除一个男士,在某个点上放置或移除一个女士,第三类,判断是否存在一种方案,所有男士都可以与心仪的女士结婚。其中$n\leq m$(题目保证线上每个人的坐标都是不同)

霍尔定理的简单应用,由于男士面朝右,因此所有男士有匹配当且仅当所有男士的右边(包括自己),女士的数目大于等于男士的数目。即我们为每个第$i$个男士维护一个属性$x_i$,为右边男士的数目减去女士的数目,之后要判断是否存在男士的完美匹配,当且仅当所有男士的属性$x_i$都非正数。这个可以通过线段树维护,时间复杂度为$O(n\log_2n)$,$n$是总共男士的数目,而$m$是请求数目。

提供一道CF题目

题目2:有$n\times m$的一个矩阵,每个单元都有一个数值,对于$1\leq i\leq n$,都有$m$个单元格的数值正好为$i$。现在要求重新整理每一行的数值(即对每一行进行重新排列),要求整理完后,每一列的元素两两不同。$1\leq n,m\leq 100$

霍尔定理的经典用途。首先我们先考虑第一列上的元素。我们建立一个二分图,每一行都对应左边一个顶点,而每个数值都对应右边的一个顶点。如果第$i$行有数值$j$存在,那么就在$L_i$和$R_j$之间加一条边。现在我们通过霍尔定理证明一定存在完美匹配,考虑$k$行组成的集合,我们可以利用鸽巢原理,可以直接断言,这些行中不同元素的数目至少有$k$个,否则的话至少一个元素出现次数超过$m$,这是不可能的。因此我们可以找到任意一个完美匹配。之后我们考虑后面$m-1$列的情况,我们发现这是原问题的一个子问题(每个元素恰好出现$m-1$次),可以用样的方式解决。

提供一道Kattis题目,再提供一道Atcoder题目

题目3:有$n\times n$的一个矩阵,每一行每一列都对应一个$1$到$n$的置换,这样的矩阵称为拉丁方。现在矩阵中前$k$行已经被填入数值了,要求你将其余数值填入其余单元格中。如果存在解,输出任意一组,否则报告无解。其中$1\leq n\leq 100$

首先很显然每行每列元素都需要不同,否则不解。那么假如通过了检测,那么就可以通过题目2的方式解决剩下的部分。

题目4:有$n\times n$的一个矩阵,每一行每一列都对应一个$1$到$n$的置换,这样的矩阵称为拉丁方。现在矩阵中有$k$个不同的数值已经填入矩阵的$nk$个单元中了,要求你将其余数值填入其余单元格中。如果存在解,输出任意一组,否则报告无解。其中$1\leq n\leq 100$

首先为了保证拉丁方有解,我们需要先保证每行每列都没有重复元素。

之后我们按数值进行填充,任意取一个未填充过的数值,填入其中的$n$个单元格中。由于每行每列需要恰好填入一个元素,我们可以建立这样的二分图,每一行对应左边某个顶点,每一列对应右边一个顶点,如果$(i,j)$为空,就在$X_i$和$X_j$之间连边。假设现在我们处理了$t$个数了,那么我们会发现每一行每一列都还有$n-t$个单元格可用,即对应二分图中每个顶点的度数都是$n-t$,这意味着二分图是一个$n-t$正则图,而我们知道这样的二分图是一定有完美匹配的(应用霍尔定理),因此我们可以不断消费掉新的数值,直到所有数被用完。

提供一道题目

链和反链

对于偏序集S,称S的子集A是链,当且仅当A组成一个全序集。若S的子集B中元素两两不可比较,那么称B是反链。

最小链覆盖是指S的一个子集族,每个元素都是链,所有元素的并为V,但是不同元素的交集为空。同样最小反链覆盖也是S的一个子集族,每个元素都是反链,所有元素的并为V,但是不同元素的交集为空。

Dilworth定理:偏序集的最小链覆盖大小等于S的最长反链的长度

证明:

记最小链覆盖的大小为n,最长反链长度为m。

设L是S的一个最长反链,很显然多个L中的元素不能同时属于相同的链,因此最小链覆盖至少包含m个链,即$n\geq m$。

之后利用数学归纳法证明$n\leq m$。

当S的大小为0或1的时候,命题显然成立。

我们记s是S的一个极大元,记S'=S-{s}。由归纳法知,S'的最小链覆盖的大小与最长反链的长度相同,记作k。设S'的最长链覆盖为${C_1, C_2, \ldots, C_k}$,而S'的所有长度为k的反链为$R_1, R_2, \ldots, R_r$。很显然,对于$R_i$,必定是由最长链覆盖中每个集合取一个元素组成的,我们记$R_i$与$C_j$的唯一公共元素为$x_{ij}$。对于$j=1,2,\ldots, k$,记$m_j=\max_i(x_{ij})$。现在考虑集合$M={m_1, m_2, \ldots, m_k}$,如果其中有任意两个不同元素$m_i,m_j$可以比较,不妨设$m_i\leq m_j$,记$m_i$所在的反链为$R_p$,而$m_j$所在的反链为$R_q$,那么可以推出$x_{qj} = M_j \geq x_{pi} = M_i \geq x_{qi}$,即$R_q$包含两个可比较元素,这是不可能的,因此我们知道$M$是反链。

接下来我们考虑集合S,即向S'加入元素s。考虑两种情况:

1) 如果M与s中元素都不可比较,那么我们考虑集合$M\cup {s}$,这是一个长度为k+1的反链。而向集合中加入一个元素,最多会增加其最长反链长度1,以及最小链覆盖大小1。因此有$m\geq k+1 \geq n$。

2) 如果M与s中某个元素可以比较,假设s与$M_i$可以比较,设$M_i$所在的反链为$R_j$,那么我们可以推出s大于等于$R_j$中的所有元素,即$D=R_j\cup {s}$也是一个链。现在考虑集合S''=S-D,由于S中的所有反链都少了一个元素,因此S''的最长反链的长度为k-1,同样利用归纳法知其最小链覆盖为${C'_1,C'_2,\ldots, C'_{k-1} }$。我们将D加入得到新的最小链覆盖${C'_1,C'_2,\ldots, C'_{k-1}, D}$。因此S的最小链覆盖大小一定是$k$,故可以得到$m\geq k = n$。

Dilworth对偶定理:偏序集的最小反链覆盖大小等于S的最长链长度

证明:

记最小反链覆盖的大小为n,最长链长度为m。

设L为S的一个最长链,而L中多个元素肯定不能同时属于一个反链,因此最小反链覆盖至少含有m个反链,即我们推出了$n\geq m$。

我们记$X_1$为S中的极小元的集合,并从S中移除$X_1$的元素。之后继续定义$X_2$为S中极小元的集合,并同样从中移除。重复这个过程,直到S为空,假设过程中我们得到了k个非空集合$X_1,X_2,\ldots, X_k$。极小元的集合一定是S的一个反链,我们得到了一个大小为k的反链覆盖。同样我们从$X_1,X_2,\ldots, X_k$中分别取一个元素$x_1,x_2,\ldots, x_k$,满足$x_1\leq x_2 \leq \ldots \leq x_k$,这样我们就得到了长度为k的一个链。得到关系式$n\geq k \geq m$,结合之前得到的$n\geq m$,可以推出$n=m$。

求最长反链方法:

我们先利用最小相交路径覆盖将图建成二分图并求得最大匹配。设n为顶点数,最大匹配数为m,记l(i)表示二分图左侧第i个顶点,r(i)表示二分图右侧第i个顶点。

之后我们可以找到最小顶点覆盖,利用最小顶点覆盖得到最大独立集。对于$1\leq i \leq n$,如果l(i)和r(i)同时属于最大独立集,我们就将它放入到集合A中,集合A初始时为空集。在上述操作后,我们得到的集合A就是最长反链条。

用反证法证明,如果A中任意两个元素u、v可比较,那么不妨设$u\leq v$。这意味着l(u)与r(v)之间有边,而我们知道l(u),r(u),l(v),r(v)都属于最大独立集,因此不可能发生。

现在我们证明得到的反链长度正好为$n-m$。由于二分图共有$2n$个顶点,而最大独立集中有$2n-m$个顶点。$|最大独立集|=|A|+|{i|l(i)与r(i)有且仅有一个属于最大独立集}|$。而后者最多为n,因此推出前者至少为n-m。当然反链长度是不可能超过n-m的,因此得到的反链的长度恰好为n-m。

一类二分图匹配问题

题目1:有两列数字,每一列数字都是$1,2,\ldots,n$。不同列两个数字$x,y$之间有边当且仅当$x+y\leq m$,其中$m$是给定的数字。要求求最大匹配,这里$n,m\leq 10^{18}$。

首先我们可以假设$n\leq m-1$,因为每一列大于等于$m$的数永远不会被匹配。

对于左边的数$x$,如果$x<m-n$,那么我们称它为第一类数,将其与右边的$x$匹配,否则称它为第二类数,将其与右边的$m-x$进行匹配。

很显然这是完美匹配,因此结果为$\min(n,m-1)$。

题目2:有两列数字,每一列数字都是$1,2,\ldots,n$,但是左边列缺少了数字$a$,右边列缺少了数字$b$。不同列两个数字$x,y$之间有边当且仅当$x+y\leq m$,其中$m$是给定的数字。要求求最大匹配,这里$n,m\leq 10^{18}$。

这道题和题目1的区别仅在于左右两边各缺失一个数。首先不管缺失的数,先利用题目1的方案找到完美匹配$\min(n,m-1)$。

如果删除的两个数都大于$m-1$,那么对结果无影响,如果有一个数小于等于$m-1$,那么不存在完美匹配,此时最大匹配为$\min(n,m-1)$。接下来仅考虑删除的两个数都小于等于$m-1$的情况。

首先如果$a+b=m$,那么$a$和$b$一定属于第二类数,且$(a,b)$正好是完美匹配中的一条边,因此我们直接得到了新图的完美匹配,匹配大小为$\min(n,m-1)-1$。

如果$a+b>m$,那么$a$和$b$一定属于第二类数,那么我们发现释放出的新的两个未匹配数为$m-a+m-b<m$,因此我们将释放出的两个数直接匹配,这样就得到了新的完美匹配,匹配的大小为$\min(n,m-1)-1$。

如果$a+b<m$,这时候需要判断是否存在第一类数,即是否有$m>n+1$。如果满足则我们可以拆开一对第一类点的匹配,而第一类数可以和任意数匹配,这样我们和新增的两个点匹配即可,这样就得到了新的完美匹配,匹配的大小为$\min(n,m-1)-1$。如果不满足,那么就一定不可能存在完美匹配,因为存在会推出剩余所有数的总和为$(\min(n,m-1)-1)m$,这是不可能的。而匹配$\min(n,m-1)-2$是存在的,因此此时的最大匹配为$\min(n,m-1)-2$。

问题3:给定一个无向图,有$n$个顶点,$m$条边,要求将部分边转换成有向边,其余边删除,且每个顶点的入度不超过1。要求保留最多数目的边,输出一种方案。

如果一条边指向这个顶点,我们称边和顶点匹配。这个问题我们可以逐连通块考虑,假设现在我们在处理某个连通块。分两种情况讨论:一种是连通块是树,我们可以将边从父亲指向孩子,很显然除了根外每个顶点的入度都正好为1。第二种情况,连通块中有环,我们计算其中的一个生成树,在加入额外的一条边,形成一个简单环。我们可以将环中的每条边都设置为单向边,沿着这些单向边移动会回到起点。接着将简单环缩点后就是一个普通的树了,将其余树边全部从父亲指向孩子即可,而根就不会被任何边指向。由于边数和顶点数相同,所以已经是最大匹配了。

算法可以通过并查集实现,时间复杂度为$O(n)$。

问题4:给定一个二分图(无重边),左边有$L$个顶点,右边有$R$个顶点,且右边顶点的度数不超过$2$。要求最大匹配。

对于右边度数为0的顶点,删除不影响结果。而度数为1的顶点,我们可以贪心将其与存在的左边顶点进行匹配。之后我们忽略删除和已经匹配的顶点,此时右边的全部顶点度数均为2,如果我们将左边的顶点视作无向图中的顶点,右边的顶点视作无向边,那么问题就变成了将无向边转换成有向边的问题,这个可以通过问题3的方式解答。

时间复杂度为$O(n)$。

问题5:给定$n$个不同的二维平面点,对于每个点,我们可以经过它画一条横线,或一条纵线,或者不画线。两条重合的线被视作是一条线。现在问能够绘制出多少不同的直线集合。这里$n\leq 10^6$,结果对素数取模。

我们建立一个二分图,水平线对应左边顶点,竖直线对应右边顶点。每个点对应一条边,连接穿过它的两条线。现在考虑每个连通块,最终的结果为所有连通块集合数的乘积。

考虑一个连通块,一个直线集合有效,当且仅当我们可以将所有边,要么删除,要么转换为有向边,且所有直线集合代表的顶点的入度恰好为$1$,其余顶点的入度为$0$。如果连通块是树,那么我们可以通过选择根,保证所有大小不超过边数的直线集合有效。如果边数不少于顶点数,我们可以保证所有集合都是是有效集合。证明方法和问题3中的一致。

利用并查集,以及离散化技术,可以$O(n\log_2n)$解决这个问题(假如将离散化替换为哈希表,可以$O(n)$解决)。

提供一道题目

Kuhn-Munkres算法

Kuhn-Munkres算法可以$O(V^3)$时间复杂度求非负权二分图的最大权完美匹配。(由于是完美匹配,如果有负权边,可以都先修正为非负数,之后从结果中减去即可)

其基于一种顶标的概念,每个顶点一开始被赋予一个顶标,之后不断调整顶标(始终非负)从而获得更大的匹配,直到得到完美匹配为止。且在这个流程中一直保持对于任意边$(i,j)$,都有$X_i+Y_j\geq w(i,j)$,即边两端的顶标和总是不小于边权重,且最终得到的完美匹配集合中所有的边$(i,j)$都满足那些$X_i+Y_j=w(i,j)$。顶标和在整个过程中始终是当前匹配集合的边权和的上界,且随着流程进行始终递减,当匹配集合是最大权完美匹配的时候,二者正好相等。

KM算法没太大用处,虽然它可以$O(V^3)$求最大权二分图完美匹配,但是它必须要求完美匹配,而最小费用流算法则没有这个约束,且用Dijkstra优化的版本的时间复杂度为$O(V\min(V^2,E\log_2V))$。

但是KM算法的顶标技术可以解决一些特殊的问题:

给定两组不同的非负变量$a_1,\ldots,a_n$以及$b_1,\ldots,b_n$,且对于任意$i,j$,均存在一个约束条件:$a_i+b_j\geq c_{i,j}$。现在希望得到一组赋值方案,满足所有约束条件的前提下,令$\sum_{i=1}^na_i+\sum_{i=1}^nb_i$最小。其中$n\leq 400$

首先这个问题很容易化成线性规划的标准型,总共$2n$列,$n^2$行,化成对偶形式后,大概时间复杂度为$O(n^5)$左右(非严格),很显然过不了。

仔细观察发现每个约束条件实际上都和KM算法中顶标约束边的方式非常相似。我们建立一个二分图,对于约束条件$a_i+a_j\geq c_{i,j}$,我们可以加入一条从$X_i$连向$Y_j$的权重为$c_{i,j}$的边。对于拥有合法顶标的二分图,$X_i$的顶标可以赋值给$a_i$,$Y_i$的顶标可以赋值给$b_i$。很显然这是一套合法的赋值方案。而同样对于一套合法的赋值方案,我们也可以将其转换为二分图的合法的一套顶标。

而要让$\sum_{i=1}^na_i+\sum_{i=1}^nb_i$最小,对应于我们要求二分图顶标和的一个下界,这个下界当二分图是完美匹配的时候可以取到。

这里总的时间复杂度为$O(n^3)$。

提供一道SGU的题目

$k$正则二分图

如果二分图中左右顶点集合$X$,$Y$拥有相同数目的顶点,且每个顶点的度数均为$k$,那么称这样的二分图为$k$正则二分图。

命题1:当$k>0$时,$k$正则二分图一定有完美匹配。

证明:

假设$k$正则二分图没有完美匹配,那么根据霍尔定理,存在$X$的某个子集$A$和$Y$的某个子集$B$,满足$N(A)=B$,且$|A|>|B|$。但是考虑到$A$的总度数为$k|A|$,而$B$的总度数仅为$k|B|$,由$k|A|>k|B|$可以得出$N(A)\neq B$。这与前提相悖,因此$k$正则二分图一定有完美匹配。

二分图边染色问题

这一节的内容是受CF博客启发写的。

二分图边染色,是指对边染色,满足相同颜色的边没有公共顶点(或者说每个顶点的关联边颜色都不同)。而用最少的颜色的二分图边染色称为最小二分图边染色。

现在我们思考如何求解最小二分图染色,这里仅考虑简单图(无重边和自环)。

由边染色的定义可以发现,同种颜色的边,没有共享顶点,换言之,其对应二分图的某个匹配。因此二分图边染色问题,等价于将边集划分为最少的匹配集合。

我们记$k$为二分图中所有顶点的度数的最大值,显然它是颜色数目的一个下界。现在我们证明它同时是一个上界。

非常简单,我们将两边顶点集合扩充到相同大小,之后我们将边集进行扩充,直到所有顶点度数都达到了$k$。这种图叫做$k$正则二分图。利用霍尔定理会发现,$k$正则图一定有完美匹配。我们对$k$正则图先计算一次最大匹配,并将匹配中的边进行染色,之后删除匹配中的边后,二分图会变成$k-1$正则图,同样执行这些操作。于是在$k$此操作后,图中的所有边都被成功划分成$k$个匹配。考虑到扩充后的边集是原来边集的超集,因此我们用相同的方案染色原图即可。

上面的算法直接实现的话时间复杂度会达到$O(kE\sqrt{V})$。但是注意到当$k$为偶数的时候,这时候我们能找到原图的欧拉环,我们将从左边到右边的边染色成白色,右边到左边的边染色成黑色,由于欧拉环中每个顶点进入次数和离开次数相同,因此染成白色的边和染成黑色的边各自可以独立构建成一个$\frac{k}{2}$正则二分图。由于每条边最多会对结果贡献$\log_2k$次,因此时间复杂度可以优化到$O(E\sqrt{V}\log_2k)$。

这里我们提供另外一个时间复杂度为$O(VE)$的算法,其实现非常简单高效。我们可以选择任意一条未染色的边$(u,v)$,如果边可以被染成某个颜色,那么就直接染色即可。否则这时候$u$的关联边颜色和$v$的关联边的颜色的并集覆盖了所有$k$种颜色。但是考虑到边$(u,v)$还未染色,因此$u,v$各自最多占有$k-1$种颜色,换言之,存在一种颜色$c_u$,是属于$u$但是不属于$v$,同理也存在$c_v$,属于$v$但是不属于$u$。之后我们可以尝试将$(u,v)$的颜色染成$c_v$,但是这时候$v$会冲突,所以我们要解决冲突,方案就是将$v$原本染成$c_v$的关联边$(v,z)$的颜色染成$c_u$,当然可能冲突还会发生,比如$z$已经有一条颜色为$c_u$的边了,我们可以递归下去解决冲突,可以证明,递归过程中不会出现环,因此递归的时间复杂度上界是$O(V)$。总的时间复杂度上界为$O(VE)$。

这里提供一道CF题目

二分图最大匹配的唯一性

给定一个二分图,假设左边有$n$个顶点,右边有$m$个顶点,要求判断该二分图的最大匹配是否唯一。

先删除掉所有度数为$0$的顶点,因为这些的顶点不会影响结果。之后我们找到任意一个最大匹配。如果有任意一个顶点没有被匹配边所覆盖,则最大匹配一定不唯一。因此唯一的前提是匹配是完美匹配。

之后考虑完美匹配的情况下,匹配是否唯一。对于左边的顶点$i$,记其当前匹配的右边顶点的编号同样为$i$(重新对右边顶点进行编号)。这时候如果最大匹配不唯一,则一定存在另外一个置换$b_1,\ldots,b_n$,其中左边的顶点$i$与右边的顶点$b_i$匹配。由于置换可以被划分为若干个环,而置换$b$与$\pi$不相同,因此$b$中一定存在长度大于$1$的环。

我们考虑另外一幅图$G$,如果二分图存在无向边$(u,v)$(其中$u\neq v$),则在$G$中加入有向边$(u,v)$。那么可以发现我们上面提到的环对应$G$中的一个环(把有向边理解为可替换关系)。同时如果$G$中存在一个环,那么我们只需要旋转环上的顶点编号就可以得到另外一个匹配了。因此匹配唯一当且仅当$G$中不含环。

因此我们需要先跑一次最大匹配,之后跑一次判环算法即可判断最大匹配是否唯一了。时间复杂度为$O(V(V+E))$。

提供一道题目

参考资料

[1] 匹配 wiki介绍

[2] Konig定理百度百科

[3] 算法导论

[4] 二分图最大匹配的König定理及其证明

[5] Dilworth定理证明