《运筹学匹配与覆盖问题名校讲义》由会员分享，可在线阅读，更多相关《运筹学匹配与覆盖问题名校讲义（18页珍藏版）》请在金锄头文库上搜索。
1、第三十讲第三十讲 匹配与覆盖问题匹配与覆盖问题 1 问题的现实来源 2 定义 3 最大匹配定理4 二分图的匹配与覆盖 5 介绍二分图的两种最大匹配算法 1 问题的现实来源 （1）匹配和覆盖问题是图论的一个重要分支，在介绍它的基本定义和有关算法之前，先举例说明其应用背景。例5-18第二次世界大战时，英国空军曾招募了许多沦陷国的飞行员。空军飞机上需配备两名在航空技能与语言技能上都相协调的飞行员（当然，一般一个飞行员可与其多个飞行员搭配）。问如何将众多飞行员进行搭配，才能使发出的飞机数目最多？1 问题的现实来源 （2）例5-19某国家有50个州和65个民族，该国需成立参谋委员会，委员会要求每州至少一
2、人和每个民族也至少一人，同时希望人员尽量少。现已从全国推选出170人准备参加该委员会，问如何挑选，才能满足上面要求？这两个问题就是典型的匹配和覆盖问题。2 定义 （1）1匹配设M是图G的连E(G)的一个子集，当图的每一个顶点最多只与该集合中一条边相关联时，则称集合M为一个匹配。2覆盖设M是图G的边集E(G)的一个子集，当图的每一个顶点至少与该集合中一条边相关联时，则称集合M为一个覆盖。值得指出的是，在后面叙述二分图时，将引出覆盖的另一种定义。3最大基数匹配图G中包含边数最多的匹配（有时简称最大匹配），例5-18即是该类匹配问题。2 定义 （2）4最大权匹配图G中含有边权和最大的匹配（有时简称最
3、优匹配）。5最小基数覆盖图G中包含边数最少的覆盖。例5-19即是该类覆盖问题。6最小权覆盖图G中包含边权和最少的覆盖。3 最大匹配定理（1）1有关术语若M是G中一个匹配，则M中的一条边的两个端点称作M下配对。若匹配M的某条边与顶点v关联，则称M饱和顶点v，且称v是M饱和的，否则称v是不饱和的。完全匹配如果G中每个顶点都被M饱和，则称M匹配为完全匹配。显然，完全匹配必是最大匹配。图5-48(a)和(b)分别给出一个最大匹配和完全匹配（图中粗线表示匹配M）。3 最大匹配定理（2）图 5-48 (a) v2 v7 v6 v5 v4 v3 v1 (b) 3 最大匹配定理（3）G的M交错通路 路上的边是
4、由G中匹配M的边与其它边（EM）交错出现的通路。例如，图5-49所示的v2 v4 v5 v7 v9 v10就是一条M交错通路。M增广通路起点和终点都是未被M饱和的交错通路。例如，图5-49中的v1 v2 v4 v7 v5 v8，就是一条M增广通路。2定理8：图G的一个匹配M成为最大匹配的充要条件是G不包含M增广通路。 图 5-49 v10 v9v8v7v6v5v4v3v2v14 二分图的匹配与覆盖 （1）1有关定义完全图每对顶点都有边相联的简单图称为完全图。二分图若图的顶点集合可分成两个子集V1和V2，通常记作G(V1，V2；E)。若二分图中V1的每个顶点与V2的每个顶点都相联，则称为完全二分
5、图。正则图若图G中所有顶点的度均相等，则称图G为正则的或正则图。顶点度为k的正则图称为k度正则图。每个顶点都是k度的二分图称k正则二分图。4 二分图的匹配与覆盖 （2）邻集对于图G中任一顶点集合V0，则称与V0相邻（有边相联）的所有顶点集合为V0的邻集，可记作NG(V0)或简写为N(V0)。在二分图中，人们往往关心图中能否找到饱和V1（或V2）中所有顶点的匹配。2定理9 设G是二分划(V1，V2)的二分图，则G含有饱和V1每个顶点的匹配的充要条件是，对所有的V0V1都存在：N(V0) V0 3推论：若G是一个K正则二分图（K0），则G必有一个完全匹配。 4 二分图的匹配与覆盖 （3）4覆盖的另
6、一定义图G中的一个覆盖可定义为V(G)中的一个子集K，使得G中每条边都至少有一个端点落在K中。后面不加特殊说明，将采用这种覆盖定义。实质上，对于图G中的最大匹配M*和最小覆盖 ，亦存在下面关系：5定理10 设M和K分别是图G的一个匹配和覆盖，且满足|M|=|K|。则M和K必分别是图G的最大匹配和最小覆盖。6定理11 二分图G中的最大匹配边数必等于最小覆盖顶点数。 5 介绍二分图的两种最大匹配算法 （1）如果说在第二章的整数规划中所说的指派问题是合理安排人员去完成工作以便寻求费用最低的优化分配的话，现在所说的分派问题就是合理安排工作人员，以便使更多人就业。1匈牙利算法算法思路及步骤在V1中选择一
7、个不被M饱和的一个顶点ui，并且力图寻找一条以ui为起点的M增广通路。 5 介绍二分图的两种最大匹配算法 （2）如果找到这样通路P，则求环和则新得 就是一个比M更大的匹配，它比M能饱和更多的V1中的点。然后把 视作M，重复上述步骤。举例例5-20已给出二分图G（V1，V2）示示图5-52中，其中V1= x1，x2，x3，x4，x5，V2= y1，y2，y3，y4，y5。试求解该问题的最大匹配5 介绍二分图的两种最大匹配算法 （3）解1)首先给出任意初始匹配M= x2y2，x3y3，x5y5，用图5-52中的粗线表示。图 5-52 y5 x5 x4 x3x2x1 y4 y3 y2 y1 5 介绍
8、二分图的两种最大匹配算法 （4） y2 x1 x2 y2 x1 y3 x2 y2 x1 y1 y3 x2 y2 x1 x3 图 5-53 y3 x2 y2 x1 x3 2)显然，x1，x4是未被M饱和的点，任取x1作为起点，寻求一条关于M的增广通路。该树的生长过程示于图5-53中。5 介绍二分图的两种最大匹配算法 （5）3)从图5-53中的最后完整树看出，通路x1y2x2y1是未饱和路，故令 M+x1y2+x2y1x2y2= x1y2，x2y1，x3y3，x5y5，具体示于图5-54中的粗线中。并视 为M。图 5-54 y5 x5 x4 x3x2x1 y4 y3 y2 y1 5 介绍二分图的两
9、种最大匹配算法 （6）4)观察图5-54，知x4为唯一不饱和点。以x4为根的关于M的交错通路树的生长过程示于图5-55中。从图中看出，已无饱和通路，故达到最大匹配，但达不到完全匹配。 y2 x4 x1 y2 x4 y3 x1 y2 x4 图 5-55 y3 x2 y2 x4 x3 5 介绍二分图的两种最大匹配算法 （7）2最大流算法算法思路及步骤i)设已知二分图G(V1，V2)中的V1= x1，x2，xn ，V2= y1，y2，ym ，标明图中边的方向全部为V1集合指向V2集合。ii)增设一个源点s和指向V1各点的有向边。iii)增设一个汇点t和指向V2各点指向t点的有向边。iv)令每条边的容量c全为1。按上述方法便把原问题转换成一个单源单汇的运输网络G。显然，G的最大流量值肯定是原二分图G的最大匹配值。
