第八章 匹配

课 堂 教 学 方 案

课程名称：二部图的完美匹配，匹配的应用 授课时数：2学时 授课类型：理论课 教学方法与手段：讲授法

教学目的与要求：掌握二部图的完美匹配的概念。能够区分完美匹配和最大匹配，

掌握Hall定理

教学重点、难点：重点为二部图的完美匹配的求法，难点为Hall定理的证明 教学内容：

8.3二部图的完美匹配

这里我们主要讨论二部图的匹配问题。二部图的主要应用是匹配，它在所谓“人员分配问题”和“最优分配问题”等运筹学中的问题上有重要的应用。

对于二部图有：

定义8.3.1 设二部图G?V1,V2,E，M是G的一个匹配。若?v?V1，v均是M饱和的，则称M是V1对V2的完美匹配（简称V1―完美匹配）；若?v?V2，v均是M饱和的，则称M是V2对V1的完美匹配（简称V2—完美匹配）。若M既是V1―完美匹配，又是V2―完美匹配（即图G的每个顶点都是饱和的），则称M是完美匹配(Complete Matching)。

显然，完美匹配是最大匹配，但反之不然。

例6 下图中各图的粗线表示匹配中的边（简称匹配边）。（b）中匹配是最大的，

X-完美的，（c）中匹配是完美的（从而也是最大的）。

（a） （b） （c）

图12 例7（1）在图11中，边集M?{(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)}是一个匹配，而且是一个最大和完美匹配。

（2）在图13(a)中，边集M1?{(1,5),(2,7),(3,9),(4,8)}和M2?{(1,6),(2,7),(3,9)，

(4,8)}都是图G的最大匹配，也是V1―完美匹配，但不是完美匹配。在图13(b)中，

边集M?{(1,4),(2,5),(3,6)}是完美匹配。

图13

在许多实际应用中，许多问题最终都将归为寻求二部图的匹配问题，或者更具体的

那就是归结为求G中的一个饱和X中的每个顶点的匹配。存在这类匹配的一个充分必要条件是由Hall在1935年所给出的，通常称为霍尔婚姻定理。

定理8.3.2（霍尔定理） 二部图G?V1,V2,E有V1―完美匹配，当且仅当对V1中任一子集A，和所有与A邻接的点构成的点集N(A)，恒有

N(A)?A

证明 先证必要性。假设M是二部图G?V1,V2,E的一个V1―完美匹配，则V1中的每个顶点均是M饱和的。对V1的任一子集A，因A的每个顶点在M下和N(A)中不同的顶点配对，所以有N(A)?A。

再证充分性。假设G是满足对任何V1的子集A，N(A)?A的二部图，但G中没有使V1中每个顶点饱和的完美匹配，设M1是G的一个最大匹配，由假设，M1不使V1中所有顶点饱和。设v是V1中的M1不饱和点，并设B是与v有关于M1交错路相连通的所有顶点的集合。由于M1是一最大匹配，由定理8.2.2可知：v为B中唯一的M1不饱和点。

令A=BV1，T?BV2，显然，A?{v}中的顶点都关于M1饱和，即它与T中

的顶点在M1下配对，于是T?A?1，且N(A)?T，又因N(A)中的每个顶点有关于M1交错路与v相连通，因此N(A)?T，所以

N(A)?A?1?A 与假设N(A)?A矛盾。

例8设有4个人x1,x2,x3,x4，现有5项工作y1,y2,y3,y4,y5需要做，每个人所能胜任工作的情况如图14所示，问能否使每个人都能分配到一项工作？

图14

解 这个问题即为：二部图G?V1,V2,E是否存在V1―完美匹配。当取

A={x1,x3,x4}时，N(A)={y2,y5}，因此N(A)?A，根据霍尔定理，二部图没有V1―

完美匹配，所以要使每个人都能分配到一项工作是不可能的。 例9 k-正则二部图（k > 0）有完美匹配。 证 设G = 为k-正则二部图，那么 k·? X ? = ? E ? = k·? Y ? 从而? X ? = ? Y ?。

设S为X的任一子集，E1为S中顶点所邻接的边的集合，E2为N(S)中顶点所邻接的边的集合。据N(S)的定义，E1?E2，于是 k·?N(S)?= ? E2 ?≥ ? E1 ? = k·? S ? ?N(S)?≥? S ? 因此G有X-完美匹配M。

由于 ? X ? = ? Y ?，显然M也是Y-完美匹配，故G有完美匹配。 三、匹配的应用 1. 匹配与一一对应 问题：FJOI-信封问题

John先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。

将Small John所提供的n封信依次编号为1，2，…，n；且n个信封也依次编号为1，2，…，n。假定Small John能提供一组信息：第i封信肯定不是装在信封