第八章 匹配

教学安排的说明

章节题目：二部图的性质，匹配，二部图的完美匹配，匹配的应用 学时分配：共4课时

本章教学目的与要求：理解匹配的实际意义，图的最大匹配和完美匹配的定义，掌

握二部图的最大匹配存在的充要条件和求法

其它：由于增加了部分例题和练习，增加了对二部图的讨论，因此授课内容与教

材不完美一致，主要教学内容有最大匹配，完美匹配，二部图完美匹配的算法

课 堂 教 学 方 案

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

教学目的与要求：掌握二部图的性质，匹配的实际意义，能够将简单的匹配问题建

立图论模型，掌握求最大匹配的匈牙利算法。

教学重点、难点：匈牙利算法，最大匹配的判别， 教学内容：

第八章 匹配

8.1 二部图

在许多实际问题中常用到二部图，本节介绍二部图的基本概念和主要结论。 定义8.1.1 若无向图G?V,E的顶点集V能分成两个子集V1和V2，满足

（1）V?V1V2，V1V2??；

（2）?e?(u,v)?E，均有u?V1，v?V2。

则称G为二部图或偶图(Bipartite Graph或Bigraph)，V1和V2称为互补顶点子集，常记为G?V1,V2,E。如果V1中每个顶点都与V2中所有顶点邻接，则称G为完美二部图或完美偶图(Complete Bipartite Graph)，并记为Kr,s，其中r?V1,s?V2。

图1中，(a),(b),(c),d(),e(都是二部图，其中)(b),(c),(d),(e)是完美二部图。 K1,3,K2,3,K2,,4K3,3

图1二部图示例

显然，在完美二部图中Kr,s中，顶点数n?r?s，边数m?rs。

一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图2中(a)可改画成图(b)，图(c)可改画成图(d)。可以看出，它们仍是二部图。

图2二部图示例

定理8.1.1 无向图G?V,E为二部图的充分必要条件为G中所有偶圈的长度均为偶数。

证明 先证必要性。

设G是具有互补顶点子集V1和V2的二部图。(v1,v2,,vk,v1)是G中任一长度为

k的偶圈，不妨设v1?V1，则v2m?1?V1，v2m?V2，所以k必为偶数，不然，不存在

边(vk,v1)。

再证充分性。

设G是连通图，否则对G的每个连通分支进行证明。设G?V,E只含有长度为偶数的偶圈，定义互补顶点子集V1和V2如下：任取一个顶点v0?V，令

V1?{v(v?V)?d(v0,v)为偶数}，V2?V?V1

现在证明V1中任意两顶点间无边存在。

假若存在一条边(vi,vj)?E，且vi,vj?V1，则由v0到vi间的最短路（长度为偶数）， 边(vi,vj)和vj到v0间的最短路（长度为偶数）所组成的偶圈的长度为奇数，与假设矛盾。

同理可证V2中任意两顶点间无边存在。

故G中的每条边必具有形式(vi,vj)，其中vi?V1，vj?V2， 即G是具有互补顶点子集V1和V2的一个二部图。

利用定理8.1可以很快地判断出图3中的(a)、(c)是二部图，而(b)则不是二部图。

图3

例1 六名间谍a,b,c,d,e,f被擒，已知a懂汉语、法语和日语，b懂德语、俄语和日语，c懂英语和法语，d懂西班牙语，e懂英语和德语，f懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。