大学精品课程离散数学课件 图论04.平面图,对偶图及图的着色65.ppt

10/22/05 XHL,SCAU F06 第十七章 平面图 本章的主要内容 平面图的基本概念 欧拉公式 平面图的判断 平面图的对偶图 一、平面图的定义 若图 G 能被“画”在曲面 S 上使得除顶点处外边都不相交(边都不交叉), 则称 G 可嵌入曲面 S. 若 G 可嵌入平面, 则称 G 是可平面图或平面图. 画出的无边交叉的图解称为 G 的平面嵌入. 无平面嵌入的图称为非平面图. 几点说明及一些简单结论 一般所谈平面图不一定是指平面嵌入，上图中4个图都是平 面图，但讨论某些性质时，一定是指平面嵌入. 结论： 1. K5, K3,3都不是平面图（待证） 三、平面图(平面嵌入)的面与次数 定义17.2 (1) G的面——由G的平面嵌入的边将平面化分成的区域 (2) 无限面或外部面——（可用R0表示）——面积无限的面 (3) 有限面或内部面（可用R1, R2, …, Rk等表示）——面积 有限的面 (4) 面 Ri 的边界——包围Ri的回路组 (5) 面 Ri 的次数——Ri边界的长度，用deg(Ri)表示 极大平面图 定义17.3 若在简单平面图G中的任意两个不相邻的顶点之间 加一条新边所得图为非平面图，则称G为极大平面图. 注意：若简单平面图G中已无不相邻顶点，G显然是极大平 面图，如K1(平凡图), K2, K3, K4都是极大平面图. 定理17.8 设G为n阶m条边r个面的连通平面图，则n?m+r=2 （此公式称为欧拉公式） 证 对边数m做归纳法 m=0，G为平凡图，结论为真. 设m=k（k?1）结论为真，m=k+1时分情况讨论. (1) G中无圈，则G为树，删除一片树叶，用归纳假设. (2) 否则，在某一个圈上删除一条边，进行讨论. 推论 K5 与 K3, 3 都不是平面图. 平面图的边数满足: 温习 17.4 平面图的对偶图 设 G 是(某平面图的)一个平面嵌入, 构造 G 的对偶图 G*: 1、G 的每个面内有 G* 的一个顶点. 2、 G 的每条边 e 与 G* 的一条边 e* 交叉. 若 e 隔开 G 的面 R1, R2, 则 e* 关联于位于 R1, R2 内的 G* 的点 v1*, v2*. 平面图 G 的对偶图 G* 的性质: G* 是平面图, 而且是平面嵌入. G* 是连通图. 若 e 为 G 中的环, 则 G* 中与 e 交叉的边 e* 为桥; 反之亦然. 连通平面图的对偶是相互的: (G*)*? G. 定理. 设 G* 是连通平面图 G 的对偶图, n*, m*, r* 和 n, m, r 分别为 G* 和 G 的顶点数, 边数, 面数, 则 (1) n* = r; (2) m* = m; (3) r* = n; (4) 设 G* 的顶点 vi* 位于 G 的面 Ri 中, 则 dG*(vi*) = deg(Ri). 与自己的对偶图同构的图叫做自对偶图. 第十七章 习题课 主要内容 平面图的基本概念 欧拉公式 平面图的判断 平面图的对偶图 基本要求 深刻理解本部分的基本概念：平面图、平面嵌入、面、次数、极大平面图、极小非平面图、对偶图 牢记极大平面图的主要性质和判别方法 熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证明有关定理与命题 会用库拉图斯基定理证明某些图不是平面图 记住平面图与它的对偶图阶数、边数、面数之间的关系 练习1 解 设G的阶数、边数、面数分别为n, m, r. (1) 否则，由欧拉公式得 2m 5r = 5 (2+m?n) ① 由于?(G)?3及握手定理又有 2m ? 3n ② 由①与②得 m?30 ③ 又有 r=2+m?n 12 ④ 由④及②又可得 m30 ⑤ ③,⑤是矛盾的. (2) 正十二面体是一个反例 证明 证 用库拉图斯基定理证明 方法一. 下图为原图的子 图，它是K3,3，由库拉图斯 基定理得证命题. ?着色把图的顶点划分为若干个色组, 同个组中的顶点染色相同, 因而互不相邻. ??互不相邻的顶点的集合叫做点独立集 ??图的最少着色就是把图的顶点划分为若干组, 同组的顶点互不相邻, 且使组数最少.(分而治之) Welch-Powell（鲍威尔）着色算法: ①根据度递减的次序排列图G的顶点.