当前位置：首页 > 第八章 匹配
教学安排的说明
章节题目：二部图的性质，匹配，二部图的完美匹配，匹配的应用 学时分配：共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懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。
本文作者：...共分享92篇相关文档
