先说KM算法求二分图的最佳匹配思想,再详讲KM的实现。
【KM算法求二分图的最佳匹配思想】
对于具有二部划分( V1, V2 )的加权完全二分图,其中 V1= { x1, x2, x3, ... , xn }, V2= {y1, y2, y3, ... , yn },边< xi, yj>具有权值 Wi,j。该带权二分图中一个总权值最大的完美匹配,称之为最佳匹配。
记 L(x) 表示结点 x的标记量,如果对于二部图中的任何边<x,y>,都有 L(x)+L(y)>= Wx,y,我们称L 为二部图的可行顶标。
设 G(V,E) 为二部图, G'(V,E') 为二部图的子图。如果对于 G'中的任何边<x,y> 满足,......
阅读全文