二分图匹配之KM求二分图最佳匹配算法

参考网址：http://blog.163.com/suntroop@yeah/blog/static/17012103120115185927194/

对于具有二部划分( V1, V2 )的加权完全二分图，其中 V1= { x1, x2, x3, ... , xn }， V2= { y1, y2, y3, ... , yn }，边< xi, yj >具有权值 W_{i,j 。}该带权二分图中一个总权值最大的完美匹配，称之为最佳匹配。

 

记 L(x) 表示结点 x 的标记量，如果对于二部图中的任何边<x,y>，都有 L(x)+ L(y)>= W_x,y，我们称 L 为二部图的可行顶标。

设 G(V,E) 为二部图， G'(V,E') 为二部图的子图。如果对于 G' 中的任何边<x,y> 满足， L(x)+ L(y)== W_x,y，我们称 G'(V,E') 为 G(V,E) 的等价子图。

 

定理一：设 L 是二部图 G 的可行顶标。若 L 等价子图 G_L 有完美匹配 M，则 M 是 G 的最佳匹配。

证明：由于 G_L 是 G 的等价子图，M 是 G_L 的完美匹配，所以，M 也是 G  的完美匹配。以由于对于匹配 M 的每条边 e ，都有 e∈ E( G_L )，而且 M 中每条边覆盖每个顶点正好一次，所以

W( M )= ? W(e), e∈ M = ? L(x), x∈ V

另一方面，对于 G 的任何完美匹配 M' 有

W( M' )= ? W(e), e∈ M' <= ? L(x), x∈ V

于是 W( M )>= W( M' )，即 M 是 G 的最优匹配。

 

由上述定理，我们可以通过来不断修改可行顶标，得到等价子图，从而求出最佳匹配。

就像匈牙利算法一样，我们依次为每一个顶点 i 寻找增广路径，如果寻找增广路径失败，我们就修改相应的可行顶标，来得到增广路径。

如图：

|  1  2  3  |

|  3  2  4  |

|  2  3  5  |

若要对这个完全二分图求最佳匹配

 

初始化：

Lx(1)= max{ y| w(1,y), 1<= y<= 3 }= max{ 1, 2, 3 }= 3, Ly(1)= 0

Lx(2)= max{ 3, 2, 4 }= 4, Ly(2)= 0

Lx(3)= max{ 2, 3, 5 }= 5, Ly(3)= 0;

我们建立等价子图( 满足 Lx(x)+ Ly(y)== W(x,y) ) 如下：

对于该图，运用匈牙利算法对 X 部顶点 1 求增广路径，得到一个匹配，如图( 红色代表匹配边 )：

 对 X 部顶点 2 求增广路径失败，寻找增广路径的过程为 X 2-> Y 3-> X 1。我们把寻找增广路径失败的 DFS 的交错树中，在 X 部顶点集称之为 S， 在 Y 部的顶点集称之为 T。则 S= { 1, 2 }，T= { 3 }。现在我们就通过修改顶标值来扩大等价子图，如何修改。

 

1)   我们寻找一个 d 值，使得 d= min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T }，因些，这时 d= min{

Lx(1)+Ly(1)-W(1,1),  Lx(1)+Ly(2)-W(1,2),  Lx(2)+Ly(1)-W(2,1),  Lx(2)+Ly(2)-W(2,2) }=

min{ 3+0- 1, 3+0-2,  4+0-3,  4+0-2 }= min{ 2, 1, 1, 2 }= 1。

寻找最小的 d 是为了保证修改后仍满足性质对于边 <x,y> 有 Lx(x)+ Ly(y)>= W(x,y)。

 

2)   然后对于顶点 x

1. 如果 x∈ S 则 Lx(x)= Lx(x)- d。

2. 如果 x∈ T 则 Ly(x)= Ly(x)+ d。

3. 其它情况保持不变。

如此修改后，我们发现对于边<x,y>，顶标 Lx(x)+ Ly(y) 的值为

1.  Lx(x)- d+ Ly(y)+ d，  x∈ S, y∈ T。

2.  Lx(x)+ Ly(y)，  x? S,  y? T。

3.  Lx(x)- d+ Ly(y)， x∈ S, y? T。

4.  Lx(x)+ Ly(y)+ d， x? S,  y∈ T。

易知，修改后对于任何边仍满足 Lx(x)+ Ly(y)>= W(x,y)，并且第三种情况顶标值减少了 d，如此定会使等价子图扩大。

 

就上例而言: 修改后 Lx(1)= 2, Lx(2)= 3, Lx(3)= 5, Ly(1)= 0, Ly(1)= 0, Ly(2)= 0, Ly(3)= 1。

这时 Lx(2)+Ly(1)=3+0=3= W(2,1)，在等价子图中增加了一条边，等价子图变为：

 

如此按以上方法，得到等价子图的完美匹配。

 

另外计算 d 值的时候可以进行一些优化。

定义 slack(y)= min{ (x,y)| Lx(x)+ Ly(y)- W(x,y)，x∈ S,  y? T }

这样能在寻找增广路径的时候就顺便将 slack 求出。

Pku 2195 Going Home

Pku 2195 Going Home