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

1返回结束第七章图论引言7.1图的基本概念7.2路与连通7.3图的矩阵表示7.4最短路径问题7.5图的匹配8.1Euler图和Hamilton图8.2树8.3生成树8.4平面图2返回结束7.5匹配匹配问题是运筹学的重要问题之一，也是图论的重要内容，它在所谓“人员分配问题”和“最优分配问题”中有重要作用。假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生结婚？类似的工作分配问题：现有n个人，m份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？3返回结束7.5匹配[例]男生认识的女生b1g1,g4,g5b2g1b3g2,g3,g4b4g2,g4b1b2g1b4g5b3g4g2g3配偶问题：二分图是否存在一个边集E使得其中任意两边不邻接，且每个结点bi与E的某个边关联。4返回结束7.5匹配例二分图G(V1,V2)的完全匹配:是否存在单射f:V1V2使得任意vV1,v与f(v)相邻。b1b2g1b4g5b3g4g2g3二分图存在完全匹配的必要条件是：任意k个男生至少认识k个女生。这个条件也是充分的。5返回结束7.5.1匹配的基本概念[匹配]设G是无环图，ME(G)，M≠，如果M中任意两条边在G中均不相邻，则M称为G的一个边独立集或匹配。[最大匹配]若对图G的任何匹配，均有||＜|M|，则称M为图G的最大匹配。[匹配数]G中最大匹配中的边数称为匹配数，记作(G)。设G的所有匹配为M1、M2、…、Mk，记||max)(,...,1'ikiMGMM6返回结束7.5.1匹配的基本概念[定义]设M是G的一个匹配，若有e=(vi,vj)M，则称vi和vj在M中饱和或M饱和。若G中的每一个顶点都为M饱和，则称M为G的一个完美匹配。e1e2e3e4e5e6e7最大匹配：{e1,e5,e6}匹配数：3注释（1）完美匹配是最大匹配，反之未必。（2）匹配的概念与边的方向无关，故只需讨论无向图。（3）图G的边不交匹配的最小数目即为图G的边色数7返回结束7.5.1匹配的基本概念例最大匹配完美匹配8返回结束7.5.1匹配的基本概念[边覆盖]一个图G=(V,E)，E´E，若G的任一个顶点都与E´中的边关联，则称E´覆盖G，或称E´为G的一个边覆盖（集）。[极小边覆盖]E´是G的一个极小边覆盖E´为G的一个边覆盖(E1)(E1E´E1不是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可增广路。例1v6v5v4v3v2v1625254{,}(())(())MvvvvPvvvMEPEPMMPM3是一个对集；但不是最大对集，有路:v，通过得比更大的对集。称为可扩路。匹配，匹配，匹配，增广路10返回结束7.5.2最大匹配的基本定理[引理]设P是匹配Ｍ-可增广道路，则PM是一个比M更大的匹配，且|PM｜＝|M|+1.[定理7-2-1](Berge)设G=(V,E)，M为G中匹配，则M为G的最大匹配当且仅当G中不存在M可增广道。[证明]必要性：如有M-可增广道路，则有更大匹配。矛盾！充分性：如果有最大匹配M’,|M’||M|.考虑MM’，其中每个结点的最多与Ｍ边和一个M’边关联，每条道路是M边和M’边交互道路。在可增广路中，第一条边与最后一条边都不是中的边，因而可增广路中属于的边数比不在中边数少一条。MMMMM11返回结束7.5.2最大匹配的基本定理M实线边，M’虚线边MM’其中回路包含相同数目的M边和M’边。由|M’||M|,必存在M’边开始，M‘边终止的M交互道路，即M-可增广道路，矛盾！12返回结束7.5.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的邻集（neighbourset），记作NG(S)。[定理7-2-2Hall定理]设G是有二部划分(V1,V2)的二分图，则G含有饱和V1的每个顶点的匹配M的充要条件是，对SV1，|N(S)|≥|S|。14返回结束7.5.2最大匹配的基本定理[证明]必要性：对SV1，匹配M将S中的每个顶点与N(S)中顶点配对，故|N(S)|≥|S|。充分性：对SV1，有|N(S)|≥|S|。可以按下面方法作出饱和V1的匹配M。先做任一初始匹配M1，若已饱和V1，定理得证。否则，V1中至少有一个非饱和点x1，检查以x1为起点，终点在V2中的交错路。考虑下列两种情形：（1）不存在任何一条交错路可以到达V2的非饱和点。这时从x1开始的一切交错路的终点还是在V1。故存在AV1，使得|N(A)|＜|A|，这与已知矛盾。（2）存在一条以x1为起点，终点为V2的非饱和点的交错路P，可见P是可增广路，于是作新匹配M2＝M1P，显然M2饱和x1，且|M2|＞|M1|。因此，重复以上过程，可以找到饱和V1的全部顶点的匹配M。定理的充分性得证。15返回结束7.5.2最大匹配的基本定理[定理7.5.3Hall婚配定理]具有二部划分(V1,V2)的二分图G有完美匹配|V1|＝|V2|，且对SV1（或V2）均有|N(S)|≥|S|。推论：设G是k（k＞0）正则二分图，则G有完美匹配。证明：设G是二部划分(V1,V2)的k正则二分图，则k|V1|＝|E(G)|＝k|V2|由于k≠0，所以|V1|＝|V2|。任取SV1，并用E1和E2分别表示G中与S和N(S)中点关联的边集，则E1E2。因而k|N(S)|＝|E2|≥|E1|＝k|S|即|N(S)|≥|S|，SV1由定理7.5.3可知，G有饱和V1的匹配M。由于|V1|＝|V2|，所以M是完美匹配。16返回结束7.5.2最大匹配的基本定理例：某工厂生产由六种不同颜色的纱织成的双色布，由这个工厂所生产的双色布中，每一种颜色至少和其它三种颜色搭配。证明：可以挑选出三种不同的双色布，它们含有所有的六种颜色。证明：分以下几步（1）建立图G(V,E)：一个点代表一种颜色，两个点相邻当且仅当这个工厂生产出一种由这两个点所对应的这两种颜色搭配而成的双色布；（2）由题意，所得图是6阶简单图，且每个点的度至少为3；（3）证明这个图有一个完美对集。17返回结束７.5.3最大匹配算法匈牙利算法（1965年，匈牙利著名数学家Edmonds设计了一种求最大匹配的算法，称为匈牙利(Hungarian)算法。）基本思想：从一个初始匹配M开始，系统地寻找M的可增广路P，然后扩展为更大的匹配M’=PM，直至不存在可增广路。方法：从一个不饱和结点开始u，寻找一条M可增广路P：构造一颗以u为根的交错树，即根出发的道路是M交错路（i）如果叶结点均为饱和的，换另一个不饱和结点；（ii)如果某个叶是不饱和的，则有可增广路P,置M=PM;重复上述过程，直至尝试过所有不饱和结点。18返回结束７.5.3最大匹配算法基本步骤：1.设有初始匹配M，x0是M不饱和点，还没有尝试扩展；如果不存在这样的结点，即不存在M可增广路，转5；2.寻找从x0出发的M可增广路P：S表示P在X中的结点，T表示P在Y中的结点。S={x0},T={},3.如果N(S)＝T，则x0不可扩展，即不存在从x0出发的可增广路，转1；否则,转4;4.当N(S)T时,取yN(S)-T，若y不饱和，则P是可增广路，则扩展M=PM,转1;若y饱和，则有(x,y)M,继续扩展P:S=S{x},T=T{y},转3；5.M是最大匹配，结束。19返回结束７.5.3最大匹配算法匈牙利算法任给初始匹配找xS为非饱和点S={x},T=取yN(S)-T存在一条从x到y的M可增广路P，M：=MP无法继续匹配，停止存在边{x,y}MS：=S{x}T：=T{y}M饱和SN(S)=T?YNYNY已经饱和YN停止，M为最大匹配20返回结束７.5.3最大匹配算法[例]x1x2y1x3x4x5y2y3y4y521返回结束７.5.3最大匹配算法解匈牙利算法例解（1）任给一个初始匹配；（2）若X已经饱和，结束；否则转（3）；x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}22返回结束７.5.3最大匹配算法解匈牙利算法例解（3）在X中找一个非饱和点x0，S={x0}，T={}（4）若N(S)=T则停止，否则任选一点y∈N(S)-Tx1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}S={x2},T={}N(S)={y2,y3}23返回结束７.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=S∪{x5}={x2,x5}；T=T∪{y3}={y3}S={x2},T={}24返回结束７.5.3最大匹配算法解匈牙利算法例解（4）若N(S)=T则停止，否则任选一点y∈N(S)-T；x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}S={x2,x5}；T={y3}N(S)={y2,y3,y4,y5}25返回结束７.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=S∪{x3}={x2,x5,x3}；T=T∪{y5}={y3,y5}26返回结束７.5.3最大匹配算法解匈牙利算法例解（4）若N(S)=T则停止，否则任选一点y∈N(S)-T；x1x2y1x3x4x5y2y3y4y5M={(x1,y1),(x3,y5),(x5,y3)}N(S)={y2,y3,y4,y5}27返回结束７.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=ME(P)={(x1,y1),(x2,y3),(x3,y2),(x5,y5)}28返回结束７.5.3最大匹配算法解匈牙利算法例解（2）若X已经饱和，结束；否则转（3）；（3）在X中找一个非饱和点x0，S={x0}，T={}（4）若N(S)=T则停止，否则任选一点y∈N(S)-Tx1x2y1x3x4x5y2y3y4y5S={x4}；T={}N(S)={y3}29返回结束７.5.3最大匹配算法例1.如图G所示,V1={x1,x2,x3,x4,x5},V2={y1,y2,y3,y4,y5}试求图G的最大匹配.图(a)图(b)X1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y