NOIP考点-二分图详解（2）

◆ ◆ ◆

导

语

READ

        二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

二分图的匹配之KM算法

上一篇文章中梳理了匈牙利算法，匈牙利算法是求解二分图中的最大基数匹配算法，这一节我们学习二分图中的最大权重匹配算法——KM算法。

其基本过程如下：

（1）初始化可行标杆

（2）用匈牙利算法寻找完备匹配

（3）若未找到完备匹配则修改可行标杆

（4）重复2，3直到找到相等子图的完备匹配

       下面，我们举例说明该算法，二分图的两个集合X和Y，X={a1,b1,c1,d1,e1}，Y={a2,b2,c2,d2,e2}，其边权矩阵为

	a2	b2	c2	d2	e2
a1	3	5	5	4	1
b1	2	2	0	2	2
c1	2	4	4	1	0
d1	0	1	1	0	0
e1	1	2	1	3	3

        算法执行过程如下：

（1）给二分图顶点初始化可行标杆：l(xi)=max(wij)，l(yj)=0，则l(a1)=5，l(b1)=2，l(c1)=4，l(d1)=1，l(e1)=3，l(a2)=l(b2)=l(c2)=l(d2)=l(e2)=0。

（2）求最大权重的邻接点集：A(xi)={yj|yj∈Y,l(xi)+l(yj)=wij}，则A(a1)={b2,c2}，A(b1)={a2,b2,d2,e2}，A(c1)={b2,c2}，A(d1)={b2,c2}，A(e1)={d2,e2}。该邻接点集即为最初的二分子图（是具有最大权重的），即

          

则M={a1c2，b1a2，c1b2，e1d2}(利用匈牙利算法的DFS算法)。

（3）若M已经渗透X中所有点，则M为最大权重匹配，停止；否则，取X中的非M渗透点u，对u进行增广路径的寻找，若成功寻找，则继续匹配，否则，列出集合S和T，（寻找增广路径失败的DFS的交错树中，并且叶子顶点为X中顶点），S即为该交错路中的X中顶点的集合，T即为该交错路中Y中顶点的集合。

       来看我们的例子，从d1出发寻找交错树，d1->b2=>c1->b2=>a1，寻找交错树失败，则S={a1,c1,d1}，T={b2,c2}，则计算d=min{L(xi)+L(yj)-weight(xiyj)}(xi∈X,yj∈Y-T，其意义在于，选择一条新的边加入到匹配子图中使匹配合法，且权重和最大权重相差最小，是合法匹配中权重最大的)。d(a1a2)=5+0-3=2，d(a1d2)=5+0-4=1，d(a1e2)=5+0-1=4，d(c1a2)=4+0-2=2，d(c1d2)=4+0-1=3，d(c1e2)=4+0-0=4，d(d1a2)=1+0-0=1，d(d1d2)=1+0-0=1，d(d1e2)=1+0-0=1，则d=1，将S集合中的X的标杆减去d，T集合中的Y的标杆加上d，则l(a1)=4，l(c1)=3，l(d1)=0，l(b2)=1,l(c2)=1，在上图的基础上加入这些具有最小d的边，则形成新图如下：

          

   则找到d1->d2，加入匹配M，则结束。

◆ ◆ 

好

消

息

由清北学堂信息学金牌教研团队策划的