资源描述：
《二分图匹配算法及其应用【毕业论文】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、本科毕业论文（20届）二分图匹配算法及其应用专业：数学与应用数学16摘要图的匹配理论简单的说就是使得图中每两个点之间都有联系.匹配理论是图论中的一个重要内容,它在运筹学、系统工程中都有着广泛的应用,近几十年来,随着组合数学的迅速发展,匹配理论成为许多重要理论的基础和源泉.二分图的最大匹配算法是匹配理论研究的热点之一.KM算法是求最大权匹配的经典算法,它是在匈牙利算法的进一步提高,它是解决数学中一类存在性问题的基本工具,广泛应用于社会、经济、科技、自然等各个领域中.本文主要研究KM算法的具体原理,步骤,以及它一些实际问题中的应用.关键词:二分图;匹配;KM算法;应用;工作分派16Binary
2、ChartMatchingAlgorithmsandItsApplicationAbstractChartmatchingtheorysimplymeansthatitmakeseverytwopointsingraphhaverelations.Matchingtheoryisanimportantcontentofgraph,ithasbeenwidelyusedinbothoperationsresearch,systemengineering,inrecentdecades,withtherapiddevelopmentofcombinatorialmathematics,matc
3、hingtheoryhasbecomethefoundationandsourceofmanyimportanttheories.Thebiggestmatchingalgorithmofbinarychartisthehotspotofmatchingtheory.KMalgorithmisaclassicalalgorithmsofobtainingmaximummatching,itisfurtherimprovementofHungaryalgorithm,itisabasictooltosolveakindofexistenceproblemsinmathematics,wide
4、lyusedareasofsociety,economic,technology,nature,etc.Thisarticlemainlystudiesthespecificprinciple,modificationsoftheKMalgorithm,andalsostudiestheapplicationsofsomeactualproblems.Keywords:Binarychart;Matching;KMalgorithms;Application;Referral16目录摘要IAbstractII1前言12二分图最大权匹配的KM算法32.1相关定义及其定理32.2KM算法的步骤
5、63KM算法的应用93.1KM算法在工作分派中的应用93.2KM算法在镜头检索中的应用134小结16参考文献17致谢18161前言现实世界中,许多问题的数学抽象形式可以用图来描述,如互联网、通讯网、集成电路、分子结构等.为了方便对这些问题的探索,通过几百年来我们对图的研究,从而形成了一个专门的数学学科:图论.图的匹配理论简单的说就是使得图中每两个点之间都有联系.图的匹配理论是图论中的一个重要的内容.近几年来,随着组合数学的迅速发展,匹配理论成为许多重要的理论的基础和源泉.二分图的最大权匹配问题已成为匹配理论研究的热点问题之一,引起了广大学者的研究和关注,并应用到实际中.KM算法是解决这类问
6、题的经典算法,二分图最大权匹配的KM算法看似简单,但二分图最大权匹配在数学的许多领域中都有着广泛的应用,同时它的局限性也很明显.用KM算法解决二分图最大权匹配问题使它的许多重要性质仍然得以保留,成为二分图最大权匹配新的研究方向.图的匹配问题起源于1935年霍尔的“婚姻问题”.当时他成功地解决了下面问题:有个小伙子和个姑娘,每个小伙子认识个姑娘中的某些人,问在什么条件下每个小伙子能够找到一个他认识的姑娘结婚?该问题抽象为图论问题为用个顶点代表个小伙子,用个顶点代表个姑娘.当且仅当小伙子认识姑娘时在和之间连一条边.上面问题则抽象为在什么条件下这个图中存在条边分别以为端点,使这些边中任意两条边都
7、没有公共端点?很显然对于“婚姻问题”有解的一个必要条件是任意个小伙子认识的姑娘总数至少为个.霍尔证明了这个条件也是充分的.这就构成了一个关于二分图的匹配问题.而在上面问题中加上一个条件,就是每位小伙子对各个姑娘的喜欢程度又各不相同,并将每位小伙子对各个姑娘的喜欢程度赋予为每条边的权值,这就将求二分图的完全匹配问题转化为求二分图的最大权匹配问题.而KM算法是Kuhn和Munkras分别于1955年和1957年独立提出来的,
