《离散数学》特殊图一1.ppt

第8章 一些特殊的图 8.1 二部图 8.2 欧拉图 8.3 哈密顿图 8.4 平面图 8.1 二部图 二部图 完全二部图 匹配 极大匹配 最大匹配 匹配数 完备匹配 二部图 定义 设无向图 G=V,E, 若能将V 分成V1 和 V2 (V1?V2=V, V1?V2=?), 使得G中的每条边的两个端点都一个属于V1, 另一个属于V2, 则称G为二部图（二分图）,记为V1,V2,E, 称V1和V2为互补顶点子集. 若V1中每个顶点均与V2中每个顶点有且只有一条边相关联, 则称二部图G为完全二部图, 记为Kr,s r=|V1|, s=|V2|. 注意: n 阶零图（|E|＝0）为二部图. 二部图的判别法 定理 无向图G=V,E是二部图当且仅当G中无奇数长度的回路（无奇圈）. 例：述各图都是二部图 匹配 设G=V,E为无向图, E*?E 匹配(边独立集): 任2条均不相邻的边组成的边子集 任2条边的端点都不一样 极大匹配: 添加任一条边后都不再是匹配的匹配 最大匹配: 边数最多的极大匹配 匹配数: 最大匹配中的边数, 记为?1 最大匹配的边数不超过|V|的一半 例 3个图的匹配数 依次为3, 3, 4. 匹配 (续) 设M为G中一个匹配，v?V(G) v为M饱和点: M中有边与v关联 v为M非饱和点: M中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点 所有点都在匹配边上 完美匹配是最大匹配 例 关于M1, a,b,e,d是饱和点 f,c是非饱和点 M1不是完美匹配 M2是完美匹配 二部图中的匹配 定义 设G=V1,V2,E为二部图, M是G中最大匹配, 若|M|＝min{|V1|，|V2|}，则称M为G中的一个完备匹配 V1或V2的任意节点都是M中边的端点 M是完备匹配， |V1| ? |V2| 则称M为V1到V2的一个完备匹配. 当|V1|=|V2|时, 完备匹配变成完美匹配. 两部分一对一 最大匹配一定存在，完备匹配不一定存在 二部图中的匹配 Hall定理 定理(Hall定理) 设二部图G=V1,V2,E中，|V1|?|V2|. G中存 在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与V2 中的k个顶点相邻(k=1,2,…,|V1|). 由Hall定理不难证明, 上一页图(2)没有完备匹配. 定理 设二部图G=V1,V2,E中, V1中每个顶点至少关联 t 条边(t?1), 而V2中每个顶点至多关联t条边，则G中存在V1到V2的完备匹配. Hall定理中的条件称为“相异性条件”, 第二个定理中的条件 称为 t 条件. 满足 t 条件的二部图一定满足相异性条件. 一个应用实例 例 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、香港去开会. 已知a只想去上海，b只想去广州，c, d, e都表示想去广州或香港. 问该课题组在满足个人要求的条件下，共有几种派遣方案？ 解 令G=V1,V2,E, 其中V1={s, g, x}, V2={a, b, c, d, e}, E={(u,v) | u?V1, v?V2, v想去u}, 其中s, g, x分别表示上海、广州和香港. G如图所示. G 满足相异性条件，因而可给 出派遣方案，共有9种派遣方案 (请给出这9种方案). 上图是二部图，满足t条件（t＝2），存在V1到V2的完备匹配 8.2 欧拉图－－一笔画问题 欧拉通路 欧拉回路 欧拉图 半欧拉图 哥尼斯堡七桥问题 欧拉图是能一笔画出的边不重复的回路. 欧拉图 欧拉通路: 经过图中每条边一次且仅一次，并且行遍图中每 个顶点的通路. 欧拉回路:经过图中每条边一次且仅一次，并且行遍图中每个顶点的回路 欧拉图: 有欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性. 一笔画问题 笔不离开纸，每边只能画一次，不允许重复，将图画出，称该图能一笔画。 如终点回到起点，则等价于该图存在欧拉回路 如终点不是起点，则等价于该图仅存在欧拉通路 如该图不能一笔画，则等价于该图不存在欧拉通路和欧拉回路。 图a不是一笔画，它不是欧拉图，也不存在欧拉通路； 图b能完成起点和终点不同的一笔画，存在欧拉通路ACFEBCDGFH，但不存在欧拉回路，不是欧拉图； 图c能完成起点与终点相同的的一笔画，存在欧拉回路，它是欧拉图。 欧拉图(续) 例 图中, (1), (4)为欧拉图; (2), (5)为欧拉通路; (3)，(