最大匹配算法.pdf

最大匹配算法 程龚 (gcheng) 上节课的要点回顾 匹配 最大匹配增广路 完美匹配奇分支 2 本节课的主要内容 面向二部图的增广路算法 面向二部图的Hopcroft-Karp算法 面向一般图的Edmonds算法 3 / 最大匹配的充要条件 (复习) 图G 的一个匹配M是最大匹配的充分必要条件是G 中不存在 M增广路 假设存在M增广路P 将M中在P上的边替换为P上的其它边 得 到另一个匹配且势