二分图最大匹配

软件一班-------郭永兴二分图最大匹配我们看这样一个例子猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被打掉，也可以在某一列中打,这样此列中的所有鸟都打掉.问至少打几枪,才能打光所有的鸟？

（猎人用的是无声枪）

如何解决？再让我们看一个例子一保守教师想带学生郊游,却怕他们途中谈恋爱,他认为满足下面条件之一的两人谈恋爱几率很小:(1)身高差>40(2)性别相同(3)爱好不同类型的音乐(4)爱好同类型的运动告诉你每个同学的信息，问老师最多能带多少学生？如何思考？搜索？怎么搜?下面将介绍一种算法，能够简单，高效的解决上面的问题，这个算法就是用来解决二分图最大匹配的匈牙利算法二分图的概念二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。二分图又常记为(X,E,Y),

X,Y是两个顶点集,

E是连接X和Y之间顶点

的边的集合112233445最大匹配给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题(maximalmatchingproblem),最大匹配的边数称为最大匹配数.如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。匈牙利算法求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。增广路的定义(也称增广轨或交错链)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。x1x2x3x4y1y2y3下面将给出匈牙利算法的图解我们假设x1和y1已近作为一种匹配（红色边表示已近是作为最大匹配集里的一个边）在从x2出发到y2这条路劲中，经过了边(x2,y1)(y1,x1)(x1,y2)其中(y1,x1)是已在匹配集合里的边，(x2,y1)(x1,y2)不是，并且，这三条边在这次路劲中是交替出现的，那么，我们可以把(x2,y1)(x1,y2)放到匹配集合里，把(y1,x1)拿出来，相当于在这个路径上进行了一次进行了一次反染色(绿的染成红的，红的染成绿的)很明显，这样的操作使得我们匹配集元素的个数增加了一。那么通过不断地像这样的搜索，直到找不到增广轨，偏可找出最大的匹配数。经过从x2的一次增广轨搜索x1x2x3x4y1y2y3代码for(i=0;i<rightNUM;i++){memset(color,0,sizeof(color));if(find(i,leftNUM))ans++;//如果从第i个点找到了增光轨，总数加一}…intfind(intright_i,intn){inti;for(i=0;i<n;i++){if(!color[i]&&map[right_i][i]){//枚举left点集中和right_i相连的所有点color[i]=1;if(match[i]==-1||find(match[i],n)){//判断是否能找到增广轨match[i]=right_i;return1;}}}return0;}让我们回顾一下前面提出的那两个问题先说第一个。猎人的目的是打到所有的鸟，言外之意不就是说所有有鸟的方格都要有子弹经过吗？方格是什么？方格不就是由行和列来唯一确定的吗？那么问题是不是就可以转化为用多少颗子弹能把所有的行和列都穿过，如果我们再联想一下，把子弹看作是边，那么问题是不是就变成了最少用多少条边可以把所有的行和列相连，把行看作是一部分点，列看作另一部分点（注意行和列只考虑有鸟的方格）这样，最大匹配数即猎人要打的枪数。再看第二个问题将男女生分为左右顶点集,

若有男女生满足身高差<=40,音乐爱好相同,运动爱好不同,则添边.保守教师带的人是此二分图的最大独立集.详细介绍请见wordword及ppt参考文献《IntroductiontoAlgorithms》ThomasH.Cormen&&CharlesE.Leiserson&&RonaldL.Riv