二分图匹配算法及其应用【毕业论文+开题报告+文献综述】

《二分图匹配算法及其应用【毕业论文+开题报告+文献综述】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科毕业论文开题报告数学与应用数学二分图匹配算法及其应用一、综述本课题国内外研究动态,说明选题的依据和意义图的匹配理论简单的说就是使得图中每两个点之间都有联系.匹配理论是图论中的一个重要内容,它在运筹学、系统工程中都有着广泛的应用,近几十年来,随着组合数学的迅速发展,匹配理论成为许多重要理论的基础和源泉.二分图的最大匹配算法是匹配理论研究的热点之一.KM算法是求最大权匹配的经典算法,它是在匈牙利算法的进一步提高,它是解决数学中一类存在性问题的基本工具,广泛应用于社会、经济、科技、自然等各个领域中.本文主要研究KM算法的具体原理,步骤,以及它一些实际问题中的应用.图的匹配问题起源于1935年霍尔

2、的“婚姻问题”.KM算法是Kuhn和Munkras分别于1955年和1957年独立提出来的,他们在研究图论中最大权匹配问题时很巧妙运用KM算法去解决问题.定义1图有三部分所组成(1)非空集合,称为的结点集,其成员称为结点或顶点.(2)集合,称为的边集,其成员称为边.(3)函数,称为边和顶点的关联映射.这里称为的偶对集,其成员偶对形如,,为结点,它们未必不同.当时,称边关联端点,.当用作序偶时,称为有向边,以为起点,以为终点,图称为有向图;当用作无序偶对时,,称为无向边(或边),图称为无向图(或图).16定义2无向图称为二分图,如果有非空集合,使,,且对每一,,,.此时常用表示二分图.若对中任一

3、及中的任一恰有一边,使,则称为完全二分图.当,时,完全二分图记为.定义3图的顶点到顶点的拟路径是指如下顶点与边的序列:其中为的顶点,为的边,且以及为端点(对有向图,以为起点,以为终点).当各不相同时,该拟路径称为路径.定义4若是二分图的一个匹配.设从图中的一个顶点到另一个顶点存在一条路径,这条路是由属于的边和不属于的边交替出现组成的,则称这条路为增广路(或称交互树或交错树).如果增广路的首尾两个顶点不属于,则称这条路为可增广路.定义5设为二分图,当给赋予映射或,为任意集合、常用实数集及其子集,此时为赋权图,常用或或表示之.称为结点的权,称为的权.定义6设为二分图,.称为的一个匹配,如果中任何两

4、条边都没有公共端点.的所有匹配中边数最多的匹配称为最大匹配,其边数称为匹配数.如果()中任一顶点均为匹配中边的端点,那么称为()—完全匹配.若既是—完全匹配又是—完全匹配,则称为的完全匹配.定义7设二分图,其中==匹配数,中每条边有权,若能找到一个匹配(=匹配数),满足所有匹配的边权和最大(或最小),则称为的一个最大(或最小)权匹配.定义8称图中顶点到是可达的,如果,或者有一条到的路径.如果16的任何两个顶点都是互相可达的,称无向图是连通的.如果是的子图,是连通的,并且不存在的真子图,使是连通的,且以为真子图,则图称为图的连通分支.定理1(霍尔定理)设图.有—完全匹配的充分必要条件是:对每一,

5、其中为的邻域,即,则有.定理2(Tutte定理)一个图有完全匹配当且仅当对图的任意顶点子集有图的奇分支数不大于中的顶点数,其中表示从图中删去顶点集及其关联的边所得的图,图的奇分支是指奇数个顶点的连通分支.定理3若由二分图中所有满足的边构成的子图(称做相等子图)有完全匹配,那么这个完全匹配就是二分图的最大权匹配.刘桂真[1]对二分图最大权匹配开讨论,介绍了二分图最大权匹配并将匹配问题从“婚姻问题”推广到工作分派问题.耿素云[2]通过对二分图的匹配及带权图的应用进行了讨论也将其运用到实际中,并以此解决了最短路径问题、关键路径问题以及中国邮递员问题.杨胜超、张瑞军[3]将在介绍毕业论文选题系统的系统

6、用例、功能模块、和流程图的基础上,针对学生选题不均衡这一突出问题,引出了二分图最大权匹配的经典算法—KM算法,该算法能够根据学生的题目预选、自命题、未定题等多种情况,完成题目与学生的智能匹配,使最终题目的整体满意度最高,从而提高学生毕业论文选题质量.该系统在武汉科技大学管理学院04级毕业论文选题中实施.谢政、程浩光[4]利用赋双权的二分图中求关于第一个权最大的限制下、第二个权最小的完美匹配的网络模型，给出了这一模型的有效性，并用此算法解决了企业的优化组合分工中的挖潜问题.彭宇新,NgoChong-Wah,肖建国[5]利用尝试将二分图的最大权匹配用于镜头检索.把两个镜头的相似度度量建模为一个带权

7、的二分图:镜头中的每一帧看成二分图的一个结点,两个镜头之间任意帧的相似值作为边的权值.在一一对应的前提下,利用最大权匹配的KM算法求出该二分图的最大权,以此作为两个镜头的相似度.考虑到检索的速度的问题,提出了两个改进算法.对于二分图最大权匹配的算法有不少,如:顶点标记法等.但KM16算法是求解二分图最大权匹配的经典算法.本文主要研究用KM算法解决二分图最大权匹配的步骤过程及二分图最大权匹配算法的一