1图论及其应用应用数学学院2本次课主要内容(一)、匈牙利算法(二)、最优匹配算法匈牙利算法与最优匹配算法3(一)、匈牙利算法1、偶图中寻找完美匹配(1)、问题设G=(X,Y),|X|=|Y|,在G中求一完美匹配M.(2)、基本思想从任一初始匹配M0出发,通过寻求一条M0可扩路P,令M1=M0ΔE(P),得比M0更大的匹配M1(近似于迭代思想)。(3)、M可扩扩路的寻找方法1965年,Edmonds首先提出:用扎根于M非饱和点u的M交错树的生长来求M可扩路。4定义1设G=(X,Y),M是G的匹配,u是M非饱和点。称树H是G的扎根于点u的M交错树,如果:1)u∈V(T);2)对任意v∈V(T),(u,v)路是M交错路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根x3的M交错树扎根于M非饱和点u的M交错树的生长讨论:5假如扎根于M非饱和点u的M交错树为H,对于H,有两种情形:情形1除点u外,H中所有点为M饱和点,且在M上配对;x4ux2y4y3y2扎根u的M交错树Hx5情形2H包含除u外的M非饱和点。x4ux2y4y3y2扎根u的M交错树H6对于情形1,令S=V(H)∩X,T=V(H)∩Y,显然:1)若N(S)=T,由于S-{u}中点与T中点配对,所以有:()TNS|T|=|S|-1,于是有:|N(S)|=|S|-1|S|.由Hall定理,G中不存在完美匹配;2)若()TNS令y∈N(S)–T,且x与y邻接。因为H的所有点,除u外,均在M下配对。所以,或者x=u,或者x与H的某一顶点配对,这样,有xyM若y为M饱和的,设yz∈M,则加上顶点y及z和边xy与yz生长H,得到情形1;7若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.8(c)若y为M饱和点,且yz∈M,置S=S∪{z},T=T∪{y},转(b)。否则,设P为M可扩路,置M1=MΔE(P),转(a).例1讨论下图G=(X,Y)是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X,Y)解:取初始匹配M={x1y2,x2y3}。(a)S={x3},T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)9(b)N(S)={y2,y3},N(S)≠T,取y2∈N(S)-T(c)y2为M非饱和点,加上y2和边x3y2生长树H。此时,置M=MΔE(P)={x1y1,x2y3,x3y2}x1x2x3x4x5y1y2y3y4y5G=(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)10(a)S={x4},T=Φ;x1x2x3x4x5y1y2y3y4y5G=(X,Y)(b)N(S)={y2,y3},N(S)≠T,取y2∈N(S)-T(c)y2为M饱和点,y2x3∈M。此时,置S=S∪{x3}T=T∪{y2}。(b)N(S)={y2,y3}≠T,取y3∈N(S)-Tx4y2x311(c)y3为M饱和点,x2y3∈M。此时,置S=S∪{x2}T=T∪{y3}。(b)N(S)={y2,y3}≠T,取y3∈N(S)-Tx1x2x3x4x5y1y2y3y4y5G=(X,Y)(b)N(S)={y2,y3}=T,所以,G无完美匹配。(5)、匈牙利算法复杂性分析121)、最多循环|X|次可以找到完美匹配;2)、初始匹配最多扩张|X|次可以找到完美匹配;3)、每次生长树的生长至多2|X|-1次。所以,算法复杂性为O(|X|3),是好算法。2、偶图中寻找最大匹配问题:在一般偶图上求最大匹配M.分析:使用匈牙利算法求完美匹配时,当在扎根于M非饱和点u的交错树上有|N(S)||S|时,由Hall定理,算法停止。要求出最大匹配,应该继续检查X-S是否为空,如果不为空,则检查是否在其上有M非饱和点。一直到所有M非饱和点均没有M可扩路才停止。13偶图中寻找最大匹配算法:设M是G=(X,Y)的初始匹配。(1)置S=Φ,T=Φ;(2)若X-S已经M饱和,停止;否则,设u是X-S中的一非饱和顶点,置S=S∪{u}。(3)若N(S)=T,转(5);否则,设y∈N(S)-T。(4)若y是M饱和的,设yz∈M,置S=S∪{z},T=T∪{y},转(3);否则,存在(u,y)交错路是M可扩路P,置M=MΔE(P),转(1).(5)若X-S=Φ,停止;否则转(2).14(二)、最优匹配算法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、可行顶点标号与相等子图15定义2设G=(X,Y),若对任意的x∈X,y∈Y,有:()()()lxlywxy称l是赋权完全偶图G的可行顶点标号。对于任意的赋权完全偶图G,均存在G的可行顶点标号。事实上,设:()max(),,()0,.yYlxwxyxXlyyY若若则l是G的一个可行顶点标号。16定义3设l是赋权完全偶图G=(X,Y的可行顶点标号,令:称Gl=G[El]为G的对应于l的相等子图。()()()()lExyEGlxlywxy例如,设如下矩阵是赋权完全偶图G的权值矩阵并注明了一种可行顶点标号l3554122022244100110012133W0000054213x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)17定理设l是赋权完全偶图G=(X,Y的可行顶点标号,若相等子图Gl有完美匹配M*,则M*是G的最优匹配。证明:设M*是Gl的完美匹配,则:*()(*)()()eMvVGwMwelv又设M是G的任一完美匹配,则:()()()()eMvVGwMwelv所以,w(M*)≥w(M)。即M*是G的最优匹配。18根据上面定理,如果找到一种恰当可行顶点标号,使得对应的相等子图有完美匹配M*,则求出了G的最优匹配。Kuhn采用顶点标号修改策略,找到了求最优匹配好算法,介绍如下:给一初始顶点标号l,在Gl中任选一个匹配M。(1)若X是M饱和的,则M是最优匹配。否则,令u是一个M非饱和点,置:S={u},T=Φ。(2)若,转(3)。否则,计算:()lGNSTmin()()()lxSyTlxlywxy19给出新的可行顶点标号。(),ˆ(),(),lllvvSllvvTlv其它(3)在NGl(S)-T中选择点y。若y是M饱和的,yz∈M,则置S=S∪{z},T=T∪{y}转(2)。否则,设P是Gl中M可扩路,置M=MΔE(P),转(1).注:该算法把匈牙利算法用于其中,主要是用来判定和求完美匹配。20例2,设如下矩阵是赋权完全偶图G的权值矩阵,求出其最优匹配。3554122022244100110012133W解:给出初始可行顶点标号l为:3554122022244100110012133W000005421321对应的相等子图Gl为:给出初始匹配M为:x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)22(1)u=x4为M非饱和顶点。置:x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)4,SxT(2)23(),lGNSyyT(3)取:2()lGyNSTy2为饱和顶点,y2x1∈M,于是:142,,SxxTy(2)23(),lGNSyyT(3)取:3()lGyNSTy3为饱和顶点,y3x3∈M,于是:13423,,,,SxxxTyy23x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)(2)23(),lGNSyyT于是修改标号:min()()()1lxSyTlxlywxy由得新标号为:(),ˆ(),(),lllvvSllvvTlv其它3554122022244100110012133W0110043203x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)24继续使用算法后得:x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)最优匹配权值为14.例3证明:K6n-2有一个3因子分解。证明:K6n-2=K2(3n-1),所以,可以分解为6n-3个边不重的1因子之和。而任意3个1因子可以并成一个3因子。所以,共可以并成2n-1个3因子。即K6n-2可以分解为2n-1个3因子的和。25例4证明:对n≥1,K4n+1有一个4因子分解。证明:K4n+1=K2(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的一个结论。群论是近世代数的重要组成部分。在数学、计算机科学、理论物理学(量子场论)中都有重要应用。是数学领域里最引人关注的方向和主流研究方向之一。创立者伽罗瓦。26(2)伽罗瓦(1811---1832)中学时受到数学老师里沙的影响而对数学产生极大兴趣。里沙对教学工作十分负责,且具有很高数学才能,但把精力耗在了学生身上,欣慰的是培养了好几位欧洲杰出数学家。中学时的伽罗瓦在里沙帮助下创立了群论。群论是19世纪最突出的数学成就。有点象相对论在物理学中的地位。在法国历史上著名的1830年的“七月革命”中,伽罗瓦两次入狱,成为坚强斗士。1832年5月,21岁的他因为反动派设下的爱情圈套,被迫决斗至死。这是他犯下的草率的错误。27证明:由陪集的性质: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,则这些元素为所求。(1≦i≦n)。28匹配在矩阵中的应用1、矩阵与偶图设A=(aij)是n阶方阵。构造偶图G=(X,Y)如下:X表示行集合,Y表示列集合。X中元素xi与Y中元素yj连线,当且仅当aij≠02010100400003701105600080Wy1y2y3y4y5x1x3x2x4x5x1x2x3x4x5y1y2y3y4y5Gw=(X,Y)292、下面研究detA和GA=(X,Y)之间关系122112(...)12(),det(1)jjjijjjjjjjAaAaaa则211201(1)jjjAaaaGSSS中无完美匹配SX,使得:N(S)有一个阶零矩阵。若|S|=n,则在A中存在n行,这n行中至多有n-1列元非零,而其余的ν-n+1列中每个元素为零。即得到A中有一个零