5匹配

匈牙利算法与最优匹配算法(一)、匈牙利算法(二)、最优匹配算法基本概念1、匹配和完美匹配图G的一个匹配M是由其一组没有公共端点的非圈的边构成的集合.与匹配M中的边关联的顶点称为M-饱和的，其余顶点称为M-不饱和.图G的一个完美匹配M是饱和了G的所有顶点的匹配.2、极大匹配和最大匹配图G的一个极大匹配是不能通过添加边来使其变大的匹配.一个最大匹配图G的所有匹配中边数最大的匹配.基本概念3、M-可增广路径给定图G的一个匹配M，如果G的一条路径P中的边交替的出现在M和Mc中，则称P为一条M-交错路径.两端点均为M-不饱和顶点的M-交错路径称为M-可增广路径.4、二分图（偶图）图G=(V,E)的点集V可以分为两各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为二部图（偶图）.匈牙利算法(一)、匈牙利算法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可扩路。匈牙利算法定义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交错树的生长讨论：对于扎根于M非饱和点u的M交错树H，有两种情形：情形1除点u外，H中所有点为M饱和点，且在M上配对；x4ux2y4y3y2扎根u的M交错树Hx5匈牙利算法对于扎根于M非饱和点u的M交错树H，有两种情形：情形2H包含除u外的M非饱和点。x4ux2y4y3y2扎根u的M交错树H匈牙利算法Hall定理X,Y-二部图有一个饱和X的匹配当且仅当对任意有|N(S)|≥|S|证明：SX匈牙利算法对于情形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；()TNS()TNSxyM若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.(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)匈牙利算法(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)匈牙利算法(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)-Tx4y2x3匈牙利算法(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无完美匹配。匈牙利算法1)、最多循环|X|次可以找到完美匹配；2)、初始匹配最多扩张|X|次可以找到完美匹配；3)、每次生长树的生长至多2|X|-1次。所以，算法复杂性为O(|X|3),是好算法。(5)、匈牙利算法复杂性分析匈牙利算法2、偶图中寻找最大匹配问题：在一般偶图上求最大匹配M.分析：使用匈牙利算法求完美匹配时，当在扎根于M非饱和点u的交错树上有|N(S)||S|时，由Hall定理，算法停止。要求出最大匹配，应该继续检查X-S是否为空，如果不为空，则检查是否在其上有M非饱和点。一直到所有M非饱和点均没有M可扩路才停止。匈牙利算法偶图中寻找最大匹配算法：设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).最优匹配算法(二)、最优匹配算法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、可行顶点标号与相等子图最优匹配算法定义2设G=(X,Y),若对任意的x∈X,y∈Y,有：称l是赋权完全偶图G的可行顶点标号。对于任意的赋权完全偶图G，均存在G的可行顶点标号。事实上，设：则l是G的一个可行顶点标号。()()()lxlywxy()max(),,()0,.yYlxwxyxXlyyY若若最优匹配算法定义3设l是赋权完全偶图G=(X,Y的可行顶点标号，令：称Gl=G[El]为G的对应于l的相等子图。例如，设如下矩阵是赋权完全偶图G的权值矩阵并注明了一种可行顶点标号l0000054213x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)()()()()lExyEGlxlywxy3554122022244100110012133W最优匹配算法定理设l是赋权完全偶图G=(X,Y的可行顶点标号，若相等子图Gl有完美匹配M*,则M*是G的最优匹配。证明：设M*是Gl的完美匹配，则：又设M是G的任一完美匹配，则：所以，w(M*)≥w(M)。即M*是G的最优匹配。*()(*)()()eMvVGwMwelv()()()()eMvVGwMwelv最优匹配算法根据上面定理，如果找到一种恰当可行顶点标号，使得对应的相等子图有完美匹配M*,则求出了G的最优匹配。Kuhn采用顶点标号修改策略，找到了求最优匹配好算法，介绍如下：给一初始顶点标号l,在Gl中任选一个匹配M。(1)若X是M饱和的，则M是最优匹配。否则，令u是一个M非饱和点，置：S={u},T=Φ。(2)若，转(3)。否则，计算：()lGNSTmin()()()lxSyTlxlywxy最优匹配算法给出新的可行顶点标号。(3)在NGl(S)-T中选择点y。若y是M饱和的，yz∈M,则置S=S∪｛z｝,T=T∪｛y｝转(2)。否则，设P是Gl中M可扩路，置M=MΔE(P),转(1).注：该算法把匈牙利算法用于其中，主要是用来判定和求完美匹配。(),ˆ(),(),lllvvSllvvTlv其它最优匹配算法例2，设如下矩阵是赋权完全偶图G的权值矩阵，求出其最优匹配。解：给出初始可行顶点标号l为：00000542133554122022244100110012133W3554122022244100110012133W最优匹配算法对应的相等子图Gl为：给出初始匹配M为：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)最优匹配算法(1)u=x4为M非饱和顶点。置：x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)(2)(3)取y2为饱和顶点，y2x1∈M,于是：(2)(3)取y3为饱和顶点，y3x3∈M,于是：4,SxT23(),lGNSyyT2()lGyNST142,,SxxTy23(),lGNSyyT3()lGyNST13423,,,,SxxxTyy最优匹配算法x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)(2)于是修改标号：由得新标号为：0110043203x1x2x3x4x5y1y2y3y4y5Gl=(X,Y)23(),lGNSyyTmin()()()1lxSyTlxlywxy(),ˆ(),(),lllvvSllvvTlv其它3554122022244100110012133W最优匹配算法继续使用算法后得：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因子的和。最优匹配算法例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的一个结论。群论是近世代数的重要组成部分。在数学、计算机科学、理论物理学(量子场论)中都有重要应用。是数学领域里最引人关注的方向和主流研究方向之一。创立者伽罗瓦。最优匹配算法(2)伽罗瓦(1811---1832)中学时受到数学老师里沙的影响而对数学产生极大兴趣。里沙对教学工作十分负责，且具有很高数学才能，但把精力耗在了学生身上，欣慰的是培养了好几位欧洲杰出数学家。中学时的伽罗瓦在里沙帮助下创立了群论。群论是19世纪最突出的数学成就。有点象相对论在物理学中的地位。在法国历史上著名的1830年的“七月革命”中，伽罗瓦两次入狱，成为坚强斗士。1832年5月，21岁的他因为反动派设下的爱情圈套，被迫决斗至死。这是他犯下的草率的错误。最优匹配算法证明：由陪集的性质：H中的任意两个左(右)陪集,要么相等，要么没有共同元素。所以H可按某子群的左(右)陪集，划分为左(右)陪集族。如果K是H的子群，则aK或者Kb的元素个数等于K中元素个数。设|K|=k。且假设子群K在群H中的指数为n。我们构造偶图G=(X,Y)如下：X表示H关于K的左陪集族，Y表示H关于K的右陪集族