《图论最优匹配》PPT课件

（或対集 Matching),定义3,若匹配,M,的某条边与点,v,关联,则称,M,饱和,点,v,并且称,v,是,M,的,饱和点,否则称,v,是,M,的,非饱,和点,.,定义4,设,M,是图,G,的一个匹配,如果,G,的每一个点,都是,M,的饱和点,则称,M,是,完美匹配,；如果,G,中,没有另外的匹配,M,0,使,|,M,0,|,|,M,|,则称,M,是,最,大匹配,.,每个完美匹配都是最大匹配,反之不一定成立,.,例16：判断下图的匹配,最大匹配,非完美匹配,完美匹配,定义5,设,M,是图,G,的的一个匹配,其边在,E,M,和,M,中交错出现的路,称为,G,的一条,M,交错路,.,起点,和终点都不是,M,的饱和点的,M,交错路,称为,M,增广路,.,Berge定理：,G,的一个匹配,M,是最大匹配的,充要条件,是,G,不包含,M,增广路,.,定义,设,V,=,X,Y,且,X,Y,=,E,xy,|,x,X,y,Y,称,G,=(,X,Y,E,),为,二部图或偶图,.,二部图可认为是有限简单无向图,.,如果,X,中的每个点都与,Y,中的每个点邻接,则称,G,=(,X,Y,E,),为,完全二部图,.,若,F,：,E,R,+,则称,G,=(,X,Y,E,F,),为,二部赋权图,.,二部赋权图的权矩阵一般记作,A,=(,a,ij,),|,X,|,Y,|,其中,a,ij,=,F,(,x,i,y,j,),.,注意：此赋权矩阵与图的邻接矩阵不同！,X:x1 x2 x3,Y:y1 y2,6 3 4 8,邻接矩阵,二部图赋权矩阵,邻接矩阵,二部图赋权矩阵,Hall定理,设,G,=(,X,Y,E,)为二部图,则,G,存在,饱和,X,的每个点的匹配的充要条件是,对任意,S ,有|,N,(,S,)|,S,|.,其中,N,(,S,)=,v,|,u,S,v,与,u,相邻.,G,存在完美匹配的充要条件是,对任意,S,或,S,有,|,N,(,S,)|,|,S,|.,二部图的匹配及其应用,工作安排问题之一,给,n,个工作人员,x,1,x,2,x,n,安排,n,项工作,y,1,y,2,y,n,.,n,个工作人员中每个人能胜任一项或几项工作,但并,不是所有工作人员都能从事任何一项工作,.,比如,x,1,能做,y,1,y,2,工作,x,2,能做,y,2,y,3,y,4,工作等,.,这样便提出一个问题,对所有的工作人员能不能都分配一件他所能胜任的工作？,二部图的匹配及其应用,我们构造一个二部图,G,=(,X,Y,E,),这里,X,=,x,1,x,2,x,n,Y,=,y,1,y,2,y,n,并且当且仅当工作人员,x,i,胜任工作,y,j,时,x,i,与,y,j,才相邻,.,于是,问题转化为求二部图的一个完美匹配,.,因为,|,X,|=|,Y,|,所以完美匹配即为最大匹配,.,二部图的匹配及其应用,问题：如何求出二部图的一个完美匹配？,1965年匈牙利人Edmonds基于Hall定理提出一个算法，一般称为匈牙利（Hungarian）算法,匈牙利算法思路,求二部图,G,=(,X,Y,E,),的最大匹配算法(匈牙利算法）迭代步骤,:,从,G,的任意匹配,M,开始.,若,X,中的顶点皆是,M,饱和点，停止，,M,即完美匹配；否则将,X,中,M,的所有,非饱和点,都给以标号0和标记*,转向.,若,X,中所有有标号的点都已去掉了标记*,则,M,是,G,的最大匹配，无完美匹配.否则任取,X,中一个既有标号又有标记*的点,x,i,去掉,x,i,的标记*,转向.,找出,在G中所有,与,x,i,邻接的点,y,j,若所有这样的,y,j,都已有标号,则转向,否则转向.,对与,x,i,邻接且尚未给标号的,y,j,都给定标号,i,.,若所有的,y,j,都是,M,的,饱和点,则转向,否则逆向返回.即由其中,M,的任一个非饱和点,y,j,的标号,i,找到,x,i,再由,x,i,的标号,k,找到,y,k,最后由,y,t,的标号,s,找到标号为0的,x,s,时结束,获得,M,-增广路,x,s,y,t,x,i,y,j,记,E,(,P),=,x,s,y,t,x,i,y,j,重新记,M,为,M,E,(,P,),将所有标记标号清空,，转向.,M,E,(,P,)=(,M,E,(,P,),(,M,E(,P,),是对称差.,将,y,j,在,M中与之邻接,的点,x,k,给以标号,j,和标记,*,转向,.,注释,上述匈牙利算法步骤中，标记*的作用在于标记X中的M非饱和点（可以能是临时的）,标记（0，1、2、。）的作用是找M-增广路的过程的标记，从它也能确定是否通过此顶点找过增广路。,M-增广路总是以X中的M-非饱和点为起始，Y中的M-非饱和点结束的，所以找到了Y中的M-非饱和点才能找到M增广路,例17：求下图最大匹配,H,ungarian,算法：,二部图的匹配及其应用,注意到,S=,x,1,x,3,x,4,时，N(S)=,y,1,y,3,由Hall定理，G没有完美匹配。,例18：求下图的最大匹配。,匈亚利算法：,解 取初始匹配,M,=,x,2,y,2,x,3,y,3,x,5,y,5,给,X,中,M,的两个非饱和点,x,1,x,4,都给以标号0和标记*(如下图所示).,0,0,*,*,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,0,去掉,x,1,的标记,*,将与,x,1,邻接的两个点,y,2,y,3,都给以标号1.,因为,y,2,y,3,都是,M,的两个饱和点,所以将它们在,M,中邻接的两个点,x,2,x,3,都给以相应的标号和标记,*.,*,*,1,1,*,2,3,*,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,0,*,1,1,*,2,3,*,去掉,x,2,的标记,*,将与,x,2,邻接且尚未给标号的三个点,y,1,y,4,y,5,都给以标号,2.,2,2,2,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,0,*,1,1,2,3,*,2,2,2,因为,y,1,是,M,的非饱和点,逆向返回,直到,x,1,为,0,为止.于是得到,M,的增广路,x,1,y,2,x,2,y,1,记,P,=,x,1,y,2,y,2,x,2,x,2,y,1,.,取,M,M,P,=,x,1,y,2,x,2,y,1,x,3,y,3,x,5,y,5,则新,M,是比原,M,多一边的匹配,.,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,*,清空所有标记和标号。,再给,X,中,M,的非饱和点,x,4,给以标号,0,和标记,*,然后去掉,x,4,的标记,*,将与,x,4,邻接的两个点,y,2,y,3,都给以标号,4.,4,4,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,4,4,因为,y,2,y,3,都是,M,1,的两个饱和点,所以将它们在,M,1,中邻接的两个点,x,1,x,3,都给以相应的标号和标记,*.,*,*,2,3,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,4,4,*,*,2,3,去掉,x,1,的标记,*,因为与,x,1,邻接的两个点,y,2,y,3,都有标号,4,所以去掉,x,3,的标记,*.,而与,x,3,邻接的两个点,y,2,y,3,也都有标号,4,此时,X,中所有有标号的点都已去掉了标记,*(,如上图所示,),因此,M,是,G,的最大匹配,.没有完美匹配。,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,注意到,S=,x,1,x,3,x,4,时，N(S)=,y,1,y,3,所以没有完美匹配。,二部图的匹配及其应用,定义6,设,G,=(,X,Y,E,W,)为完备的二部赋权,图,若,L,：,X,Y,R,+,满足：,对任意,x,X,y,Y,L,(,x,)+,L,(,y,),W,(,x y,),则称,L,为,G,的一个,可行点标记,记相应的生成,子图为,G,L,=(,X,Y,E,L,W,),这里,E,L,=,x y,E,|,L,(,x,)+,L,(,y,)=,W,(,x y,).,定理3,设,L,是完备的二部赋权图,G,=(,X,Y,E,F,),的可行点标记,若,M,*,是,G,L,的完美匹配,则,M,*,是,G,的,权数最大的匹配。称为,最佳（或最优）匹配,.,工作安排问题之二,给,n,个工作人员,x,1,x,2,x,n,安排,n,项工作,y,1,y,2,y,n,.如果每个工作人员工作效率不同,要求工作分配的同时考虑,总效率最高,.,二部图的匹配及其应用,我们构造一个二部赋权图,G,=(,X,Y,E,F,),这里,X,=,x,1,x,2,x,n,Y,=,y,1,y,2,y,n,F,(,x,i,y,j,),为工作人员,x,i,胜任工作,y,j,时的工作效率,.,则问题转化为：求二部赋权图,G,的最佳匹配,.,在求,G,的最佳匹配时,总可以假设,G,为完备二部赋权图.,若,x,i,与,y,j,不相邻,可令,F,(,x,i,y,j,)=0.,同样地,还可虚设点,x,或,y,使,|,X,|=|,Y,|,.如此就将,G,转化为完备二部赋权图,而且不会影响结果,.,二部图的匹配及其应用,求完备二部赋权图,G,=(,X,Y,E,F,),的最佳匹配算法迭代步骤：,设,G,=,(,X,Y,E,F,),为完备的二部赋权图,L,是其一个初始可行点标记,通常取,L,(,x,)=max,F,(,x y,)|,y,Y,x,X,L,(,y,)=0,y,Y,.,可行顶点标号法(Kuhn-Munkres算法)：,二部图的最佳匹配算法：,算法基本思想：通过顶点标记将赋权图转化为非赋权图，再用匈牙利算法求最大匹配,M,是,G,L,的一个匹配.,若,X,的每个点都是饱和的,则,M,是最佳匹配.否则取,M,的非饱和点,u,X,令,S,=,u,T,=,转向.,记,N,L,(,S,)=,v,|,u,S,uv,G,L,.若,N,L,(,S,)=,T,则,G,L,没有完美匹配,转向.否则转向.,调整标记,计算,a,L,=min,L,(,x,)+,L,(,y,),-,F,(,xy,)|,x,S,y,Y,T,.,由此得新的可行点标记,令,L,=,H,G,L,=,G,H,重新给出,G,L,的一个匹配,M,转向.,取,y,N,L,(,S,),T,若,y,是,M,的饱和点,转向,.,否则,转向,.,设,x y,M,则令,S,=,S,x,T,=,T,y,转向,.,在,G,L,中的,u,-,y,路是,M,-,增广路,设为,P,并令,M,=,M,P,转向,.,1,用H,ungarian,算法求下图最大匹配,作业（任选其一）,利用k-m算法求赋权矩阵为,的完备二部赋权图,G,=(,X,Y,E,F,)的最佳匹配。,作业2,