匹配问题与匈牙利算法和较大基数匹配

《匹配问题与匈牙利算法和较大基数匹配》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论-浅谈匹配问题1．匹配问题的起源匹配理论起源于组合数学中著名的婚配问题：若在一个团体中有若干待婚的小伙子和姑娘，所有人都已到结婚年龄，若没有其他条件的限制，为了满足姑娘的愿望，唯一的必备条件就是小伙子的人数至少和姑娘的人数一样多。但是在事实上，所有人都不会草率地处理自己的终身大事，以姑娘为例（与小伙子的情况是完全相同的），每个姑娘往往会排除一些小伙子作为她们可能的配偶，也即每个姑娘都会有一个有序的可接受的配偶名单。那么会有一个问题出现：在这个团体中是否每个姑娘都可以嫁给自己认可的小伙子？显然，

2、上述问题并非是永远可以的，因为或许有几个姑娘手头上的名单是完全一样的。而既然上述问题并非永远可行，那么什么条件下可以满足上述要求？在并满足这些条件的时候，最多会有几位姑娘可以实现自己的愿望？如何配对，才能使得最终的团体中婚后的家庭更为美满？为了解决诸如此类的问题，人们发展得到了一种匹配理论和诸多有效算法。2．图论相关知识若图G的所有顶点能够分为两个非空子集X和Ｙ，并且每条边都有一个顶点在Ｘ中，而另一个顶点在Y中，则称此图是二分图或者偶图；而如果X的每个顶点都与Y的每个顶点相连，则称此图为完全二分图

3、或者完全偶图。设M是图G=（V,E）的边集E的子集，如果M的任何两边都不邻接，则称M为G的一个匹配；匹配M中边元素个数称为此匹配的基数，而在匹配M中边的端点称为M-饱和点，其他的端点称为M-未饱和点。10/10图论-浅谈匹配问题若G中的每个顶点都是M-饱和点，也即匹配M将G中的所有顶点进行了配对，那么称M为G的完美匹配；而在图G中不存在另一个匹配M'，使得M'>M，则称M为最大匹配，其中M称为图G的匹配数。设M是G的一个匹配，G的M交错路是指其边在EM和M中交错出现的路。M可扩路是指其起点和终点

4、都是M未饱和的M交错路。以下结论是在二分图中寻找最大匹配和最佳匹配算法的理论基础：定理1：G的匹配M是最大匹配当且仅当G不包含M可扩路。定理2：设X，Y为二分图G的二分类，则G包含饱和X的每个顶点的匹配当且仅当N(S)≥S，对所有S⊆X成立其中N(S)为G中S的临集，即为与S的顶点相邻的所有顶点的集合。定理3：G有完美匹配当且仅当oG-S≤S，对所有的S⊂V成立其中，oG-S为图G的奇分支（图的分支根据它有奇数或者偶数个顶点而分别称为奇分支或偶分支）的个数。3．几个典型的匹配算法由于刚接触到图论知

5、识，碍于在图论方面能力有限，因此本文在本节中选择性地介绍了三个图论匹配问题中比较经典的算法：婚配问题的Gale-Shapley算法、最大匹配的匈牙利算法和图论中的较大基数匹配算法，并且对匈牙利算法和较大基数匹配算法进行了matlab代码实现。10/10图论-浅谈匹配问题3.1婚配问题婚配问题可以说是一个相对经典的图论匹配算法的入门问题。假设对于n个男人的集合M={m1,m2,⋯,mn}和n个女人的集合W={w1,w2,⋯,wn}。在男人女人进行匹配的情况下，就会产生一个如何进行完美匹配的问题。在这

6、个问题背景下，进一步加入优先的概念：根据实际情况，每个男人m∈M将对所有女人进行排名，如果m给w的排名高于w'，那么我们就说m偏爱w超过w'，因此我们将把m的按顺序的排名作为他的优先表。依照常理来看，每个男人都会按照自己的优先表顺序从高向低依次进行求婚，直到被接受为止。那么，接下来本文将讨论如何生成一个稳定的完美匹配。Gale和Shapley两人根据自己对申请人-雇主之间关系的研究，提出了Gale-Shapley算法，具体算法描述如下：初始所有的m∈M和w∈W都是自由的while存在男人m是自由的

7、且还没对每个女人都求过婚选择这样的一个男人m令w为m的优先表中还没有求过婚的最高排名的女人ifw是自由的(m,w）变为约会状态elsew当前与m'约会ifw是更加偏爱m'而不爱mm保持自由elsew更加偏爱m而不爱m'10/10图论-浅谈匹配问题(m,w)变为约会状态m'变为自由endendend输出约会状态的所有匹配集合S分析Gale-Shapley算法，可以得到以下结论：结论1：G-S算法至多在n2次while循环的迭代之后终止；结论2：程序终止时返回的集合S为一个完美匹配；结论3：考虑G-S

8、算法的一次执行，结果为一个集合S，且S是一个稳定匹配；结论4：G-S算法的每次执行最终得到的匹配集合是相同的；结论5：稳定匹配集合S中，每个女人与她最差（即排名最低）的有效伴侣匹配。由结论5，在G-S算法中，主动进行求婚的一方以最佳可能的稳定匹配结束，而另一方则以最差可能的稳定匹配结束。3.2匈牙利算法二分图的匹配问题是图的最大匹配问题的特殊类型。对于一个二分图G=（X,Y,E），我们可以利用匈牙利算法对其进行最大匹配。其基本的思想为：从G的任意匹配M开始,对X中所有M的非饱和点,