KM算法的要点是在相等子图中寻找完备匹配，其正确性的基石是：任何一个匹配的权值之和都不大于所有顶点的顶标之和，而能够取到相等的必然是最大权匹配。但|X|!=|Y|时，完备匹配并不需要覆盖图中所有点，因此这个证明不成立，KM算法的正确性得不到保障。


举例如下：设X1，X2的点标分别为1和2，Y1，Y2，Y3的点标分别为1,2,3，相等子图中共4条边：w<X1,Y1>=2, w<X1,Y2>=3, w<X2,Y2>=4, w<X2,Y3>=5,则可见{<X1,Y1>,<X2,Y2>}是相等子图中的一个完备匹配，但显然不是最佳匹配。

网上的很多KM算法的做法都没有补点，就是用普通的写法过的，是因为数据太水了？还是这样做确实是正确的(个人表示不太相信)？

不知道我说的对不对？还请大牛们多多指教。

• 用网络流和KM算法的程序对拍跑了几万组数据，发现没什么问题。可是心里还是感觉不踏实，求严格证明 (0) Ruby931031 2013-05-20 22:39:55
• 想明白了 (247) Ruby931031 2013-05-21 14:29:41
  • Re:想明白了 (25) Liuzhaoliang 2014-08-21 08:39:43