单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Email:,图论及其应用,任课教师：杨春,1,本次课主要内容,(,一,),、匈牙利算法,(,二,),、最优匹配算法,匈牙利算法与最优匹配算法,2,(,一,),、匈牙利算法,1,、偶图中寻找完美匹配,(1),、问题,设,G=(X,Y),|X|=|Y|,在,G,中求一完美匹配,M.,(2),、基本思想,从任一初始匹配,M,0,出发，通过寻求一条,M,0,可扩路,P,，令,M,1,=M,0,E(P),得比,M,0,更大的匹配,M,1,(,近似于迭代思想,),。,(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,交错路。,x,1,x,2,x,3,x,4,y,2,y,1,y,3,y,4,G=(X,Y),x,3,x,2,x,4,y,4,y,3,y,2,扎根,x,3,的,M,交错树,扎根于,M,非饱和点,u,的,M,交错树的生长讨论：,4,对于情形,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=S,z,T=T,y,转,(b),。否则，设,P,为,M,可扩路，置,M,1,=M,E(P),，转,(a).,例,1,讨论下图,G=(X,Y),是否有完美匹配。,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G=(X,Y),解：取初始匹配,M=,x,1,y,2,x,2,y,3,。,(a)S=,x,3,T=,;,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G=(X,Y),8,(a)S=,x,4,T=,;,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G=(X,Y),(b)N(S)=,y,2,y,3,N(S),T,取,y,2,N(S)-T,(c)y,2,为,M,饱和点，,y,2,x,3,M,。此时，置,S=S,x,3,T=T,y,2,。,(b)N(S)=,y,2,y,3,T,，,取,y,3,N(S)-T,x,4,y,2,x,3,10,(c)y,3,为,M,饱和点，,x,2,y,3,M,。此时，置,S=S,x,2,T=T,y,3,。,(b)N(S)=,y,2,y,3,T,，,取,y,3,N(S)-T,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G=(X,Y),(b)N(S)=,y,2,y,3,=T,，所以，,G,无完美匹配。,(5),、匈牙利算法复杂性分析,11,偶图中寻找最大匹配算法：,设,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).,13,定义,2,设,G=(X,Y),若对任意的,x,X,y,Y,有：,称,l,是赋权完全偶图,G,的可行顶点标号。,对于任意的赋权完全偶图,G,，均存在,G,的可行顶点标号。事实上，设：,则,l,是,G,的一个可行顶点标号。,15,定义,3,设,l,是赋权完全偶图,G=(X,Y,的可行顶点标号，令：,称,G,l,=G E,l,为,G,的对应于,l,的相等子图。,例如，设如下矩阵是赋权完全偶图,G,的权值矩阵并注明了一种可行顶点标号,l,0,0,0,0,0,5,4,2,1,3,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G,l,=(X,Y),16,根据上面定理，如果找到一种恰当可行顶点标号，使得对应的相等子图有完美匹配,M*,则求出了,G,的最优匹配。,Kuhn,采用顶点标号修改策略，找到了求最优匹配好算法，介绍如下：,给一初始顶点标号,l,在,G,l,中任选一个匹配,M,。,(1),若,X,是,M,饱和的，则,M,是最优匹配。否则，令,u,是一个,M,非饱和点，置：,S=,u,T=,。,(2),若 ，转,(3),。否则，计算：,18,给出新的可行顶点标号。,(3),在,N,G,l,(S)-T,中选择点,y,。若,y,是,M,饱和的，,yz,M,则置,S=S,z,T=T,y,转,(2),。否则，设,P,是,Gl,中,M,可扩路，置,M=M,E(P),转,(1).,注：该算法把匈牙利算法用于其中，主要是用来判定和求完美匹配。,19,例,2,，设如下矩阵是赋权完全偶图,G,的权值矩阵，求出其最优匹配。,解：给出初始可行顶点标号,l,为：,0,0,0,0,0,5,4,2,1,3,20,对应的相等子图,G,l,为：,给出初始匹配,M,为：,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G,l,=(X,Y),x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G,l,=(X,Y),21,(1)u=x,4,为,M,非饱和顶点。置：,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G,l,=(X,Y),(2),(3),取：,y,2,为饱和顶点，,y,2,x,1,M,于是：,(2),(3),取：,y,3,为饱和顶点，,y,3,x,3,M,于是：,22,继续使用算法后得：,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G,l,=(X,Y),最优匹配权值为,14.,例,3,证明：,K,6n-2,有一个,3,因子分解。,证明：,K,6n-2,=K,2(3n-1),所以，可以分解为,6n-3,个边不重的,1,因子之和。而任意,3,个,1,因子可以并成一个,3,因子。所以，共可以并成,2n-1,个,3,因子。即,K6n-2,可以分解为,2n-1,个,3,因子的和。,24,例,4,证明：对,n,1,K,4n+1,有一个,4,因子分解。,证明：,K,4n+1,=K,2(2n)+1,所以，可以分解为,2n,个边不重的,2,因子之和。而任意,2,个,2,因子可以并成一个,4,因子。所以，共可以并成,n,个,4,因子。即,K,4n+1,可以分解为,n,个,4,因子的和。,例,5,设,H,是有限群，,K,是,H,的子群。证明：存在元素,h,1,h,2,h,n,H,使得,h,1,K,h,2,K,h,n,K,都是,K,的左陪集。而,Kh,1,Kh,2,Kh,n,都是,K,的右陪集。,注,:(1),上面结论是群论学家,Hall,的一个结论。群论是近世代数的重要组成部分。在数学、计算机科学、理论物理学,(,量子场论,),中都有重要应用。是数学领域里最引人关注的方向和主流研究方向之一。创立者伽罗瓦。,25,(2),伽罗瓦,(1811-1832),中学时受到数学老师里沙的影响而对数学产生极大兴趣。里沙对教学工作十分负责，且具有很高数学才能，但把精力耗在了学生身上，欣慰的是培养了好几位欧洲杰出数学家。中学时的伽罗瓦,在里沙帮助下创立了群论。群论是,19,世纪最突出的数学成就。有点象相对论在物理学中的地位。,在法国历史上著名的,1830,年的“七月革命”中，伽罗瓦两次入狱，成为坚强斗士。,1832,年,5,月，,21,岁的他因为反动派设下的爱情圈套，被迫决斗至死。这是他犯下的草率的错误。,26,匹配在矩阵中的应用,1,、矩阵与偶图,设,A=(a,ij,),是,n,阶方阵。构造偶图,G=(X,Y),如下：,X,表示行集合，,Y,表示列集合。,X,中元素,x,i,与,Y,中元素,y,j,连线，当且仅当,a,ij,0,y,1,y,2,y,3,y,4,y,5,x,1,x,3,x,2,x,4,x,5,x,1,x,2,x,3,x,4,x,5,y,1,y,2,y,3,y,4,y,5,G,w,=(X,Y),28,2,、下面研究,detA,和,G,A,=(X,Y),之间关系,若,|S|=n,则在,A,中存在,n,行，这,n,行中至多有,n-1,列元非零，而其余的,-n+1,列中每个元素为零。即得到,A,中有一个 零子阵。,29,作业,P117-118,习题,4,：,13,31,Thank You!,32,