第7章+图论-5(匹配)

1、1返回 结束第七章 图论引言引言7.1 图的基本概念图的基本概念7.2 路与连通路与连通7.3 图的矩阵表示图的矩阵表示7.5 图的匹配2返回 结束7.5 匹配 匹配问题是运筹学的重要问题之一，也是图论匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓的重要内容，它在所谓“人员分配问题人员分配问题”和和“最最优分配问题优分配问题”中有重要作用。中有重要作用。v 假定有一个男生有穷集合，其中每个男生认识一假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识些女生，在什么条件下每个男生都可以和他认识的女生结婚？的女生结婚？v 类似的工作分配问题：现有类似的

2、工作分配问题：现有n n个人，个人，m m份工作，每份工作，每个人有其擅长的工作。在什么条件下每个人都可个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？以得到一份他擅长的工作？如何分配？3返回 结束7.5 匹配例 男生认识的女生b1g1,g4,g5b2g1b3g2,g3,g4b4g2,g4b1b2g1b4g5b3g4g2g3配偶问题：二分图是否存在一个边集配偶问题：二分图是否存在一个边集E E使使得其中任意两边不邻接，且每个结点得其中任意两边不邻接，且每个结点b bi i与与E E的某个边关联。的某个边关联。4返回 结束7.5 匹配v例二分图二分图G(V1,V2)的

3、完全匹配的完全匹配: 是否存在单射是否存在单射 f: V1 V2使得任意使得任意v V1, v与与f(v)相邻。相邻。b1b2g1b4g5b3g4g2g3二分图存在完全匹配的必要条件是：二分图存在完全匹配的必要条件是：任意任意k个男生至少认识个男生至少认识k个女生。个女生。这个条件也是充分的。这个条件也是充分的。5返回 结束7.5 .1 匹配的基本概念匹配匹配设设G是无环图，是无环图，M E(G)，M ，如果，如果M中任意中任意两条边在两条边在G中均不相邻，中均不相邻， 则则M称为称为G的一个边独立集或匹的一个边独立集或匹配。配。最最大匹配大匹配若对图若对图G的任何匹配，均有的任何匹配，均有|

4、 |M|，则，则 称称M为图为图G的最大匹配。的最大匹配。匹配数匹配数 G中最大匹配中的边数称为匹配数，记作中最大匹配中的边数称为匹配数，记作 (G)。设设G的所有匹配为的所有匹配为M1、M2、 、Mk，记，记|max)(,.,1ikiMGMM6返回 结束7.5 .1 匹配的基本概念定义定义 设设M是是G的的一个匹配一个匹配 ，若有，若有e=(vi,vj) M，则称，则称vi和和vj在在M中中饱和饱和或或M 饱和。若饱和。若G中的每一个顶点中的每一个顶点都为都为M 饱和，则称饱和，则称M为为G的一个的一个完美匹配完美匹配。e1e2e3e4e5e6e7最大匹配：最大匹配： e1,e5 ,e6匹配

5、数：匹配数：3注释注释（1）完美匹配是最大匹配，反之未必。（2）匹配的概念与边的方向无关，故只需讨论无向图。（3）图G的边不交匹配的最小数目即为图G的边色数7返回 结束7.5 .1 匹配的基本概念v例例最大匹配完美匹配8返回 结束7.5 .1 匹配的基本概念边覆盖边覆盖 一个图一个图 G=(V, E) ，E E，若，若G的的任任一个顶点都与一个顶点都与E 中的边关联，则称中的边关联，则称E 覆盖覆盖G，或称或称E 为为G的一个边覆盖（集）。的一个边覆盖（集）。 极小边覆盖极小边覆盖 E 是是G的一个极小边覆盖的一个极小边覆盖 E 为为G的一个边覆盖的一个边覆盖 ( E1)(E1 E E1不不是

6、是G的边覆盖的边覆盖)若在E 集中去除任何元素E 不再是覆盖集9返回 结束7.5 .2 最大匹配的基本定理M 交错路交错路 设设G和和M如上所述，如上所述，G的一条的一条M 交错路交错路指指G中一条路，其中的边在中一条路，其中的边在M和和 E M 中交错出现中交错出现。 路是由属于M的匹配边和不属于M的非匹配边交替出现组成M 可增广路可增广路 设设G和和M如上所述，若如上所述，若G的一条的一条 M 交交错路的始点和终点都是错路的始点和终点都是 M 不饱和的，则称该不饱和的，则称该 M 交错路为一条交错路为一条 M 可增广路。可增广路。例 1v6v5v4v3v2v1 62 52 54,( )(

7、( )Mv v v vPv v vME PE PMMPM3是一个对集；但不是最大对集，有路 :v，通过得比更大的对集。 称为可扩路。匹配，匹配，匹配，增广路10返回 结束7.5 .2 最大匹配的基本定理引理引理设设P是匹配是匹配-可增广道路，则可增广道路，则PM是一个比M更大的匹配，且| PM|M|+1.定理定理7-2-1 (Berge) 设设G=(V,E)，M为为G中匹配，则中匹配，则 M为为G的最的最大匹配当且仅当大匹配当且仅当G中不存在中不存在 M 可增广道。可增广道。 证明证明 必要性：如有必要性：如有M-可增广道路，则有更大匹配。矛盾！可增广道路，则有更大匹配。矛盾！充分性充分性 ：

8、如果有最大匹配：如果有最大匹配M, |M|M|. 考虑考虑M M，其中每个，其中每个结点的最多与边和一个结点的最多与边和一个M边关联，每条道路是边关联，每条道路是M边和边和M边边交互道路。交互道路。在 可增广路中，第一条边与最后一条边都不是 中的边，因而 可增广路中属于 的边数比不在 中边数少一条。MMMMM11返回 结束7.5 .2 最大匹配的基本定理M实线边，M虚线边MM其中回路包含相同数目的其中回路包含相同数目的M边和边和M边。由边。由|M|M|, 必必存在存在M边开始，边开始， M边终止的边终止的M交互道路，即交互道路，即M-可增广可增广道路，矛盾！道路，矛盾！12返回 结束7.5 .

9、2 最大匹配的基本定理例例 从匹配从匹配M=(v6,v7)开始，求下图的最大匹开始，求下图的最大匹配配系统地检查不饱和点出发有无可增广道路，如，v1出发有可增广道路v1,v7v6,v8(可画以v1为根的交互树)，由此得到匹配(a), v2出发没有，v3出发存在v3v4，可得更大匹配(b), 其他点出发不存在可增广道路，故(b)是最大匹配。(a)(b)13返回 结束7.5 .2 最大匹配的基本定理设设S是图是图G的任一顶点子集，的任一顶点子集，G中与中与S的顶点邻接的顶点邻接的所有顶点的集合，称为的所有顶点的集合，称为S的邻集（的邻集（neighbour set），记作），记作NG(S)。定理定

10、理7-2-2 HallHall定理定理设设G是有二部划分是有二部划分(V1,V2)的二的二分图，则分图，则G含有饱和含有饱和V1的每个顶点的匹配的每个顶点的匹配M的充的充要条件是，对要条件是，对S V1，|N(S)|S|。 14返回 结束7.5 .2 最大匹配的基本定理v证明证明 必要性：对必要性：对S V1，匹配，匹配M将将S中的每个顶点与中的每个顶点与N(S)中顶点中顶点配对，故配对，故|N(S)|S|。v充分性：充分性：对对S V1，有，有|N(S)|S|。可以按下面方法作出饱和。可以按下面方法作出饱和V1的匹配的匹配M。先做任一初始匹配先做任一初始匹配M1，若已饱和，若已饱和V1，定理

11、得证。否则，定理得证。否则，V1中中至少有一个非饱和点至少有一个非饱和点x1，检查以，检查以x1为起点，终点在为起点，终点在V2中的交错中的交错路。考虑下列两种情形：路。考虑下列两种情形：（1）不存在任何一条交错路可以到达）不存在任何一条交错路可以到达V2的非饱和点。这时从的非饱和点。这时从x1开始的一切交错路的终点还是在开始的一切交错路的终点还是在V1。故存在。故存在A V1，使得，使得|N(A)|A|，这与已知矛盾。，这与已知矛盾。（2）存在一条以）存在一条以x1为起点，终点为为起点，终点为V2的非饱和点的交错路的非饱和点的交错路P，可见可见P是可增广路，于是作新匹配是可增广路，于是作新匹

12、配M2M1 P，显然，显然M2饱和饱和x1，且，且|M2|M1|。因此，重复以上过程，可以找到饱和因此，重复以上过程，可以找到饱和V1的全部顶点的匹配的全部顶点的匹配M。定理的充分性得证。定理的充分性得证。15返回 结束7.5 .2 最大匹配的基本定理定理定理7.5.3 Hall婚配定理婚配定理具有二部划分具有二部划分(V1,V2)的二分图的二分图G有有完美匹配完美匹配|V1|V2|，且对，且对S V1（或（或V2）均有）均有|N(S)|S|。v推论：推论：设设G是是k（k0）正则二分图，则）正则二分图，则G有完美匹配。有完美匹配。证明：证明： 设设G是二部划分是二部划分(V1,V2)的的k正

13、则二分图，则正则二分图，则k|V1|E(G)|k|V2|v由于由于k0，所以，所以|V1|V2|。任取。任取S V1，并用，并用E1和和E2分分别表示别表示G中与中与S和和N(S)中点关联的边集，则中点关联的边集，则E1 E2。v因而因而k|N(S)|E2|E1|k|S|v即即 |N(S)|S|，S V1由定理由定理7.5.3可知，可知，G有饱和有饱和V1的匹配的匹配M。由于。由于|V1|V2|，所，所以以M是完美匹配。是完美匹配。 16返回 结束7.5 .2 最大匹配的基本定理例：某工厂生产由六种不同颜色的纱织成的双色布，由这个工厂所生产的双色布中，每一种颜色至少和其它三种颜色搭配。证明：可

14、以挑选出三种不同的双色布，它们含有所有的六种颜色。v证明：分以下几步（1）建立图G(V,E)：一个点代表一种颜色，两个点相邻当且仅当这个工厂生产出一种由这两个点所对应的这两种颜色搭配而成的双色布；（2）由题意，所得图是6阶简单图，且每个点的度至少为3；（3）证明这个图有一个完美对集。17返回 结束.5.3 .5.3 最大匹配算法最大匹配算法v匈牙利算法（匈牙利算法（ 1965年，匈牙利著名数学家Edmonds设计了一种求最大匹配的算法，称为匈牙利(Hungarian)算法。 ）基本思想基本思想：从一个初始匹配：从一个初始匹配M开始，系统地寻找开始，系统地寻找M的可增广路的可增广路P，然后扩展为

15、更大的匹配然后扩展为更大的匹配M=PM，直至不存在可增广路。，直至不存在可增广路。方法：方法： 从一个不饱和结点开始从一个不饱和结点开始u，寻找一条，寻找一条M可增广路可增广路P： 构造一颗以构造一颗以u为根的交错树，即根出发的道路是为根的交错树，即根出发的道路是M交错路交错路 （i）如果叶结点均为饱和的，换另一个不饱和结点；）如果叶结点均为饱和的，换另一个不饱和结点； （ii) 如果某个叶是不饱和的如果某个叶是不饱和的 ，则有可增广路，则有可增广路P, 置置M=P M;重复上述过程，直至尝试过所有不饱和结点。重复上述过程，直至尝试过所有不饱和结点。18返回 结束.5.3 .5.3 最大匹配算

16、法最大匹配算法基本步骤：基本步骤：设有初始匹配设有初始匹配M，x0是是M不饱和点，还没有尝试扩展；如果不饱和点，还没有尝试扩展；如果不存在这样的结点，即不存在不存在这样的结点，即不存在M可增广路，转可增广路，转5；寻找从寻找从x0出发的出发的M可增广路可增广路P：S表示表示P在在X中的结点，中的结点，T表表示示P在在Y中的结点。中的结点。S=x0, T=, 如果如果N(S) T ，则，则x0不可扩展，即不存在从不可扩展，即不存在从x0出发的可增出发的可增广路，广路， 转转1；否则；否则, 转转4;当当N(S) T时时, 取取y N(S)- T ，若，若y不饱和，则不饱和，则P是可增广路，是可增

17、广路，则扩展则扩展M= P M,转转1; 若若y饱和，则有饱和，则有(x,y) M, 继续扩展继续扩展P: S = S x, T = T y, 转转3；M是最大匹配，结束。是最大匹配，结束。19返回 结束.5.3 .5.3 最大匹配算法最大匹配算法v匈牙利算法任给初始匹配找xS为非饱和点S =x, T =取y N(S)- T存在一条从x到y的M可增广路P，M：=MP无法继续匹配，停止存在边x,y MS：= S xT：= T yM饱和SN(S)= T?YNYNY已经饱和YN停止，M为最大匹配20返回 结束.5.3 .5.3 最大匹配算法最大匹配算法v例例x1x2y1x3x4x5y2y3y4y52

18、1返回 结束.5.3 .5.3 最大匹配算法最大匹配算法匈牙利算法例解（1）任给一个初始匹配；（2）若X已经饱和，结束；否则转（3）；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)22返回 结束.5.3 .5.3 最大匹配算法最大匹配算法匈牙利算法例解（3）在X中找一个非饱和点x0，S=x0，T= （4）若N(S)=T则停止，否则任选一点yN(S)-Tx1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)S=x2,T=N(S)=y2, y323返回 结束.5.3 .5.3 最大匹配算法最大匹配算法匈牙利算法例解

19、（5）若y已饱和， M中必有(x,y) ；作【 S =S x ， T =T y； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)S=Sx5=x2,x5；T=T y3 =y3S=x2,T=24返回 结束.5.3 .5.3 最大匹配算法最大匹配算法匈牙利算法例解（4）若N(S)=T则停止，否则任选一点yN(S)-T；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)S=x2,x5；T=y3N(S)=y2,y3,y4,y525返回 结束.5

20、.3 .5.3 最大匹配算法最大匹配算法匈牙利算法例解（5）若y已饱和， M中必有(x,y) ；作【 S =S x ， T =T y； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)S=x2,x5；T=y3；S=Sx3=x2,x5,x3；T=T y5 =y3,y526返回 结束.5.3 .5.3 最大匹配算法最大匹配算法匈牙利算法例解（4）若N(S)=T则停止，否则任选一点yN(S)-T；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y

21、3)N(S)=y2,y3,y4,y527返回 结束.5.3 .5.3 最大匹配算法最大匹配算法匈牙利算法例解（5）若y已饱和， M中必有(x,y) ；作【 S =S x ， T =T y； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)28返回 结束.5.3 .5.3 最大匹配算法最大匹配算法匈牙利算法例解（2）若

22、X已经饱和，结束；否则转（3）；（3）在X中找一个非饱和点x0，S=x0，T=（4）若N(S)=T则停止，否则任选一点yN(S)-Tx1x2y1x3x4x5y2y3y4y5S=x4；T =N(S)=y329返回 结束.5.3 .5.3 最大匹配算法最大匹配算法例1.如图G所示,V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5试求图G的最大匹配. 图(a) 图(b)X1 x2 x3 x4 x5y1 y2 y3 y4 y5x1 x2 x3 x4 x5y1 y2 y3 y4 y530返回 结束.5.3 .5.3 最大匹配算法最大匹配算法解:任取初始匹配M=x2y2,x3y3,x

23、5y5,如图(a)中虚线所示.解题过程如下表:MxSTN(S)yN(S)-Ty,u MPx2y2,x3y3,x5y5x1x1y2,y3y2饱和y2,x2x1,x2y2y1,y2,y3,y4,y5y1非饱和(x1y2y2y2)x1y2,x2y1,x3y3 x5y5x4x4y2,x3y2饱和y2,x1x4,x1y2y2,y3y3饱和y3,x3x4,x1,x3y2,y3y2,y3N(S)=T,停止31返回 结束.5.3 .5.3 最大匹配算法最大匹配算法因此,M=x1y2,x2y1,x3y3,x5y5即为图G的最大匹配,如图(b)虚线所示.X1 x2 x3 x4 x5y1 y2 y3 y4 y5x1

24、 x2 x3 x4 x5y1 y2 y3 y4 y5图(b)图(a)匈牙利算法的时间复杂度分析:设二分图G有n个结点,m条边,利用匈牙利算法求G的最大匹配时,初始匹配可为空,因此算法最多可找n条可增广路,每找一条可增广路,最多比较m条边,从而算法的时间复杂度为O(mn),故匈牙利算法为有效算法32返回 结束7.5.4 最优匹配v某公司准备安排n个员工x1,x2,xn从事n项工作y1,y2,yn。已知每个员工能胜任其中一项或几项工作，试问应该怎样安排，才能使尽可能多的人有工作可做，同时使尽量多的工作有人胜任？v构造具有二部划分(V1,V2)的简单二分图G，其中其中V1x1,x2,xn，V2y1,

25、y2,yn，并且边(xi,yj)E(G)职员xi能胜任工作yj，于是问题转化为求给定二分图G的最大匹配。 n,nKn,nKn,nKn,nK33返回 结束7.5.4 最优匹配v这种分配方案可能不止一种，或者说职员做各项工作，熟练程度、工作效率等未必一致，因此，要制定一个分工方案，使人尽其才，且公司的总效益最大。这样，就要考察具有二部划分(V1,V2)的加权完全二分图( , )，其中V1x1,x2,xn，V2y1,y2,yn，边(xi,yj)上的权 (xi,yj)表示职员xi做工作yj的效率。于是问题等价于在这个加权图( , )中求一个总权最大的完美匹配，称这种匹配为最优匹配最优匹配（optima

26、l matching）。 v当然，若枚举所有n！个完美匹配，然后比较它们的权，这种方法无疑是可以的。但是，当n很大时，这种方法显然是无效的。本节将介绍一个求最优匹配的有效算法。 n,nK n,nKn,nKn,nKn,nKn,nK34返回 结束7.5.4 最优匹配带权二分图 二分图的每条边二分图的每条边(i,j)均带有一个权均带有一个权w(i,j). 一个匹配的权是匹配各边权的和。一个匹配的权是匹配各边权的和。最优匹配问题最优匹配问题 给定带权二分图，求具有最大给定带权二分图，求具有最大权的匹配。权的匹配。35返回 结束7.5.4 最优匹配考虑带权完全二分图考虑带权完全二分图G（X,Y), X=

27、x1,.,xn,Y=y1,yn) ， V=X Y可行顶点标号可行顶点标号是定义在是定义在V上的一个实数函数上的一个实数函数l， 满足条满足条件：对于任意件：对于任意x X,y Y l(x)+l(y) w(x,y), l(v)称为顶点称为顶点v的标号的标号可行顶标总是存在的，例如可行顶标总是存在的，例如212( )max,( )0yVl xx yVl yyV这种可行顶标称为平凡标平凡标号号（trivil labelling）。36返回 结束7.5.4 最优匹配等式子图等式子图 关于标号关于标号l的等式子图的等式子图Gl=(V,El), El=(x,y):l(x)+l(y)=w(x,y)37返回

28、结束7.5.4 最优匹配定理定理1.设设l是是G的可行顶标的可行顶标.若若l顶子图顶子图Gl有完美匹配有完美匹配M,则则M是是G的最优匹配的最优匹配.al=minl(x)+l(y)-w(x,y)|x S,y V2-T 其它)()()()(ulTuaulSuaululll38返回 结束7.5.4 最优匹配基于定理基于定理1的在一个加权二分图的在一个加权二分图(Km,n, )中求最优匹配的有中求最优匹配的有效算法效算法Kuhn-munkres算法算法:(1)从任意可行顶标从任意可行顶标(如平凡标号如平凡标号)l开始开始,确定确定l等子图等子图Gl,并且在并且在Gl中选取匹配中选取匹配M.若若M饱和

29、饱和V1,则则M是完美匹配是完美匹配,也即也即M是最是最优匹配优匹配,算法终止算法终止,否则转入否则转入(2)步步.(2)匈牙利算法终止于匈牙利算法终止于S V1,T V2且使且使NGl(S)=T,计算计算a1,确定新的可行顶标确定新的可行顶标l,并以并以l替代替代l,以以Gl替代替代Gl转入转入(1)步步. 39返回 结束7.5.4 最优匹配例1 已知完全二分图K5，5，其中V1=x1,x2,x3,x4,x5，V2=y1,y2,y3,y4,y5，且K5，5的权矩阵为A，求K5，5的最优匹配。3312100110014422202214553A解：（1）取可行顶标l如下：l(y1) l(y2) l(y3) l(y4) l(y5) 0l(x1)max(3,5,5,4,1) 5l(x2)max