图论ppt课件匈牙利算法与最优匹配算法.ppt
1,本次课主要内容,(一)、匈牙利算法,(二)、最优匹配算法,匈牙利算法与最优匹配算法,2,(一)、匈牙利算法,1、偶图中寻找完美匹配,(1)、问题,设G=(X,Y),|X|=|Y|,在G中求一完美匹配M.,(2)、基本思想,从任一初始匹配M0出发，通过寻求一条M0可扩路P，令M1=M0E(P),得比M0更大的匹配M1(近似于迭代思想)。,(3)、M可扩扩路的寻找方法,1965年，Edmonds首先提出:用扎根于M非饱和点u的M交错树的生长来求M可扩路。,3,定义1 设G=(X,Y),M是G的匹配，u是M非饱和点。称树H是G的扎根于点u的M交错树,如果：,1)u V(T)；2)对任意v V(T),(u,v)路是M交错路。,扎根于M非饱和点u的M交错树的生长讨论：,4,假如扎根于M非饱和点u的M交错树为H,对于H,有两种情形：,情形1 除点u外，H中所有点为M饱和点，且在M上配对；,情形2 H包含除u外的M非饱和点。,5,对于情形1，令S=V(H)X,T=V(H)Y,显然：,1)若N(S)=T,由于S-u中点与T中点配对，所以有：,|T|=|S|-1,于是有：|N(S)|=|S|-1|S|.由Hall定理，G中不存在完美匹配；,2)若,令y N(S)T,且x与y邻接。因为H的所有点，除u外，均在M下配对。所以，或者x=u，或者x与H的某一顶点配对，这样，有,若y为M饱和的，设yz M,则加上顶点y及z和边xy与yz生长H，得到情形1；,6,若y为M非饱和的，加上顶点y和边xy生长H，得到情形2.,找到一条M可扩路，可以对匹配进行一次修改，过程的反复进行，最终判定G是否有完美匹配或者求出完美匹配。,根据上面讨论，可以设计求偶图的完美匹配算法。,(4)、偶图完美匹配算法匈牙利算法。,设M是初始匹配。,(a)、若M饱和X所有顶点，停止。否则，设u为X中M非饱和顶点，置S=u,T=;,(b)、若N(S)=T,则G中不存在完美匹配。否则设 y N(S)T.,7,(c)若y为M饱和点，且yz M,置S=Sz,T=Ty,转(b)。否则，设P为M可扩路，置M1=ME(P)，转(a).,例1 讨论下图G=(X,Y)是否有完美匹配。,解：取初始匹配 M=x1y2,x2y3。,(a)S=x3,T=;,8,(b)N(S)=y2,y3,N(S)T,取y2 N(S)-T,(c)y2为M非饱和点，加上y2和边x3y2生长树H。此时，置M=ME(P)=x1y1,x2y3,x3y2,9,(a)S=x4,T=;,(b)N(S)=y2,y3,N(S)T,取y2 N(S)-T,(c)y2为M饱和点，y2x3 M。此时，置S=Sx3,T=Ty2。,(b)N(S)=y2,y3 T，取y3 N(S)-T,10,(c)y3为M饱和点，x2y3 M。此时，置S=Sx2,T=Ty3。,(b)N(S)=y2,y3 T，取y3 N(S)-T,(b)N(S)=y2,y3=T，所以，G无完美匹配。,(5)、匈牙利算法复杂性分析,11,1)、最多循环|X|次可以找到完美匹配；,2)、初始匹配最多扩张|X|次可以找到完美匹配；,3)、每次生长树的生长至多2|X|-1次。,所以，算法复杂性为O(|X|3),是好算法。,2、偶图中寻找最大匹配,问题：在一般偶图上求最大匹配M.,分析：使用匈牙利算法求完美匹配时，当在扎根于M非饱和点u的交错树上有|N(S)|S|时，由Hall定理，算法停止。要求出最大匹配，应该继续检查X-S是否为空，如果不为空，则检查是否在其上有M非饱和点。一直到所有M非饱和点均没有M可扩路才停止。,12,偶图中寻找最大匹配算法：,设M是G=(X,Y)的初始匹配。,(1)置S=,T=;,(2)若X-S已经M饱和，停止；否则，设u是X-S中的一非饱和顶点，置S=Su。,(3)若N(S)=T,转(5)；否则，设y N(S)-T。,(4)若y是M饱和的，设yz M,置S=Sz,T=Ty,转(3);否则，存在(u,y)交错路是M可扩路P,置M=ME(P),转(1).,(5)若X-S=,停止；否则转(2).,13,(二)、最优匹配算法,1、问题,设G=(X,Y)是边赋权完全偶图，且X=x1,x2,xn,Y=y1,y2,yn,wij=w(xiyj)。在G中求出一个具有最大权值的完美匹配。,由于Kn,n有n!个不同完美匹配，所以枚举计算量是n!。,在匈牙利算法的基础上，Kuhn（1955）与Munkres(1957)提出了上面问题的好算法。,2、可行顶点标号与相等子图,14,定义2 设G=(X,Y),若对任意的x X,y Y,有：,称 l 是赋权完全偶图G的可行顶点标号。,对于任意的赋权完全偶图G，均存在G的可行顶点标号。事实上，设：,则 l 是G的一个可行顶点标号。,15,定义3 设 l 是赋权完全偶图G=(X,Y的可行顶点标号，令：,称Gl=G El为G的对应于l 的相等子图。,例如，设如下矩阵是赋权完全偶图G的权值矩阵并注明了一种可行顶点标号l,16,定理 设 l 是赋权完全偶图G=(X,Y的可行顶点标号，若相等子图Gl有完美匹配M*,则M*是G的最优匹配。,证明：设M*是Gl的完美匹配，则：,又设M是G的任一完美匹配，则：,所以，w(M*)w(M)。即M*是G的最优匹配。,17,根据上面定理，如果找到一种恰当可行顶点标号，使得对应的相等子图有完美匹配M*,则求出了G的最优匹配。,Kuhn采用顶点标号修改策略，找到了求最优匹配好算法，介绍如下：,给一初始顶点标号l,在Gl中任选一个匹配M。,(1)若X是M饱和的，则M是最优匹配。否则，令u是一个M非饱和点，置：S=u,T=。,(2)若，转(3)。否则，计算：,18,给出新的可行顶点标号。,(3)在NGl(S)-T中选择点y。若y是M饱和的，yz M,则置S=Sz,T=Ty转(2)。否则，设P是Gl中M可扩路，置M=ME(P),转(1).,注：该算法把匈牙利算法用于其中，主要是用来判定和求完美匹配。,19,例2，设如下矩阵是赋权完全偶图G的权值矩阵，求出其最优匹配。,解：给出初始可行顶点标号 l 为：,20,对应的相等子图Gl为：,给出初始匹配M为：,21,(1)u=x4为M非饱和顶点。置：,(2),(3)取：,y2为饱和顶点，y2x1 M,于是：,(2),(3)取：,y3为饱和顶点，y3x3 M,于是：,22,(2),于是修改标号：,由 得新标号为：,23,继续使用算法后得：,最优匹配权值为14.,例3 证明：K6n-2有一个3因子分解。,证明：K6n-2=K 2(3n-1),所以，可以分解为6n-3个边不重的1因子之和。而任意3个1因子可以并成一个3因子。所以，共可以并成2n-1个3因子。即K6n-2可以分解为2n-1个3因子的和。,24,例4 证明：对n1,K4n+1有一个4因子分解。,证明：K4n+1=K 2(2n)+1,所以，可以分解为2n个边不重的2因子之和。而任意2个2因子可以并成一个4因子。所以，共可以并成n个4因子。即K4n+1可以分解为n个4因子的和。,例5 设H是有限群，K是H的子群。证明：存在元素h1,h2,hn H,使得h1K,h2K,hnK都是K的左陪集。而Kh1,Kh2,Khn都是K的右陪集。,注:(1)上面结论是群论学家Hall的一个结论。群论是近世代数的重要组成部分。在数学、计算机科学、理论物理学(量子场论)中都有重要应用。是数学领域里最引人关注的方向和主流研究方向之一。创立者伽罗瓦。,25,(2)伽罗瓦(1811-1832)中学时受到数学老师里沙的影响而对数学产生极大兴趣。里沙对教学工作十分负责，且具有很高数学才能，但把精力耗在了学生身上，欣慰的是培养了好几位欧洲杰出数学家。中学时的伽罗瓦 在里沙帮助下创立了群论。群论是19世纪最突出的数学成就。有点象相对论在物理学中的地位。,在法国历史上著名的1830年的“七月革命”中，伽罗瓦两次入狱，成为坚强斗士。1832年5月，21岁的他因为反动派设下的爱情圈套，被迫决斗至死。这是他犯下的草率的错误。,26,证明：由陪集的性质：H中的任意两个左(右)陪集,要么相等，要么没有共同元素。所以H可按某子群的左(右)陪集，划分为左(右)陪集族。如果K是H的子群，则aK或者Kb的元素个数等于K中元素个数。,设|K|=k。且假设子群K在群H中的指数为n。我们构造偶图G=(X,Y)如下：,X表示H关于K的左陪集族，Y表示H关于K的右陪集族。对于x X,y Y,x与y间连接 l 条边，当且仅当左陪集x和右陪集y有l个共同元素。,显然G是k正则偶图，于是存在完美匹配M。|M|=n,在M中的边ei的两端点的陪集中选取共同元素hi,则这些元素为所求。(1in）。,27,匹配在矩阵中的应用,1、矩阵与偶图,设A=(aij)是n阶方阵。构造偶图G=(X,Y)如下：,X表示行集合，Y表示列集合。X中元素xi与Y中元素yj连线，当且仅当aij0,28,2、下面研究detA和GA=(X,Y)之间关系,若|S|=n,则在A中存在n行，这n行中至多有n-1列元非零，而其余的-n+1列中每个元素为零。即得到A中有一个 零子阵。,29,于是有如下定理：,30,作业,P117-118 习题4：13,31,Thank You!,
