算法合集之《偶图算法及应用》.doc

偶图的算法及应用
南京师范大学附属中学 孙方成
【摘要】
本文首先介绍了匹配这种无向图中特殊的关系,以及偶图这种特殊图的定义。然后将两者结合起来,介绍了偶图的最大基数匹配和最佳匹配的有效算法。同时通过给出有关偶图的最大匹配数和最小覆盖数间的数量关系,说明了和一般图相比,偶图所具有的独特优势。
【关键词】
偶图 匹配 增广路 覆盖集 算法复杂度
前言
偶图是一种特殊的图。偶图的结点总是被分成两个互补的部分,这两部分常常用来分别表示两类不同的事物。而两类事物间的最基本的关系,就是匹配的关系。如果能根据具体的情况,将偶图和匹配结合起来,则可以在很大程度上打开思路,优化算法。总之,偶图这种特殊的图,在程序设计中有着广泛的应用。它的高效性有助于对某些复杂问题的较特殊情况,给出完美的解。
匹配的概念
定义1 设图,而是的一个子集,如果中的任两条边均不邻接,则称是的一个匹配。中的一条边的两个端点叫做在下是配对的。
若匹配中的某条边与顶点关联,则称饱和顶点,并称是饱和的。
设是图的一个匹配,若中存在一条基本路径,路径的边是由属于的匹配边和不属于的非匹配边交替出现组成,则称为交替路。若的两个端点都是的非饱和点,则称这条交替路为可增广路。
设图,被分成两个非空的互补顶点子集和,若图的一个匹配能饱和中的每个顶点,换言之,中的全部顶点和中的一个子集的顶点之间确定一个一一对应关系,则称是图的一个完备匹配。
在大多数情况下,如果直接从可增广路的角度求一个图的最大(最佳)匹配,其算法效率较低。所以,对于一般图的匹配算法同时还要涉及到花苞我们把匹配边数达到最大时的奇次回路称为“花苞”。
的定义即处理。但由于本文主要考虑偶图的匹配问题,所以对这些内容不进行展开。
偶图的定义和判定
定义2 设图,若能把分成两个集合和,使得中的每条边的两个端点,一个在中,另一个在中,这样的图称为偶图,也叫二分图,或是二部图。
根据这个定义,或中任何两个顶点都不邻接。偶图也可表示为。对于顶点集,表示中所有和相连的顶点的集合。
定义3 如果偶图的互补结点子集中的每一结点都与中的所有结点邻接,则称为完全偶图。
对于较简单的图,可以用肉眼来判断其是否为偶图。然而,根据定义或用直观的改画方法判定一个较复杂的图是否是偶图是很不方便的,因此有必要寻求一个行之有效的判定定理。
定理1 当且仅当无向图的每一个回路的次数均为偶数时,才是一个偶图。如果无回路,相当于任一回路的次数为0,0视为偶数。
证:必要性,即若是偶图,则的任一回路的次数为偶数。
设中任意一个长度为m的回路。因是偶图,因此可将V分为两个互补结点子集和,因和是邻接的,设
必有同理可得
从结点的下标可以看出,下标为偶数的结点属于,而下标为奇数的结点属于,今属于,故m-1为奇数,即m为偶数。
充分性,即的任一回路的次数为偶数时,必是偶图。分两种情况进行讨论
(1)是连通图
将图的结点集合V按下列定义分为两个子集。
下面证明和就是的两个互补结点子集。
任取图的一条边,如果e的两个端点和都在中,如图所示的那样得到一个回路,因,按定义和到的距离都是偶数,再加上边e,故回路C的长度为奇数,与题设矛盾,说明和不可能都处于中。
如果任意边e的两个端点和都在中,则由定义和到的距离都是奇数,再加上边e,故回路C的长度仍为奇数,也与题设矛盾,说明和也不可能都处于中。因此只有唯一一种可能,即e的两个端点,一个在中而另一个在中,由于e是任意一条边,根据偶图的定义,是偶图。
(2)是非连通图
此时可分片讨论,对的每个连通分量应用上面的证明,然后合并起来,即可得证。
偶图的最大匹配
根据偶图的定义,它在继承了一般图的性质的同时,更有一些特殊的性质。因此,偶图的最大匹配算法相对于一般图的最大匹配算法较为简单,也有更广泛的适用性。可以说,偶图的最大匹配算法是所有偶图算法的基础。Edmonds于1965年提出了解决偶图的最大匹配的匈牙利算法。
从G中取一个初始匹配M。
若X中的顶皆为M中边的端点,止,M即为完备匹配;否则,取X中不与M中边关联的顶u,记。
若,止,无完备匹配,否则,取。
若y是M中边的端点,设,令,转(3);否则,取可增广通路
,令,转(2)。
分析上述算法,可以得到求偶图最大匹配的算法的时间复杂度为:。
在现实生活中,有很多的问题都可以转化成偶图的最大匹配问题,例如工作安排问题等。这里,举一个相对较新的例子。《小狗散步》选自NOI2001上海市选拔赛试题:
Grant喜欢带着他的小狗Pandog散步。Grant以一定的速度沿着固定路线走,该路线可能自交。Pandog喜欢游览沿途的景点,不过会在给定的N个点和主人相遇。小狗和主人同时从点出发,并同时在点汇合。小狗的速度最快