匈牙利最大匹配算法

匈牙利算法在一个图上找到一个最大独立边集。该算法从任意匹配开始，并通过广度优先搜索构建一棵树，以找到一条增广路径，即一条路径，它起始和终止于未匹配的顶点，其第一条和最后一条边不在中，并且其边在的外部和内部交替。如果搜索成功，则和中边的对称差产生一个比多一条边的匹配。添加该边，然后执行另一次搜索以查找新的增广路径。如果搜索不成功，则算法终止，并且必须是最大尺寸的匹配。

作为额外的奖励，树数据提供了一个顶点覆盖。

如果树搜索不成功（就像在最后一样），那么顶点覆盖的大小与匹配的大小相同，这证明了最终匹配具有最大可能的尺寸。

另请参阅

增广路径, 花算法, 匹配, 匹配数, 最大独立边集

此条目由 Stan Wagon 贡献

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Brualdi, R. A. 组合数学导论，第 4 版。 纽约：爱思唯尔，1997 年。Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; 和 Schrijver, A. 组合优化。 纽约：威利，1998 年。Hopcroft, J. 和 Karp, R. "二分图最大匹配的

算法。" SIAM J. Comput. 2, 225-231, 1975 年。

Wagon, S. "匈牙利最大匹配算法。" http://demonstrations.wolfram.com/TheHungarianMaximumMatchingAlgorithm/。West, D. B. 图论导论，第 2 版。 Englewood Cliffs, NJ: Prentice-Hall, pp. 127-130, 2000 年。Zwick, U. "关于二分图和非二分图最大匹配的讲义。" http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf. 2009 年。

请引用为

Wagon, Stan. "匈牙利最大匹配算法。" 来自 MathWorld--Wolfram Web 资源，由 Eric W. Weisstein 创建。 https://mathworld.net.cn/HungarianMaximumMatchingAlgorithm.html