资源描述：
《二分图最大匹配及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、二分图最大匹配及其应用二分图与图的匹配二分图的概念匹配的概念例1.THEPERFECTSTALL题目来源：USACO,POJ1274农夫John的牛棚共有M个牛栏，其中一共养了N头奶牛。每头奶牛只愿意在它喜欢的那些牛栏中产奶。一个牛栏只能容纳一头奶牛，一头奶牛也只在一个牛栏中产奶。请你将奶牛分配到牛栏中，使得愿意产奶的奶牛数T最大。限制：N≤200，M≤200。题目描述例1.THEPERFECTSTALL样例：N=5,M=5方案：1-5,2-3,3-1,5-2解释：5号奶牛只能去2号，那么1号奶牛只能去5号，3号奶牛只能去1号，于是4号奶牛无论如何都不能被分配到喜欢的牛栏。分析样例
2、奶牛编号喜欢的牛栏12,522,3,431,541,2,552例1.THEPERFECTSTALL如果题目的规模比较小，那么有什么方法？暴力搜索：O(N!)，当N≥12时已经难以在时限内出解。在暴力搜索的基础上优化？状态压缩+记忆化搜索（动态规划）暴力搜索例1.THEPERFECTSTALL考虑用图论模型来表示题给的条件。将每一头奶牛、每一个牛栏都作为图的顶点：i号奶牛对应顶点Xi，j号牛栏对应顶点Yj。如果i号奶牛喜欢j号牛栏，那么连边(Xi,Yj)。建立图论模型例1.THEPERFECTSTALL注意到如果对于1号奶牛选择1号牛栏，2号奶牛选择2号牛栏的情况，答案为t，那么对于
3、1号奶牛选择2号牛栏，2号奶牛选择1号牛栏的情况（即交换两头奶牛选择的牛栏），答案仍为t。从中得到启发，其实很多状态是冗余的。只需记录有哪些奶牛和牛栏没有被用过，答案就确定了，而那些用过的奶牛和牛栏不需要考虑。发现冗余状态例1.THEPERFECTSTALL用f[i][S]表示在前i头奶牛已经选择的牛栏集合为S的情况下，其余的奶牛最多能有多少可以选择喜欢的牛栏。S是一个二进制数，其中S的第k位如果是1则表示k号牛栏已经被使用，否则k号牛栏可以被后面的奶牛使用。对于状态f[i][S]，枚举i号奶牛使用的牛栏j（要满足S的第j位是0），则f[i][S]就是所有f[i-1][S-{j}]
4、的最大值加1。状态压缩例1.THEPERFECTSTALL由于转移的时间复杂度为O(M)，所以总的时间复杂度为O(M2M)。空间复杂度似乎也是O(M2M)。注意到每当i减少1时，S中含的元素也会少1个，所以通过S就可以唯一确定i，因此状态中只需要记录S，从而空间复杂度降为O(2M)。这个算法可以解决N≤20的数据。如果规模更大，还有办法解决吗？复杂度分析例1.THEPERFECTSTALL不难发现这个图的特点：可以将图的顶点划分为两个集合X,Y，使得图的任何一条边的一个端点在X中，另一个端点在Y中。满足这个条件的图称为二分图（二部图）。可以证明，一个图是二分图等价于图中不含长度为奇
5、数的环。对于一个二分图G，如果X中的每个顶点都与Y中的每个顶点有边相连，则称G为完全二分图。二分图的概念例1.THEPERFECTSTALL本题就是要求从图中选出尽可能多的边，满足每个顶点至多是其中一条边的端点。设G=(V,E)是一个图，M是E的一个子集。如果M中的任何两条边都没有共同的端点，则称M为G的一个匹配。G中边数最多的匹配称为G的最大匹配。要求一般图的最大匹配是比较困难的，但是求二分图的匹配就容易得多。本题就是求二分图最大匹配的问题。匹配的概念求二分图最大匹配的算法网络流匈牙利算法Hopcroft-Karp转化为求最大流的问题可以将求二分图最大匹配的问题转化为最大流的问题
6、。增加两个顶点S、T。对于X中的每个顶点Xi，连边(S,Xi)，容量为1。对于Y中的每个顶点Yj，连边(Yj,T)，容量为1。对于原图中的边(Xi,Yj)，将容量设为1。显而易见，S到T的最大流就是原图的最大匹配。建立网络流模型匈牙利算法然而，用网络流算法求最大匹配，显得过于麻烦。利用二分图的特殊性质，将求最大流的算法简化，就得到了匈牙利算法。匈牙利算法的实质匈牙利算法设M是图G=(V,E)的一个匹配。若顶点v是M中某条边的端点，则称v是M的饱和点，否则称v为M的非饱和点（未盖点）。如果G的每个顶点都是M的饱和点，则称M是G的一个完备匹配（完美匹配）。基本概念匈牙利算法设M是G的一
7、个匹配，P是G的一条链。如果P的边交替地一条是M中的边，一条不是M中的边，则称P为M的交错轨。如果交错轨P连接的是两个非饱和点，则称P是增广路（增广链，增广轨）。不难发现，对于增广路P，将在M中的边删去，而将不在M中的边加上，那么得到的仍然是一个匹配，但匹配数增加了1。这就是匈牙利算法的原理。实现原理匈牙利算法形象化地说，就是从二分图中找出一条路径，使得路径的起点和终点都是没有被匹配的点，而且路径经过的边是一条没被匹配，一条已经匹配过，再下一条又没匹配这样交替地出现。
