最大匹配算法.docx

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