《离散数学平面》PPT课件.ppt

1 8.4 平 面 图 平 面 图 与 平 面 嵌 入 平 面 图 的 面 、 有 限 面 、 无 限 面 面 的 次 数 极 大 平 面 图 极 小 非 平 面 图 欧 拉 公 式 平 面 图 的 对 偶 图 2 平 面 图 和 平 面 嵌 入 定 义 如 果 能 将 图 G除 顶 点 外 边 不 相 交 地 画 在 平 面 上 , 则 称 G是 平 面 图 . 这 个 画 出 的 无 边 相 交 的 图 称 作 G的 平 面 嵌 入 . 没 有 平 面 嵌 入 的 图 称 作 非 平 面 图 . 例 如 下 图 中 (1)(4)是 平 面 图 , (2)是 (1)的 平 面 嵌 入 ，(4)是 (3)的 平 面 嵌 入 . (5)是 非 平 面 图 . 3 平 面 图 和 平 面 嵌 入 (续 ) 今 后 称 一 个 图 是 平 面 图 , 可 以 是 指 定 义 中 的 平 面 图 , 又 可 以是 指 平 面 嵌 入 , 视 当 时 的 情 况 而 定 . 当 讨 论 的 问 题 与 图 的 画法 有 关 时 , 是 指 平 面 嵌 入 . K5和 K3,3是 非 平 面 图 设 G G, 若 G为 平 面 图 , 则 G 也 是 平 面 图 ; 若 G 为 非 平 面 图 , 则 G也 是 非 平 面 图 . K n(n5), K3,n(n3)都 是 非 平 面 图 . 平 行 边 与 环 不 影 响 图 的 平 面 性 . K5K3,3 4 平 面 图 的 面 与 次 数设 G是 一 个 平 面 嵌 入G的 面 : 由 G的 边 将 平 面 划 分 成 的 每 一 个 区 域无 限 面 (外 部 面 ): 面 积 无 限 的 面 , 用 R0表 示有 限 面 (内 部 面 ): 面 积 有 限 的 面 , 用 R1, R2, Rk表 示 面 Ri的 边 界 : 包 围 Ri的 所 有 边 构 成 的 回 路 组面 Ri的 次 数 : Ri边 界 的 长 度 ， 用 deg(Ri)表 示 说 明 : 构 成 一 个 面 的 边 界 的 回 路 组 可 能 是 初 级 回 路 , 简 单 回路 , 也 可 能 是 复 杂 回 路 , 还 可 能 是 非 连 通 的 回 路 之 并 . 定 理 平 面 图 各 面 的 次 数 之 和 等 于 边 数 的 2倍 . 5 平 面 图 的 面 与 次 数 (续 )例 1 右 图 有 4个 面 , deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 请 写 各 面 的 边 界 . 例 2 左 边 2个 图 是 同 一 个 平 面图 的 平 面 嵌 入 . R1在 (1)中 是外 部 面 , 在 (2)中 是 内 部 面 ; R 2在 (1)中 是 内 部 面 , 在 (2)中 是外 部 面 . 其 实 , 在 平 面 嵌 入 中可 把 任 何 面 作 为 外 部 面 . 6 极 大 平 面 图 定 义 若 G是 简 单 平 面 图 , 并 且 在 任 意 两 个 不 相 邻 的 顶 点 之间 加 一 条 新 边 所 得 图 为 非 平 面 图 , 则 称 G为 极 大 平 面 图 .性 质 若 简 单 平 面 图 中 已 无 不 相 邻 顶 点 ， 则 是 极 大 平 面 图 . 如 K1, K2, K3, K4都 是 极 大 平 面 图 . 极 大 平 面 图 必 连 通 . 阶 数 大 于 等 于 3的 极 大 平 面 图 中 不 可 能 有 割 点 和 桥 . 设 G为 n(n3)阶 极 大 平 面 图 , 则 G每 个 面 的 次 数 均 为 3. 任 何 n(n4)阶 极 大 平 面 图 G均 有 (G)3. 7 实 例3个 图 都 是 平 面 图 , 但 只 有 右 边 的 图 为 极 大 平 面 图 . 8 极 小 非 平 面 图 定 义 若 G是 非 平 面 图 , 并 且 任 意 删 除 一 条 边 所 得 图都 是 平 面 图 , 则 称 G为 极 小 非 平 面 图 .说 明 : K5, K3,3都 是 极 小 非 平 面 图 极 小 非 平 面 图 必 为 简 单 图下 面 4个 图 都 是 极 小 非 平 面 图 9 欧 拉 公 式 定 理 8.11 (欧 拉 公 式 ) 设 G为 n阶 m条 边 r个 面 的 连 通 平 面 图 ，则 nm+r=2. 证 对 边 数 m做 归 纳 证 明 . m=0, G为 平 凡 图 , 结 论 为 真 .设 m=k(k0)结 论 为 真 , m=k+1时 分 情 况 讨 论 如 下 : (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时 结 论 成 立 . (2) 否 则 ,删 除 一 个 圈 上 的 一 条 边 ,记 作 G . G 连 通 , 有 n个 顶点 ,k条 边 和 r-1个 面 . 由 归 纳 假 设 , n-k+(r-1)=2, 即 n-(k+1)+r=2,得 证 m=k+1时 结 论 也 成 立 . 证 毕 . 10 欧 拉 公 式 (续 )欧 拉 公 式 的 推 广 设 G是 有 p (p2) 个 连 通 分 支 的 平 面 图 , 则 n m + r = p + 1证 设 第 i 个 连 通 分 支 有 ni个 顶 点 , mi 条 边 和 ri 个 面 . 对 各 连 通 分 支 用 欧 拉 公 式 , ni mi + ri = 2, i = 1, 2, , p求 和 并 注 意 r = r1+rp+ p1, 即 得 n m + r = p + 1 11 与 欧 拉 公 式 有 关 的 定 理 )2(2 nl lm K 5 K3,3 定 理 设 G为 n阶 连 通 平 面 图 , 有 m条 边 , 且 每 个 面 的 次 数 不小 于 l (l 3), 则 证 由 定 理 (各 面 次 数 之 和 等 于 边 数 的 2倍 )及 欧 拉 公 式 得 2m lr = l (2+m-n)可 解 得 所 需 结 论 . 推 论 K5 和 K3,3不 是 平 面 图 .证 用 反 证 法 , 假 设 它 们 是 平 面 图 ,则 K5 : n=5, m=10, l=3 K 3,3 : n=6, m=9, l=4与 定 理 矛 盾 . 12 与 欧 拉 公 式 有 关 的 定 理 (续 )1(2 pnl lm定 理 : 设 G为 有 p (p2) 个 连 通 分 支 的 平 面 图 , 且 每 个 面 的 次 数 不 小 于 l (l 3), 则定 理 设 G为 简 单 平 面 图 ， 则 (G)5. 13 同 胚 与 收 缩 消 去 2度 顶 点 v 如 上 图 从 (1)到 (2)插 入 2度 顶 点 v 如 上 图 从 (2)到 (1)G1与 G2同 胚 : G1与 G2同 构 , 或经 过 反 复 插 入 、 或 消 去 2度 顶点 后 同 构收 缩 边 e 如 下 图 从 (1)到 (2) 14 库 拉 图 斯 基 定 理定 理 G是 平 面 图 G中 不 含 与 K5同 胚 的 子 图 , 也 不含 与 K3,3同 胚 的 子 图 .定 理 G是 平 面 图 G中 无 可 收 缩 为 K5的 子 图 , 也 无可 收 缩 为 K3,3的 子 图 . 15 非 平 面 图 证 明例 证 明 下 述 2个 图 均 为 非 平 面 图 . 证 图 中 红 色 部 分 分 别 与 K 3,3和 K5 同 胚 16 平 面 图 的 对 偶 图 定 义 设 平 面 图 G, 有 n个 顶 点 , m条 边 和 r个 面 , 构 造 G的 对 偶 图 G*=如 下 ：在 G的 每 一 个 面 Ri中 任 取 一 个 点 vi*作 为 G*的 顶 点 , V*= vi*| i=1,2,r .对 G每 一 条 边 ek, 若 ek在 G的 面 Ri与 Rj的 公 共 边 界 上 , 则 作 边 ek*=(vi*,vj*), 且 与 ek相 交 ; 若 ek为 G中 的 桥 且 在面 R i的 边 界 上 , 则 作 环 ek*=(vi*,vi*). E*= ek*| k=1,2, ,m . 17 平 面 图 的 对 偶 图 （ 续 ）例 黑 色 实 线 为 原 平 面 图 , 红 色 虚 线 为 其 对 偶 图 18 平 面 图 的 对 偶 图 (续 )性 质 ： G*是 平 面 图 ， 而 且 是 平 面 嵌 入 . G*是 连 通 图 若 边 e为 G中 的 环 ， 则 G*与 e对 应 的 边 e*为 桥 ; 若 e为 桥 ， 则 G*中 与 e对 应 的 边 e*为 环 . 在 多 数 情 况 下 ， G*含 有 平 行 边 . 同 构 的 平 面 图 的 对 偶 图 不 一 定 同 构 . 上 面 两 个 平 面 图 是 同 构 的 , 但 它 们 的 对 偶 图 不 同 构 . 19 平 面 图 与 对 偶 图 的 阶 数 、 边 数 与 面 数 之 间 的 关 系 :设 G*是 平 面 图 G的 对 偶 图 ， n*, m*, r*和 n, m, r分 别为 G*和 G的 顶 点 数 、 边 数 和 面 数 ， 则(1) n*= r(2) m*=m(3) r*=n-p+1, 其 中 p是 G的 连 通 分 支 数(4) 设 G*的 顶 点 vi*位 于 G的 面 Ri中 , 则 d(vi*)=deg(Ri)平 面 图 的 对 偶 图 (续 )