二分图匹配算法及其应用【文献综述】

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

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

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

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

4、设为二分图,当给赋予映射或,为任意集合、常用实数集及其子集,此时为赋权图,常用或或表示之.称为结点的权,称为的权.定义6设为二分图,.称为的一个匹配,如果中任何两条边都没有公共端点.的所有匹配中边数最多的匹配称为最大匹配,其边数称为匹配数.如果()中任一顶点均为匹配中边的端点,那么称为()—完全匹配.若既是—完全匹配又是—完全匹配,则称为的完全匹配.定义7设二分图,其中==匹配数,中每条边有权,若能找到一个匹配(=匹配数),满足所有匹配的边权和最大(或最小),则称为的一个最大(或最小)权匹配.定义8称图中顶点到是可达的,

5、如果,或者有一条到的路径.如果的任何两个顶点都是互相可达的,称无向图是连通的.如果是的子图,是连通的,并且不存在的真子图,使是连通的,且以为真子图,则图称为图的连通分支.定理1(霍尔定理)设图.有—完全匹配的充分必要条件是:对每一,其中为的邻域,即,则有.定理2(Tutte定理)一个图有完全匹配当且仅当对图的任意顶点子集有图的奇分支数不大于中的顶点数,其中表示从图中删去顶点集及其关联的边所得的图,图的奇分支是指奇数个顶点的连通分支.定理3若由二分图中所有满足的边构成的子图(称做相等子图)有完全匹配,那么这个完全匹配就是二

6、分图的最大权匹配.Kuhn－Munkras算法(即KM算法)流程(1)初始化可行顶标的值;(2)用匈牙利算法寻找完备匹配;(3)若未找到完全匹配则修改可行顶标的值;(4)重复(2)(3)直到找到相等子图的完全匹配为止.KM算法是通过给每个顶点一个标号(我们有时称之为顶标)来把求最大权匹配的问题转化为不断地寻找增广路以使二分图的匹配数达到最大的完全匹配的问题.我们令二分图中部的节点的顶标为.部的节点的顶标为.部与部节点之间的权值为.要求在算法执行过程中的任一时刻，对于任一条边,使得始终成立.在初始时,令为所有与顶点关联的边

7、的权值的最大值,令.如果当前的相等子图没有完全匹配,就需要修改顶标以使扩大相等子图,直到相等子图具有完全匹配为止(这样就可以求出最大权匹配).如果当前相等子图找不到完全匹配,那么是因为对于某个顶点,我们找不到一条从它出发的增广路.这时为了获得了一条增广路,现在我们把增广路中的顶点的顶标全都减小某个值,的顶点的顶标全都增加,就可以使得至少有一条新边进入相等子图.那么我们会发现:(1)两端都在增广路中的边,的值没有变化.也就是说,它原来属于相等子图,现在仍属于相等子图.(2)两端都不在增广路中的边,和都没有变化.也就是说,它

8、原来属于(或不属于)相等子图,现在仍属于(或不属于)相等子图.(3)端不在增广路中,端在增广路中的边,它的的值有所增大.它原来不属于相等子图,现在仍不属于相等子图.(4)端在增广路中,端不在增广路中的边,它的的值有所减小.也就说,它原来不属于相等子图,现在可能进入了相等子图,因而使相等子图得到了扩大.现在的问题就是求