离散数学 65平面图.ppt

课件 1 6.4.4 平面图 – 平面图与平面嵌入 – 平面图的面及其次数 – 极大平面图 – 极小非平面图 – 欧拉公式 – 库拉图斯基定理 – 平面图的对偶图 课件 2 平面图与非平面图 定义 6.22 如果能将图 G 除顶点外边不相交地画在平面上 , 则称 G 是 平面图 . 这个画出的无边相交的图称作 G 的 平面 嵌入 . 没有平面嵌入的图称作 非平面图 . 例如 下图中 (1)~(4) 是平面图 , (2) 是 (1) 的平面嵌入， (4) 是 (3) 的平面嵌入 . (5) 是非平面图 . 课件 3 平面图的面与次数 设 G 是一个平面嵌入 G 的面 : 由 G 的边将平面划分成的每一个区域 无限面 ( 外部面 ) : 面积无限的面 , 用 R 0 表示 有限面 ( 内部面 ) : 面积有限的面 , 用 R 1 , R 2 , … , R k 表示 面 R i 的边界 : 包围 R i 的所有边构成的回路组 面 R i 的次数 : R i 边界的长度，用 deg( R i ) 表示 说明 : 构成一个面的边界的回路组可能是初级回路 , 简单回 路 , 也可能是复杂回路 , 甚至还可能是非连通的回路之并 . 课件 4 实例 例 1 右图有 个面 4 deg( R 1 )= deg( R 2 )= deg( R 3 )= deg( R 0 )= 1 3 2 8 R 1 的边界 : R 2 的边界 : R 3 的边界 : R 0 的边界 : a bce fg abcdde, fg 课件 5 实例 例 2 右边 2 个图是同一 平面图的平面嵌入 . R 1 在 (1) 中是外部面 , 在 (2) 中是内部面 ; R 2 在 (1) 中是内部面 , 在 (2) 中是外部面 . (1) R 1 R 2 R 3 (2) R 1 R 2 R 3 说明 : (1) 一个平面图可以有多个不同形式的平面嵌入 , 它们都同构 . (2) 可以通过变换 ( 测地投影法 ) 把平面图的任何一面作为 外部面 课件 6 平面图的面与次数 ( 续 ) 定理 6.13 平面图各面的次数之和等于边数的 2 倍 证 一条边或者是 2 个面的公共边界 , 或者在一个面的边界 中出现 2 次 . 在计算各面的次数之和时 , 每条边恰好被计算 2 次 . 课件 7 极大平面图 定义 6.24 若 G 是简单平面图 , 且在任意两个不相邻的顶点 之间加一条新边所得图为非平面图 , 则称 G 为 极大平面图 例如 K 1 , K 2 , K 3 , K 4 都是极大平面图 (1) 是 K 5 删去一条边 , 是极大平面图 . (2) 、 (3) 不是 . (2) (3) (1) 课件 8 极大平面图的性质 ? 极大平面图是连通的 ? 设 G 为 n ( n ? 3) 阶简单图 , G 为极大平面图的充分必要条 件是 , G 每个面的次数均为 3. 例如 极大平面图 外部面的次数为 4 非极大平面图 课件 9 极小非平面图 定义 6.25 若 G 是非平面图 , 并且任意删除一条边所得图都 是平面图 , 则称 G 为 极小非平面图 例如 K 5 , K 3,3 都是极小非平面图 下述 4 个图也都是极小非平面图 课件 10 欧拉公式 定理 6.14 设 G 为 n 阶 m 条边 r 个面的连通平面图 , 则 n ? m + r =2 证 对边数 m 做归纳证明 . m =0, G 为平凡图 , 结论成立 . 设 m = k ( k ? 0) 时结论成立 , 对 m = k +1, 若 G 中无圈 , 则 G 必有一个度数为 1 的顶点 v , 删除 v 及关联的 边 , 记作 G ? . G ? 连通 , 有 n -1 个顶点 , k 条边和 r 个面 . 由归纳假 设 , ( n -1)- k + r =2, 即 n -( k +1)+ r =2, 得证 m = k +1