二分图匹配总结

【二分图】二分图是一种特殊的图结构，所有点分为两类，记做x和y，所有的边的两端分别在x和y，不存在两端同在x或y的边。

 

【最大匹配、完备匹配】

给定一个二分图(x,y)，找到一种匹配数最大的方案，记做最大匹配。|x|=|y|=匹配数时，我们称该匹配方案为完备匹配。

显然，解决了最大匹配也就解决了完备匹配。

解决二分图的最大匹配可以用网络流或者匈牙利算法，两者本质上是相同的，不过不论从编程复杂度还是运行效率来讲，匈牙利算法都更加优秀。

关于匈牙利算法，可以参见我以前写的文章：用匈牙利算法求二分图的最大匹配

 

这里我主要叙述另一类问题：

【最优完备匹配】

对于二分图的每条边都有一个权（非负），要求一种完备匹配方案，使得所有匹配边的权和最大，记做最优完备匹配。（特殊的，当所有边的权为1时，就是最大完备匹配问题）

KM算法：（全称是Kuhn-Munkras，是这两个人在1957年提出的，有趣的是，匈牙利算法是在1965年提出的）

为每个点设立一个顶标L_i，先不要去管它的意义。

设v_i,j­为(i,j)边的权，如果可以求得一个完备匹配，使得每条匹配边v_i,j=L_i+L_j，其余边v_i,j≤L_i+L_j。

此时的解就是最优的，因为匹配边的权和=∑L_i，其余任意解的权和都不可能比这个大

 

定理：二分图中所有v_i,j=L_i+L_j的边构成一个子图G，用匈牙利算法求G中的最大匹配，如果该匹配是完备匹配，则是最优完备匹配。

（不知道怎么证明）

 

问题是，现在连L_i的意义还不清楚。

其实，我们现在要求的就是L的值，使得在该L值下达到最优完备匹配。

 

L初始化：

L_i=max{w_i,j}(i∈x,j∈y)

L_j=0

 

建立子图G，用匈牙利算法求G的最大匹配，如果在某点i (i∈x)找不到增广轨，则得不到完备匹配。

此时需要对L做一些调整：

设S为寻找从i出发的增广轨时访问的x中的点的集合，T为访问的y中的点的集合。

找到一个改进量dx，dx=min{L_i+L_j-w_i,j}(i∈S,j不∈T)

L_i=L_i-dx (i∈S)

L_i=L_i+dx (i∈T)

 

重复以上过程，不断的调整L，直到求出完备匹配为止。

 

从调整过程中可以看出：

每次调整后新子图中在包含原子图中所有的边的基础上添加了一些新边。

每次调整后∑L_i会减少dx，由于每次dx取最小，所以保证了解的最优性。

 

复杂度分析：

设n为点数，m为边数，从每个点出发寻找增广轨的复杂度是O(m)，如果找不到增广轨，对L做调整的复杂度也是O(m)，而一次调整或者找到一条增广轨，或者将两个连通分量合成一个，而这两种情况最多都只进行O(n)次，所以总的复杂度是O(nm)

 

扩展：

根据KM算法的实质，可以求出使得所有匹配边的权和最小的匹配方案。

 

L初始化：

L_i=min{w_i,j}(i∈x,j∈y)

L_j=0

 

dx=min{w_i,j-L_i-L_j}(i∈S,j不∈T)

L_i=L_i+dx (i∈S)

L_i=L_i-dx (i∈T)

 

 

【最优匹配】

与最优完备匹配很相似，但不必以完备匹配为前提。

只要对KM算法作一些修改就可以了：

将原图转换成完全二分图（m=|x||y|），添加原图中不存在的边，并且设该边的权值为0。