第三十讲 匹配与覆盖问题匹配与覆盖问题 §1 问题的现实来源 §2 定义 §3 最大匹配定理 §4 二分图的匹配与覆盖 §5 介绍二分图的两种最大匹配算法 §1 §1 问题的现实来源问题的现实来源 （（1 1））匹配和覆盖问题是图论的一个重要分支，在介绍它的基 本定义和有关算法之前，先举例说明其应用背景[例5-18]第二次世界大战时，英国空军曾招募了许多沦 陷国的飞行员空军飞机上需配备两名在航空技能与语 言技能上都相协调的飞行员（当然，一般一个飞行员可 与其多个飞行员搭配）问如何将众多飞行员进行搭配 ，才能使发出的飞机数目最多？§1 §1 问题的现实来源问题的现实来源 （（2 2））[例5-19]某国家有50个州和65个民族，该国需成立参谋 委员会，委员会要求每州至少一人和每个民族也至少一 人，同时希望人员尽量少现已从全国推选出170人准 备参加该委员会，问如何挑选，才能满足上面要求？这两个问题就是典型的匹配和覆盖问题§2 §2 定义定义 （（1 1））1．匹配设M是图G的连E(G)的一个子集，当图的每一 个顶点最多只与该集合中一条边相关联时，则称集合M 为一个匹配。
2．覆盖设M是图G的边集E(G)的一个子集，当图的每 一个顶点至少与该集合中一条边相关联时，则称集合M 为一个覆盖值得指出的是，在后面叙述二分图时，将 引出覆盖的另一种定义3．最大基数匹配图G中包含边数最多的匹配（有时简 称最大匹配），例5-18即是该类匹配问题§2 §2 定义定义 （（2 2））4．最大权匹配图G中含有边权和最大的匹配（有时简 称最优匹配）5．最小基数覆盖图G中包含边数最少的覆盖例5-19 即是该类覆盖问题6．最小权覆盖图G中包含边权和最少的覆盖§3 §3 最大匹配定理最大匹配定理（（1 1））1．有关术语若M是G中一个匹配，则M中的一条边的两个端点称作M 下配对①若匹配M的某条边与顶点v关联，则称M饱和顶点v， 且称v是M饱和的，否则称v是不饱和的②完全匹配如果G中每个顶点都被M饱和，则称M匹配 为完全匹配显然，完全匹配必是最大匹配图5-48(a) 和(b)分别给出一个最大匹配和完全匹配（图中粗线表示 匹配M）§3 §3 最大匹配定理最大匹配定理（（2 2））图 5-48 (a) v2 v7 v6 v5 v4 v3 v1 (b) §3 §3 最大匹配定理最大匹配定理（（3 3））③G的M交错通路 路上的边是由G中匹 配M的边与其它边（E－M）交错出现 的通路。
例如，图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 v9 v8v7v6v5v4v3v2 v1§4 §4 二分图的匹配与覆盖二分图的匹配与覆盖 （（1 1））1．有关定义①完全图每对顶点都有边相联的简单图称为完全图②二分图若图的顶点集合可分成两个子集V1和V2，通 常记作G＝(V1，V2；E)若二分图中V1的每个顶点与V2的每个顶点都相联，则称 为完全二分图③正则图若图G中所有顶点的度均相等，则称图G为 正则的或正则图顶点度为k的正则图称为k度正则图每个顶点都是k度的二分图称k正则二分图§4 §4 二分图的匹配与覆盖二分图的匹配与覆盖 （（2 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正则二分图（K＞0），则G必有 一个完全匹配 §4 §4 二分图的匹配与覆盖二分图的匹配与覆盖 （（3 3））4．覆盖的另一定义图G中的一个覆盖可定义为V(G)中的一 个子集K，使得G中每条边都至少有一个端点落在K中后面 不加特殊说明，将采用这种覆盖定义实质上，对于图G中的最大匹配M*和最小覆盖 ，亦存在下 面关系：5．定理10 设M和K分别是图G的一个匹配和覆盖，且满足 |M|=|K|则M和K必分别是图G的最大匹配和最小覆盖6．定理11 二分图G中的最大匹配边数必等于最小覆盖顶点 数 §5 §5 介绍二分图的两种最大匹配介绍二分图的两种最大匹配 算法算法 （（1 1））如果说在第二章的整数规划中所说的指派问题是合理安 排人员去完成工作以便寻求费用最低的优化分配的话， 现在所说的分派问题就是合理安排工作人员，以便使更 多人就业1．匈牙利算法①算法思路及步骤在V1中选择一个不被M饱和的一个顶点ui，并且力图寻 找一条以ui为起点的M增广通路。
§5 §5 介绍二分图的两种最大匹配介绍二分图的两种最大匹配 算法算法 （（2 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 §5 介绍二分图的两种最大匹配介绍二分图的两种最大匹配 算法算法 （（3 3））[解]1)首先给出任意初始匹配M={ x2y2，x3y3，x5y5}，用图5-52中 的粗线表示图 5-52 y5 x5 x4 x3x2x1 y4 y3 y2 y1 §5 §5 介绍二分图的两种最大匹配介绍二分图的两种最大匹配 算法算法 （（4 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 介绍二分图的两种最大匹配介绍二分图的两种最大匹配 算法算法 （（5 5））3)从图5-53中的最后完整树看出，通路{x1y2x2y1}是未饱和路 ，故令 ＝M+{x1y2}+{x2y1}－{x2y2}={ x1y2，x2y1，x3y3，x5y5}，具体示于图5-54中的粗线中并视 为M图 5-54 y5 x5 x4 x3x2x1 y4 y3 y2 y1 §5 §5 介绍二分图的两种最大匹配介绍二分图的两种最大匹配 算法算法 （（6 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 §5 介绍二分图的两种最大匹配介绍二分图的两种最大匹配 算法算法 （（7 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的最大匹配值。