二分图的最优匹配（KM算法）.doc
版权申诉
74 浏览量
2022-05-06
17:22:30
上传
评论
收藏 76KB DOC 举报
二分图的最优匹配（KM 算法）
算法用来解决最大权匹配问题： 在一个二分图内，左顶点为 ，右顶点为 ，现对于每组左右
连接 有权 ，求一种匹配使得所有 的和最大。
基本原理
该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问
题的。设顶点 的顶标为 ，顶点 的顶标为 ，顶点 与 之间的边权为 。在算法
执行过程中的任一时刻，对于任一条边，始终成立。
算法的正确性基于以下定理：
若由二分图中所有满足 的边构成的子图（称做相等子图）有完备匹配，那
么这个完备匹配就是二分图的最大权匹配。
首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中， 点集中的所有点都有对应的匹配
或者是
点集中所有的点都有对应的匹配，则称该匹配为完备匹配。
这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和
等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。
所以相等子图的完备匹配一定是二分图的最大权匹配。
初始时为了使 恒成立，令 为所有与顶点 关联的边的最大权，
。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等
子图具有完备匹配为止。
我们求当前相等子图的完备匹配失败了，是因为对于某个 顶点，我们找不到一条从它出发的交
错路。这时我们获得了一棵交错树，它的叶子结点全部是 顶点。现在我们把交错树中 顶点的顶标
全都减小某个值 ， 顶点的顶标全都增加同一个值 ，那么我们会发现：
）两端都在交错树中的边，的值没有变化。也就是说，它原来属于相等子图，现
在仍属于相等子图。
）两端都不在交错树中的边，和 都没有变化。也就是说，它原来属于（或不属于）
相等子图，现在仍属于（或不属于）相等子图。
） 端不在交错树中， 端在交错树中的边，它的 的值有所增大。它原来不属于
相等子图，现在仍不属于相等子图。
） 端在交错树中， 端不在交错树中的边，它的 的值有所减小。也就说，它原
来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中
这条边）
现在的问题就是求 值了。为了使 始终成立，且至少有一条边进入相等子图，
应该等于：
在交错树中， 不在交错树中。
改进
以上就是 算法的基本思路。但是朴素的实现方法，时间复杂度为 !!需要找 次增
广路，每次增广最多需要修改 次顶标，每次修改 顶标时由于要枚举边来求 值，复杂度为
。实际上 算法的复杂度是可以做到 的。我们给每个 顶点一个“松弛量”函数 "#$%&，
每次 开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边时，如果它不在相等子图
中，则让 "#$%&变成原值与 的较小值。这样，在修改顶标时，取所有不在交错树中
的 顶点的 "#$%& 值中的最小值作为 值即可。但还要注意一点：修改顶标后，要把所有的不在交错
树中的 顶点的 "#$%& 值都减去 （因为： 的定义为 '(()*+
资源评论
