最大权匹配算法优化指南

二分图的权匹配就是求出一个匹配集合，使得集合中边的权值之和最大或最小。而所谓最大权匹配（最优匹配）是指对于二分图的每条边都有一个权（非负），要求一种完备匹配方案，使得所有匹配边的权和最大[275]。

定义2.4 设G为具有二划分（X，Y）的二分图，|X|≤|Y|，M为G中一个最大基数匹配，且|M|=|X|，则称M为G的完备匹配。

在上述定义中，若|X|=|Y|，则完备匹配即为完美匹配，若|X|≤|Y|，则完备匹配为G中最大基数匹配。

定义2.5 图G的顶点标号是从顶点集到正整数集的一个映射。用l（v）表示顶点v的标号，w（uv）表示边u，v的权。对于赋权二分图G=（X，Y），若对每条边e=xy，均有l（x）+l（y）≥w（xy），则称这个标号为G的一个可行顶点标号。

定义2.6 设G=（X，Y）是一个赋权二分图，l是G的可行顶点标号，边（u，v）上的权为w（uv），令El={xy∈E（G|l（x）+l（y）=w（x y）}，G中以El为边集的生成子图称为G的l相等子图，记为Gl。

定理2.7 设l是赋权二分图G的一个可行顶点标号，若相等子图Gl有完美匹配，则该完美匹配是G的最大权完美匹配。(www.xing528.com)

求解最大权匹配的Kunh-Munkres算法基本思想为：首先给出赋权二分图G的任意一个可行顶点标号，然后决定相等子图Gl，在Gl中执行匈牙利算法。若在Gl中找到完美匹配，则由上面定理2.7可知，它就是G的最大权完美匹配。否则，匈牙利算法终止于S⊂X，T⊂Y，且NGl（S）=T。求解最大权匹配的Kunh-Munkres算法如下：

Step1：给G=（X，Y）添加一些可行顶点和权为0的边，使其成为赋权完全二分图，记为G。

Step2：从G的任何一可行的顶点标号l开始，求出相等子图Gl。

Step3：在Gl中执行匈牙利算法，如果求得Gl的一个完美匹配M，则算法停止；否则，匈牙利算法必将终止于两个集合S⊂X，T⊂Y，且NGl（S）=T，此时转下一步。

Step4：计算αl=min{l（x）+l（y）-w（xy）|x∈S，y∈Y-T|}，并计算G的新的可行顶点标号l′，以l′代替l，Gl′代替Gl，转Step3。