ACM讲课之二分图匹配(匈牙利算法).ppt

《ACM讲课之二分图匹配(匈牙利算法).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二分图匹配什么是二分图？在离散数学中，我们都学过偶图，而偶图就是二分图。二分图：给你一个图，它的顶点可以分为两个集合，集合V1和V2，所有关联边的一个顶点在V1中，另一个顶点则在V2中。v1v2v3v4v5v1v2v3v4二分图非二分图什么是二分图匹配？二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。v1v2v3v4v5v1v2v3v4v5匹配1匹配2二分图的最大匹配最大匹配：图中包含边数最多的匹配称为图的最大匹配。今天我要讲的是无权二分图的最大匹配问题，采用匈牙利算法。匈牙利算法必备

2、知识：1.盖点：有被M中的边关联到的节点，未盖点则相反。2.增广路径：若二分图中有一条路径p，其起始点和结束点都是未盖点，其间属于M的边和不属于M的边交替出现，则称路径p是一条关于M的增广路径。匈牙利算法：计算二分图最大匹配就是应用增广路径的概念，每次寻找一条关于M的增广路径p，通过M和增广路径进行异或，使得M中的匹配数增加1。以此类推，直至二分图中不存在关于M的增广路径为止。此时得到匹配M就是图G的一个最大匹配。注：M为一个边集，M就是二分图的匹配结合增广路径的定义和下图所示，我们可以理解以下结论：1.增广路径的长度必定为奇数，第一条边和最后一条

3、边都不属于M。2.将M和增广路径进行异或操作（去同存异）可以得到一个更大的匹配M'。3.M'比M的匹配数多1。4.M为G的最大匹配当且仅当不存在M的增广路径。核心：判断当前结点为起点的增广路径是否存在。poj1274题目大意：有N头奶牛，M个产奶的棚子，每头奶牛都有自己想去产奶的几个棚子，问可以产生的最大匹配数。数据：SampleInput55NM225第一头：tm2m53234第二头：tm2m3m4215第三头：…..3125第四头：…..12第五头：…..SampleOutput4解题思路：将奶牛看成N集合，棚子看成M集合1,对于N集合中一个未

4、匹配的节点i,寻找它的每条关联边,如果它的边上的另一个节点j还没匹配则表明找到了一个匹配,直接转步骤4;2,假如节点i它边上的另一个节点j已经匹配,那么就转向跟j匹配的节点，也就是它的前驱,假设是pre[j],然后再对pre[j]重复1,2的步骤,即寻找增广路径.3,假如我们在1,2步过程中找到一条增广路,那么修改各自对应的匹配点,转步骤4,若无增广路,则退出.4,匹配数+1;234554321123455432112345543211i=1时：Pre[2]=1;2345543211123i=2时：Pre[5]=1;Pre[2]=2;2345543

5、2111i=3时：Pre[1]=3;2345543211i=4时：Pre[3]=2;Pre[2]=1;Pre[5]=3;Pre[1]=4;二分图最大匹配延伸最小点覆盖最小边覆盖最大独立集有向图最小路径覆盖最优匹配（KM算法）