匹配算法

Published: May 15, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• Berge定理
• 最大流算法求最大匹配
• Dinic求最大匹配
• 匈牙利算法
• 最小顶点覆盖
• 最小边覆盖
• 二分图最大独立集
• 二分图最大团
• 最小路径覆盖
• 霍尔定理
• 一类二分图匹配问题
• Kuhn-Munkres算法
• $k$正则二分图
• 二分图边染色问题
• 二分图最大匹配的唯一性
• 集线器
• 一般图匹配
• 泛化的匹配
• 参考资料

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的一个匹配。由此得出下面不等式：

$$2X=V+k\geq V+X-Y\Rightarrow X\geq V-Y$$

因此我们可以得出最小边覆盖的大小至少为$|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|$。

题目1：给定一个大小为$n\times m$的网格，每个网格的颜色是黑色或白色。现在要求找到在网格中放置最少数目的长条形状的瓷砖，要求这些瓷砖不能相互覆盖，且瓷砖只能放在黑色网格上，且要求每个黑色网格都被一块瓷砖所覆盖。要求找到使用瓷砖数最少的一种方案，且输出。其中$1\leq n,m\leq 200$

提供一道题目

我们可以认为一开始所有黑色网格上都放置一个$1\times 1$的瓷砖。我们可以删除一些黑色瓷砖之间的边界来减少使用的瓷砖数量，且被删除的瓷砖不能出现L这种形状。

我们可以将所有黑色瓷砖之间的边界视作顶点，并且对于同一个黑色网格，我们将上下边界对应的顶点和左右边界对应的顶点连边（共四条边）。

可以发现我们可以删除的边（对应的顶点）一定是一个独立集，我们要让独立集最大。可以发现左右顶点之间不存在边，上下顶点之间也是。因此我们可以将所有顶点建立成一个二分图，我们可以使用Dinic求二分图的最大匹配，时间复杂度为$O((nm)^{1.5})$。

二分图最大团

对于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$个顶点的树，记$d(u,v)$表示两个顶点的距离。要求找到一个$1$到$n$的置换$p$，使得$\sum_{i=1}^{n}d(i,p_i)$最大的前提下，使得置换$p$字典序最小。

提供一道题目。

首先我们找到树的重心。考虑以重心为根。之后考虑重心下不同子树中的顶点。要使$\sum_{i=1}^{n}d(i,p_i)$最大，需要使$\sum_{i=1}^ndepth(lca(i,p_i))$尽可能小。我们可以调整置换，将所有lca都设置为我们的重心，即根，这时候$\sum_{i=1}^ndepth(lca(i,p_i))=0$达到最小。

这时候可以发现这是一个二分图，如果$(i,j)$匹配，则将$p_i:=j$。这时候问题变成我们希望得到一个完美匹配的前提下使得匹配的字典序尽可能小。其中顶点与所有不在同一个子树中的顶点都有一条连边。

考虑到这个图的特殊性，任意左边两个不同子树中顶点的并集，它的邻集都是所有右边顶点。因此我们只需要满足同一个子树它的邻集至少比它大即可。

我们可以用线段树维护每一个子树的邻集大小减去它自身大小。之后按照编号贪心枚举顶点寻找它的匹配对象。如果这时候有一个子树$T$的邻集大小与自身大小正好相等，那么这个顶点只能在$T$中寻找匹配对象。否则可以在除自己所在子树外其它子树中寻找匹配对象。

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

题目3：给定一个二分图$(A,B)$，其中$A$与$B$中均包含$n$个顶点。每个顶点都有各自的颜色，如果$a\in A$与$b\in B$拥有不同的颜色，则二者之间建立一条边。现在要求判断是否存在完美匹配，如果存在则找到一组。其中$1\leq n\leq 10^6$。

提供一道题目。

我们将同一侧的相同颜色的顶点合并为一组。那么霍尔定理告诉我们，如果存在完美匹配，只要任意颜色的顶点数不超过$n$（等价于邻集比任意组大）。下面我们主要讲一下如何找到完美匹配。

具体的思路就是我们为每个组$g$提供一个权重$w(g)$，其值为$n-c(g)$，$c(g)$表示拥有组$g$的颜色的顶点总数。那么存在完美匹配，当且仅当对于任意$g$，有$w(g)\geq 0$。我们可以为任意选择两个顶点进行匹配，只要不违背存在完美匹配的条件。比如我们让$A$中组$a$中的一个顶点和$B$中组$b$进行匹配，这时候我们可以发现，$A$和$B$中其余组（颜色不为$a$和$b$的组）的权重全部减少$1$。因此我们可以发现每次选择$A$中权重最小的组$a$和$B$中权重最小的不同于$a$的组$b$进行匹配，这时候一定能维护完美匹配的充要条件。

具体的实现细节是维护两个优先队列，可以发现我们只需要考虑$A$组优先队列前两个组，以及$B$组优先队列的前两个组。这样可以做到$O(n\log_2n)$的时间复杂度。但是由于每次的变更量都是$1$，因此我们可以使用多个链表来代替优先队列，这样可以优化到$O(n)$的时间复杂度。

一类二分图匹配问题

题目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的题目。

给定二维平面上白点和黑点各$n$个，要求将白点和黑点进行连边，要求每个白点恰好与一个黑点连边，每个黑点也恰好与一个百点连边。要求白点和黑点连边形成的线段不能有交点。其中$1\leq n\leq 100$，且不存在三个点共线。

可以观察发现当我们已经将$W_1$和$B_1$连了边，之后将$W_2$和$B_2$连边，但是发现两条边有交点。这时候我们可以通过将$W_1$和$B_2$连边，而将$W_2$和$B_1$连边解决冲突。这时候我们发现连边的总长度是减少的（可以画图看看，实际上是将两个三角形的四条边转换为两个三角形的另外两条边，根据三角形任意两边长度大于第三边的性质容易知道）。这给了我们一个启发，我们为每条边的权重赋值为它们的长度，那么在我们取得最小权匹配的时候，不可能存在两条边相交的情况。因此我们只需要找到最小权匹配即可，这个可以通过KM算法$O(n^3)$完成。

提供一道题目。

$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))$。

2021-02-21更新

最近从这道题学习到了一种更加高效的判断唯一的方式。

首先我们将所有度数为$1$的顶点进行贪心匹配。之后如果所有顶点都被匹配了，就意味着匹配是唯一的。否则如果存在顶点度数为$0$，则意味着不存在完美匹配，自然匹配也不唯一。否则剩下的顶点的度数至少为$2$，这时候我们证明不可能存在唯一匹配。

证明方法非常简单，假设剩下的顶点存在唯一的完美匹配。我们从任意一个顶点出发，先经过其匹配边到达另外一个顶点，之后由于它的度数至少为$2$，因此一定存在一条非匹配边，我们沿着非匹配边到第三个顶点。重复这个流程，直到有一个顶点被重复访问，这时候对重复顶点两次访问之间形成的是一个匹配边和非匹配边交替的偶数长度的环。我们将环中所有边的匹配取反（匹配边变成非匹配边，同时非匹配边变成匹配边），这样我们可以得到一个不同的完美匹配。

新的方法的时间复杂度仅为$O(V+E)$，我们将所有度数为$1$的顶点加入到一个队列中处理即可。

集线器

考虑这样一个问题，我们有一个大小为$h\times w$的矩形，之后我们要往上面放$m$个棋子，要求棋子不能同行或同列。第$i$个棋子只能放在某些行列中，准确说记棋子的行为$x_i$，列为$y_i$，则必须满足$x_i\in X_i$且$y_i\in Y_i$。

要求计算最多放多少个棋子，并输出这些棋子的编号和位置。

其中$1\leq h,w,n\leq 100$。

行列限制很容易让我们想到使用二分图匹配，行建左图，列建右图，而每个网格建立边。但是这里加入了棋子的限制。

更准确来说我们实际上有很多三元组$(id,x,y)$，其中$id$表示棋子的编号。两个三元组矛盾当且仅当存在一个下标，它们在这个下标的元素相同。实际上可以将这个问题建模为三个拟阵交的最大独立集问题，当然这是NP-hard的。

我们可以考虑现实中的集线器，对于棋子$i$，我们创建一个集线器顶点$v_i$，它与所有$X_i$和$Y_i$中的顶点建立容量为$1$的边。但是我们现在还需要保证$v_i$最多只有$1$的入度和出度，这个我们可以通过将$v_i$拆分成两个点来实现。

可以发现我们会建立$O(h+w+n)$个顶点，$O((n+1)(h+w))$条边，注意到每个顶点（除了源点和汇点）都要么只有一条入边且容量为$1$，或者只有一条出边且容量为$1$，因此用Dinic可以优化到$O((h+w+n)^{1/2}(n+1)(h+w))$。

提供一道题目。

一般图匹配

这节内容只是这篇博客的一个翻译，跳过其中一些不重要的部分。

因为之前一直学不会一般图上的最大匹配的blossom算法，因此只好学一个代数版本的随机算法。

首先考虑给定的一幅图$G=(V,E)$，其中$n=|V|$。它的Tutte矩阵为：

$$\begin{equation} T(x_{12}, \dots, x_{(n-1)n}) = \begin{pmatrix} 0 & x_{12} e_{12} & x_{13} e_{13} & \dots & x_{1n} e_{1n} \newline -x_{12} e_{12} & 0 & x_{23} e_{23} & \dots & x_{2n} e_{2n} \newline -x_{13} e_{13} & -x_{23} e_{23} & 0 & \dots & x_{3n} e_{3n} \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline -x_{1n} e_{1n} & -x_{2n} e_{2n} & -x_{3n} e_{3n} & \dots & 0 \end{pmatrix} \end{equation}$$

其中$e_{i,j}$表示是否存在边$(i,j)$，存在则为$1$，否则为$0$。

考虑二分图的情况。Edmond矩阵$E$定义为：$E_{i,j}=1$当且仅当第一部分图的第$i$个顶点和第二部分图的第$j$个顶点之间有一条边，否则$E_{i,j}=0$。考虑$E$的行列式值和permanent值。

$$\begin{equation} \begin{matrix} \text{per }E=\sum\limits_{\sigma \in S_n} \prod\limits_{i=1}^n E_{i \sigma_i}, \newline \det E=\sum\limits_{\sigma \in S_n} \text{sgn }\sigma \prod\limits_{i=1}^n E_{i\sigma_i} \end{matrix} \end{equation}$$

很显然$\mathrm{per} E$代表的是$E$的完美匹配数目，而$\mathrm{det} E$没有太大实际含义。但是由于$\mathrm{det} E$对应的是一个$n$阶$(n-1)n$元多项式，因此根据Schwartz–Zippel引理，我们在$S$中随机选择$x_{i,j}$的时候，在$\mathrm{per}E\neq 0$的时候，仅$\frac{n}{|S|}$的概率，$\mathrm{det}E=0$。换言之，只要$|S|$足够大，我们可以认为$\mathrm{det}E=0$时，大概率有$\mathrm{per}E=0$，即不存在完美匹配。

回到一般图的情况，这时候Edmond矩阵转换为Tutte矩阵后如下：

$$\begin{equation} T = \begin{pmatrix} 0 & E \newline -E^T & 0 \end{pmatrix} \end{equation}$$

这时候有$\det T=\det E^2$，因此$\det T=0\Leftrightarrow \det E=0$。

对于一般斜对称矩阵，我们该如何理解它的permanent值。将置换分解为环之后，考虑单独环$(i_1, i_2, \dots, i_k)$带来的影响：

$$\begin{equation} T_{i_1 i_2} T_{i_2 i_3} \dots T_{i_k i_1}=(-1)^k T_{i_1 i_k} \dots T_{i_3 i_2} T_{i_2 i_1} \end{equation}$$

如果$k$是奇数，那么上述的两个环（其余部分完全相同）带来的贡献和为$0$，它们被抵消了。因此真正留下的只有全都是偶环的置换，这时候显然可以单独分解环，得到一个完美匹配。因此$\mathrm{per} T$表示的是图$G$中的完美匹配数。

类似二分图的Edmond矩阵，我们可以用$\det T$是否等于$0$来测试是否大概率存在完美匹配。

现在我们考虑如何找到最大匹配。实际上最大匹配等于$\mathrm{rank} T/2$。

考虑$\mathrm{rank} T=m$，一组最大线性无关行向量组为$a_1,\ldots,a_m$。由于$T$是斜对称矩阵，我们可以保证由行列由$a_1,\ldots,a_m$组成的子矩阵是非奇异的。

实际上假设得到的子矩阵是奇异的，这意味着我们可以通过一些行变换将它的第一行消为$0$，由于第$a_1,\ldots,a_m$列是最大线性无关列向量组，因此其余列可以通过这些列的线性组合得到，但是现在第一行已经被消除为$0$了，因此可以得出$T$的第$a_1$行全部为$0$，这与$a_1,\ldots,a_m$行线性无关相悖。

最后我们考虑如何找到最大匹配（这里我们假设$T$有完美匹配，否则我们通过上面的方法找到最大行线性无关组即可）。由于：

$$\begin{equation} T^{-1} = \frac{\text{adj }T}{\det T} \end{equation}$$

其中$(\mathrm{adj} T)_{i,j}$表示的是$(-1)^{i+j}$乘上$T$删除第$i$行第$j$列后子矩阵的行列式值。它实际上意味着将$T_{i,j}$修改为$1$，其它同行同列元素修改为$0$后的行列式值。换言之即如果$i$与$j$在同一个偶环中且相邻，是否存在这样的置换。在我们匹配的视野中，实际上就是是否存在完美匹配，其中$i$与$j$匹配

这样我们就找到了一种算法可以高效判断在预选一条边加入匹配的前提下，是否还能存在完美匹配。

因此如果我们发现有$T_{i,j}\neq 0$且$T^{-1}_{i,j}\neq 0$，那么我们可以断言选择了边$(i,j)$加入匹配后，依旧存在完美匹配。我们可以将$(i,j)$加入匹配，之后删除$T$的第$i,j$行列，继续求解即可。这个方法提供了一个$O(n^4)$的算法。

实际上这个方法可以提高到$O(n^3)$。对于方形矩阵$A$，令：

$$\begin{equation} \begin{matrix} A=\begin{pmatrix} a_{11} & v^T \newline u & B \end{pmatrix} & A^{-1}=\begin{pmatrix} \hat a_{11} & \hat v^T \newline \hat u & \hat B \end{pmatrix} \end{matrix} \end{equation}$$

可以推出：

$$\begin{equation} AA^{-1} = \begin{pmatrix} a_{11} \hat a_{11} + v^T \hat u & a_{11} \hat v^T + v^T \hat B \newline u \hat a_{11} + B \hat u & u \hat v^T + B \hat B \end{pmatrix} = \begin{pmatrix} I_1 & 0 \newline 0 & I_{n-1} \end{pmatrix} = I_n \end{equation}$$

进一步可以得到：

$$\begin{equation} \begin{matrix} B \hat B = I_{n-1} — u \hat v^T,\newline (u \hat a_{11} + B \hat u)\hat v^T = 0 \end{matrix} \end{equation}$$

第二部分意味着$B \hat u \hat v^T = - \hat a_{11} u \hat v^T$，除去$-\hat a_{11}$并与第一部分合并后得到：

$$\begin{equation} B\left(\hat B -\frac{\hat u \hat v^T}{\hat a_{11}}\right) = I_{n-1} \end{equation}$$

最终可以得到$B^{-1} = \hat B - \hat u \hat v^T / \hat a_{11}$，即存在$O(n^2)$的算法对$B$进行求逆。

结合我们上面的部分，总的时间复杂度可以优化到$O(n^3)$，并且成功的概率为$O(1-\frac{n}{|S|})$。

题目1：提供一副无向图，带边权。找一组最大匹配，其中最大权边和最小权边的差值最小。其中$1\leq n\leq 100$，$1\leq m\leq n^2$，无重边和自环。

提供一道题目。

先在原图上找一组最大匹配。

之后我们可以用双指针算法，维护一个最大匹配，之后尝试删除其中最小权重的边，如果删除会使得匹配减少，那么就撤销删除操作，对应的加入一条较大权重的边。

之后可以发现删除边后维护最大匹配非常容易，因为删除一条边$(u,v)$后，如果边不属于匹配，最大匹配不变，否则如果出现新的增广路，则增广路必须经过$u,v$中至少一个顶点，且很显然$u$与$v$必须是增广路的终点或起点。我们可以$O(n^2)$重新计算匹配。

加入边在匹配不是最大的情况很难维护，但是在匹配最大的情况，很显然此时匹配不会改变，因此非常容易，$O(1)$。

由于双指针，左右指针最多移动$O(m)$，总的时间复杂度为$O(n^4)$。

泛化的匹配

题目1：给定大小为$n$的无向图，两条边匹配当且仅当它们至少有一个公共端点。找到任意一个最大匹配。其中$1\leq n\leq 10^6$。

提供一道题目。

可以证明如果一个连通子图中有偶数条边，那么它一定存在完美匹配。

因此我们只需要找到每个连通块，如果连通块中有奇数条边，则删除一条没用的边（环上的或则是与叶子结点连接的边）。

算法流程非常简单，首先算出任意一株生成树，把边分为树边和非树边。

现在考虑如何找到一个连通图的完美匹配。

第一步将任意两个有公共端点的非树边进行匹配并删除。处理完这一步后所有顶点依旧连通，但是非树边没有公共端点。

第二步是找到所有深度最大的叶子顶点，如果有多个就选择与某个非树边相连的，记叶子顶点为$l$，叶子的父结点为$f$。分4种情况讨论：

1. $l$与非树边关联，则将$(l,f)$与该非树边匹配并删除。
2. $f$与非树边关联，则将$(l,f)$与该非树边匹配并删除。
3. $f$下有另外一个叶子顶点$t$，则将$(l,f)$与$(f,t)$匹配并删除。
4. 记$F$为$f$的父结点，将$(l,f)$与$(f,F)$匹配并删除。

重复上面过程就可以保证所有边最终都被匹配并删除。

题目2：给定大小为$n$的无向图，将无向图分解为若干个子图，每个子图都是连通的，并且子图包含两个或三个顶点。找到任意一个分解或报告无解，其中$1\leq n\leq 500$。保证每个顶点至少与$\lceil n/2 \rceil$个不同顶点有连边，且图中没有重边和自环。

提供一道题目。

参考资料

• 匹配 wiki介绍
• Konig定理百度百科
• 《算法导论》
• 二分图最大匹配的König定理及其证明
• Dilworth定理证明
• Randomized general matching with Tutte matrix