最优匹配

的一个匹配。是中均不邻接，则称边在中任意两条若设图定义GMGMEM,,EV,G2（或対集Matching)定义3若匹配M的某条边与点v关联,则称M饱和点v,并且称v是M的饱和点,否则称v是M的非饱和点.定义4设M是图G的一个匹配,如果G的每一个点都是M的饱和点,则称M是完美匹配；如果G中没有另外的匹配M0,使|M0|＞|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=(aij)|X|×|Y|,其中aij=F(xiyj).注意：此赋权矩阵与图的邻接矩阵不同！X:x1x2x3Y:y1y2634812123603480yyxAxx12312123120006000034000806380004000xxxyyxxAxyy邻接矩阵二部图赋权矩阵邻接矩阵12123603480yyxAxx二部图赋权矩阵Hall定理设G=(X,Y,E)为二部图,则①G存在饱和X的每个点的匹配的充要条件是对任意S,有|N(S)|≥|S|.其中,N(S)={v|u∈S,v与u相邻}.②G存在完美匹配的充要条件是对任意S或S有|N(S)|≥|S|.XXY二部图的匹配及其应用工作安排问题之一给n个工作人员x1,x2,…,xn安排n项工作y1,y2,…,yn.n个工作人员中每个人能胜任一项或几项工作,但并不是所有工作人员都能从事任何一项工作.比如x1能做y1,y2工作,x2能做y2,y3,y4工作等.这样便提出一个问题,对所有的工作人员能不能都分配一件他所能胜任的工作？二部图的匹配及其应用我们构造一个二部图G=(X,Y,E),这里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且当且仅当工作人员xi胜任工作yj时,xi与yj才相邻.于是,问题转化为求二部图的一个完美匹配.因为|X|=|Y|,所以完美匹配即为最大匹配.二部图的匹配及其应用问题：如何求出二部图的一个完美匹配？1965年匈牙利人Edmonds基于Hall定理提出一个算法，一般称为匈牙利（Hungarian）算法匈牙利算法思路（i）从G中任意取定一个初始匹配M。（ii）若X中的顶点皆是M饱和点，停止，M即完美匹配；否则取X中不是M饱和点的一顶点u，记}{uS，T。（iii）若TSN)(，停止，M即最大匹配，无完美匹配；否则取TSNy)(。（iv）若y是M饱和点，设Myz，}{zSS，}{yTT，转（iii）；否则，取可增广道路),(yuP，令))(())((MPEPEMM（对称差），转（ii）。求二部图G=(X,Y,E)的最大匹配算法(匈牙利算法）迭代步骤:从G的任意匹配M开始.①若X中的顶点皆是M饱和点，停止，M即完美匹配；否则将X中M的所有非饱和点都给以标号0和标记*,,转向②.②若X中所有有标号的点都已去掉了标记*,则M是G的最大匹配，无完美匹配.否则任取X中一个既有标号又有标记*的点xi,去掉xi的标记*,转向③.③找出在G中所有与xi邻接的点yj,若所有这样的yj都已有标号,则转向②,否则转向④.④对与xi邻接且尚未给标号的yj都给定标号i.若所有的yj都是M的饱和点,则转向⑤,否则逆向返回.即由其中M的任一个非饱和点yj的标号i找到xi,再由xi的标号k找到yk,…,最后由yt的标号s找到标号为0的xs时结束,获得M-增广路xsyt…xiyj,记E(P)={xsyt,…,xiyj},重新记M为M⊕E(P),将所有标记标号清空，转向①.M⊕E(P)=(M∪E(P))\(M∩E(P)),是对称差.⑤将yj在M中与之邻接的点xk,给以标号j和标记*,转向②.注释•上述匈牙利算法步骤中，标记*的作用在于标记X中的M非饱和点（可以能是临时的）•标记（0，1、2、。。）的作用是找M-增广路的过程的标记，从它也能确定是否通过此顶点找过增广路。•M-增广路总是以X中的M-非饱和点为起始，Y中的M-非饱和点结束的，所以找到了Y中的M-非饱和点才能找到M增广路1x2x3x4x5x1y2y3y4y5y例17：求下图最大匹配Hungarian算法：二部图的匹配及其应用注意到S={x1,x3,x4}时，N(S)={y1,y3,},NSS由Hall定理，G没有完美匹配。例18：求下图的最大匹配。匈亚利算法：解①取初始匹配M={x2y2,x3y3,x5y5}②给X中M的两个非饱和点x1,x4都给以标号0和标记*(如下图所示).00**二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：00③去掉x1的标记*,将与x1邻接的两个点y2,y3都给以标号1.因为y2,y3都是M的两个饱和点,所以将它们在M中邻接的两个点x2,x3都给以相应的标号和标记*.**11*23*二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：00*11*23*④去掉x2的标记*,将与x2邻接且尚未给标号的三个点y1,y4,y5都给以标号2.222二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：00*1123*222⑤因为y1是M的非饱和点,逆向返回,直到x1为0为止.于是得到M的增广路x1y2x2y1,记P={x1y2,y2x2,x2y1}.取M←M⊕P={x1y2,x2y1,x3y3,x5y5},则新M是比原M多一边的匹配.二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：0*⑥清空所有标记和标号。再给X中M的非饱和点x4给以标号0和标记*,然后去掉x4的标记*,将与x4邻接的两个点y2,y3都给以标号4.44二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：044因为y2,y3都是M1的两个饱和点,所以将它们在M1中邻接的两个点x1,x3都给以相应的标号和标记*.**23二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：044**23⑦去掉x1的标记*,因为与x1邻接的两个点y2,y3都有标号4,所以去掉x3的标记*.而与x3邻接的两个点y2,y3也都有标号4,此时X中所有有标号的点都已去掉了标记*(如上图所示),因此M是G的最大匹配.没有完美匹配。二部图的匹配及其应用例18：求下图的最大匹配。匈亚利算法：注意到S={x1,x3,x4}时，N(S)={y1,y3,},NSS所以没有完美匹配。二部图的匹配及其应用定义6设G=(X,Y,E,W)为完备的二部赋权图,若L：X∪Y→R+满足：对任意x∈X,y∈Y,L(x)+L(y)≥W(xy),则称L为G的一个可行点标记,记相应的生成子图为GL=(X,Y,EL,W),这里EL={xy∈E|L(x)+L(y)=W(xy)}.可行顶点标号总是存在的。例如;),(max)(XxxywxlYyYyyl,0)(。定理3设L是完备的二部赋权图G=(X,Y,E,F)的可行点标记,若M*是GL的完美匹配,则M*是G的权数最大的匹配。称为最佳（或最优）匹配.工作安排问题之二给n个工作人员x1,x2,…,xn安排n项工作y1,y2,…,yn.如果每个工作人员工作效率不同,要求工作分配的同时考虑总效率最高.二部图的匹配及其应用我们构造一个二部赋权图G=(X,Y,E,F),这里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xiyj)为工作人员xi胜任工作yj时的工作效率.则问题转化为：求二部赋权图G的最佳匹配.在求G的最佳匹配时,总可以假设G为完备二部赋权图.若xi与yj不相邻,可令F(xiyj)=0.同样地,还可虚设点x或y,使|X|=|Y|.如此就将G转化为完备二部赋权图,而且不会影响结果.二部图的匹配及其应用求完备二部赋权图G=(X,Y,E,F)的最佳匹配算法迭代步骤：设G=(X,Y,E,F)为完备的二部赋权图,L是其一个初始可行点标记,通常取L(x)=max{F(xy)|y∈Y},x∈X,L(y)=0,y∈Y.可行顶点标号法(Kuhn-Munkres算法)：二部图的最佳匹配算法：算法基本思想：通过顶点标记将赋权图转化为非赋权图，再用匈牙利算法求最大匹配M是GL的一个匹配.①若X的每个点都是饱和的,则M是最佳匹配.否则取M的非饱和点u∈X,令S={u},T=,转向②.②记NL(S)={v|u∈S,uv∈GL}.若NL(S)=T,则GL没有完美匹配,转向③.否则转向④.③调整标记,计算aL=min{L(x)+L(y)-F(xy)|x∈S,y∈Y\T}.由此得新的可行点标记.),(,,)(,,)()(ccLLTSvvLTvavLSvavLvH令L=H,GL=GH,重新给出GL的一个匹配M,转向①.④取y∈NL(S)\T,若y是M的饱和点,转向⑤.否则,转向⑥.⑤设xy∈M,则令S=S∪{x},T=T∪{y},转向②.⑥在GL中的u-y路是M-增广路,设为P,并令M=M⊕P,转向①.1x2x3x4x5x1y2y3y4y5y1用Hungarian算法求下图最大匹配作业（任选其一）利用k-m算法求赋权矩阵为4124153123543263A的完备二部赋权图G=(X,Y,E,F)的最佳匹配。作业2