#匈牙利算法和Kuhn-Munkres算法
内容摘自高随祥的《图论与网络流理论》一书
文章图片
文章图片
文章图片
文章图片
文章图片
|N(S)|或者|X|或|Y|表示的是相应集合的元素的个数。
N(S)表示与S集合中的顶点相邻接的顶点，例如，A-B-C-D中，B的邻接点就是A和C。
A-B-C-D是一条增广路，红色线表示属于M匹配，黑色线表示不属于，图中，B，C两点是M饱和的，A,D两点是非M饱和的。
文章图片
上面这个算法只是针对饱和X的，意思就是，如果X中的每个顶点都已匹配上，那么算法终止，而不必管Y中的顶点是否都有匹配。
圆圈里面一个加号的运算其实可以简单理解为增广路的取反，所谓取反就是把属于M匹配的边变成不属于M的边，把不属于M的边变为属于M的边，在那个A-B-C-D的增广路的图例中就是把A-B和C-D边变成红色而把B-C边变成黑色。这样做一个明显的作用就是匹配的边数增多了一条！
文章图片
文章图片
文章图片
下面是求二部图最大匹配的匈牙利算法，就是不管X还是Y，我们求得是含匹配边最多的匹配
文章图片
文章图片
一般的，我们会这样取顶点标号的值：l(y)全部赋值为0，而l(x)取得是和顶点x相邻接的所有的点之间的权重的最大值。下面有个例子用的就是这个方法。
文章图片
“图G的平凡标号”那个图上X集中的各顶点上的数字5,2,4,1就是顶点标号，Y集中的顶点标号全为0。
文章图片
上面这个修改标号的过程是KM算法区别于匈牙利算法的地方。修改的目的是在目前找到的M匹配的基础上增加可行顶点，从而得到增广路。
文章图片
【#匈牙利算法和Kuhn-Munkres算法】
推荐阅读
- 急于表达——往往欲速则不达
- 第三节|第三节 快乐和幸福（12）
- 20170612时间和注意力开销记录
- 2.6|2.6 Photoshop操作步骤的撤消和重做 [Ps教程]
- 对称加密和非对称加密的区别
- 眼光要放高远
- 樱花雨
- 前任
- 2020-04-07vue中Axios的封装和API接口的管理
- 烦恼和幸福