离散数学第十七章平面

1 第 十 七 章 平 面 图本 章 的 主 要 内 容l 平 面 图 的 基 本 概 念l 欧 拉 公 式l 平 面 图 的 判 断l 平 面 图 的 对 偶 图 2 引 言许 多 实 际 问 题 可 以 抽 象 为 这 样 的 模 式 ： 在 一 些 表 示 客 体 的 结点 之 间 “ 布 线 ” 、 “ 建 通 道 ” ， 以 建 立 它 们 之 间 的 某 些 联系 ， 要 求 这 些 “ 线 ” 、 “ 通 道 ” 在 一 个 平 面 上 而 又 不 相 互交 叠 。 这 正 是 本 章 要 讨 论 的 图 论 问 题 。例 如 ， 要 在 三 个 工 作 点 A,B,C和 三 个 原 料 库 L,M,N之 间 建 立各 工 作 点 到 原 料 库 的 传 输 线 ， 问 是 否 可 能 使 这 些 线 路 互 不相 交 ？ 如 果 用 结 点 表 示 工 作 站 ， 用 边 表 示 传 输 线 ， 那 么 上述 问 题 便 可 描 述 为 ： K3,3是 否 可 以 在 一 个 平 面 上 图 示 出 来 ，使 图 中 各 边 除 端 点 外 均 不 相 交 ？ 另 外 ， 印 刷 电 路 板 上 的 布线 与 交 通 道 路 的 设 计 等 都 是 此 类 问 题 。 为 了 深 入 讨 论 这 个问 题 ， 需 要 引 入 平 面 图 的 概 念 。 3在 图 中 ， (2)是 (1) 的 平 面 嵌 入 ， (4)是 (3)的 平 面 嵌 入 . 17.1 平 面 图 的 基 本 概 念定 义 17.1 (1) G可 嵌 入 曲 面 S若 能 将 G除 顶 点 外 无 边 相 交 地 画 在 S上(2) G是 可 平 面 图 或 平 面 图 G可 嵌 入 平 面 (3) 平 面 嵌 入 画 出 的 无 边 相 交 的 平 面 图(4) 非 平 面 图 无 平 面 嵌 入 的 无 向 图 (1) (2) (3) (4) 4 几 点 说 明 及 一 些 简 单 结 论一 般 所 谈 平 面 图 不 一 定 是 指 平 面 嵌 入 ， 上 图 中 4个 图 都 是 平面 图 ， 但 讨 论 某 些 性 质 时 ， 一 定 是 指 平 面 嵌 入 . 结 论 ： (1) K5, K3,3都 不 是 平 面 图 （ 待 证 ）(2) 设 GG， 若 G为 平 面 图 ， 则 G也 是 平 面 图 （ 定 理 17.1）(3) 设 GG， 若 G为 非 平 面 图 ， 则 G也 是 非 平 面 图 （ 定 理17.2） ， 由 此 可 知 ， Kn(n6)， K3,n(n4) 都 是 非 平 面 图 . (4) 平 行 边 与 环 不 影 响 平 面 性 . 5 平 面 图 (平 面 嵌 入 )的 面 与 次 数定 义 17.2 (1) G的 面 由 G的 平 面 嵌 入 的 边 将 平 面 化 分 成 的 区 域(2) 无 限 面 或 外 部 面 （ 可 用 R0表 示 ） 面 积 无 限 的 面(3) 有 限 面 或 内 部 面 （ 可 用 R1, R2, , Rk等 表 示 ） 面 积 有 限 的 面 (4) 面 Ri 的 边 界 包 围 Ri的 回 路 组(5) 面 Ri 的 次 数 Ri边 界 的 长 度 ， 用 deg(Ri)表 示 6定 理 17.4 平 面 图 各 面 次 数 之 和 等 于 边 数 的 两 倍 . 几 点 说 明l 若 平 面 图 G有 k个 面 ， 可 笼 统 地 用 R1, R2, , Rk表 示 ， 不 需要 指 出 外 部 面 .l 定 义 17.2(4) 中 回 路 组 是 指 ： 边 界 可 能 是 初 级 回 路 (圈 )， 可能 是 简 单 回 路 ， 也 可 能 是 复 杂 回 路 . 特 别 地 ， 还 可 能 是 非连 通 的 回 路 之 并 . 平 面 图 有 4个 面 ，deg(R1)=1, deg(R2)=3, deg(R 3)=2, deg(R0)=8. 请 写 各 面 的 边 界 . 7 极 大 平 面 图定 义 17.3 若 在 简 单 平 面 图 G中 的 任 意 两 个 不 相 邻 的 顶 点 之 间加 一 条 新 边 所 得 图 为 非 平 面 图 ， 则 称 G为 极 大 平 面 图 .注 意 ： 若 简 单 平 面 图 G中 已 无 不 相 邻 顶 点 ， G显 然 是 极 大 平面 图 ， 如 K1(平 凡 图 ), K2, K3, K4都 是 极 大 平 面 图 .极 大 平 面 图 的 主 要 性 质定 理 17.5 极 大 平 面 图 是 连 通 的 . 证 明 线 索 ： 否 则 ， 加 新 边 不 破 坏 平 面 性定 理 17.6 n（ n3） 阶 极 大 平 面 图 中 不 可 能 有 割 点 和 桥 . 证 明 线 索 ： 由 定 理 17.5及 n3可 知 ， G中 若 有 桥 ， 则 一 定 有割 点 ， 因 而 只 需 证 无 割 点 即 可 . 方 法 还 是 反 证 法 . 8 证 明 线 索 ：(1) 由 于 n3, 又 G必 为 简 单平 面 图 可 知 ， G每 个 面 的次 数 均 3.(2) 因 为 G为 平 面 图 ， 又 为 极大 平 面 图 . 可 证 G不 可 能存 在 次 数 3的 面 . 就 给 出 的 图 讨 论 即 可 . 极 大 平 面 图 的 性 质定 理 17.7 设 G为 n（ n3） 阶 极 大 平 面 图 ， 则 G的 每 个 面 的次 数 均 为 3. 9 定 理 17.7中 的 条 件 也 是 极 大 平 面 图 的 充 分 条 件 . 定 理 17.7 设 G为 n (n3) 阶 平 面 图 ， 且 每 个 面 的 次 数 均 为 3，则 G为 极 大 平 面 图 . 定 理 的 应 用上 图 中 ， 只 有 (3)为 极 大 平 面 图 (1) (2) (3) 10 极 小 非 平 面 图定 义 17.4 若 在 非 平 面 图 G中 任 意 删 除 一 条 边 ， 所 得 图 G为 平面 图 ， 则 称 G为 极 小 非 平 面 图 .由 定 义 不 难 看 出 ：(1) K5, K3,3都 是 极 小 非 平 面 图(2) 极 小 非 平 面 图 必 为 简 单 图图 中 所 示 各 图 都 是 极 小 非 平 面 图 . 11定 理 17.9 （ 欧 拉 公 式 的 推 广 ） 设 G是 具 有 k（ k2） 个 连 通分 支 的 平 面 图 ， 则 nm+r=k+1证 明 中 对 各 连 通 分 支 用 欧 拉 公 式 ， 并 注 意即 可 . ki i krr 1 )1( 17.2 欧 拉 公 式定 理 17.8 设 G为 n阶 m条 边 r个 面 的 连 通 平 面 图 ， 则 nm+r=2（ 此 公 式 称 为 欧 拉 公 式 ）证 对 边 数 m做 归 纳 法m=0， G为 平 凡 图 ， 结 论 为 真 .设 m=k（ k1） 结 论 为 真 ， m=k+1时 分 情 况 讨 论 .(1) G中 无 圈 ， 则 G为 树 ， 删 除 一 片 树 叶 ， 用 归 纳 假 设 .(2) 否 则 ， 在 某 一 个 圈 上 删 除 一 条 边 ， 进 行 讨 论 . 12 )2(2 nl lm )2()deg(2 1 nmlrlRm ri i )2(2 nl lm )1(2 knl lm解 得 定 理 17.11 在 具 有 k（ k2） 个 连 通 分 支 的 平 面 图 中 ，与 欧 拉 公 式 有 关 的 定 理定 理 17.10 设 G为 连 通 的 平 面 图 ， 且 deg(Ri)l, l3， 则 证 由 定 理 17.4及 欧 拉 公 式 得推 论 K5, K3,3不 是 平 面 图 . 13 定 理 17.12 设 G为 n（ n3） 阶 m条 边 的 简 单 平 面 图 ， 则 m3n6. 证 设 G有 k（ k1） 个 连 通 分 支 ， 若 G为 树 或 森 林 ， 当 n3时 ，m3n6为 真 . 否 则 G中 含 圈 ， 每 个 面 至 少 由 l（ l3） 条 边 围 成， 又 2212 ll l定 理 17.13 设 G为 n（ n3） 阶 m条 边 的 极 大 平 面 图 ， 则 m=3n6.证 由 定 理 17.4, 欧 拉 公 式 及 定 理 17.7所 证 . 定 理 17.14 设 G 为 简 单 平 面 图 ， 则 (G)5. 证 阶 数 n6， 结 论 为 真 . 当 n7 时 ， 用 反 证 法 . 否 则 会 推 出2m6n m3n， 这 与 定 理 17.12矛 盾 . 与 欧 拉 公 式 有 关 的 定 理在 l=3达 到 最 大 值 ， 由 定 理 17.11可 知 m3n6. 14 17.3 平 面 图 的 判 断1. 插 入 2度 顶 点 和 消 去 2度 顶 点定 义 17.5(1) 消 去 2度 顶 点 v， 见 下 图 中 ， 由 (1) 到 (2) (2) 插 入 2度 顶 点 v， 见 下 图 中 ， 从 (2) 到 (1) . (1) (2) 15 2. 收 缩 边 e， 见 下 图 所 示 .3. 图 之 间 的 同 胚定 义 17.6 若 G1G2， 或 经 过 反 复 插 入 或 消 去 2度 顶 点 后 所得 G1G2， 则 称 G1与 G2同 胚 . 图 的 同 胚右 边 两 个 图 同 胚 16 平 面 图 判 定 定 理定 理 17.15 G是 平 面 图 G中 不 含 与 K5或 K3,3同 胚 的 子 图 .定 理 17.16 G是 平 面 图 G中 无 可 收 缩 为 K5或 K3,3的 子 图例 1 证 明 所 示 图 (1)与 (2)均 为 非 平 面 图 . (1) (2)右 图 (1),(2)分 别 为原 图 (1), (2)的 子 图与 K 3,3, K5同 胚 . 子 图 (1) (2) 17 17.4 平 面 图 的 对 偶 图定 义 17.7 设 G是 某 平 面 图 的 某 个 平 面 嵌 入 ， 构 造 G的 对 偶 图G*如 下 ：(1) 在 G的 面 Ri中 放 置 G*的 顶 点 v*i. (2) 设 e为 G的 任 意 一 条 边 . 若 e在 G的 面 Ri与 Rj 的 公 共 边 界 上 ， 做 G*的 边 e*与 e相 交 ， 且 e*关 联 G*的 位 于 Ri与 Rj中 的 顶 点 v*i与 v*j， 即 e*=(v*i,v*j)， e*不 与 其 它 任 何 边 相 交 . 若 e为 G中 的 桥 且 在 面 R i的 边 界 上 ， 则 e*是 以 Ri中 G*的 顶 点 v*i为 端 点 的 环 ， 即 e*=(v*i,v*i). 18 下 面 两 图 中 ， 实 线 边 图 为 平 面 图 ， 虚 线 边 图 为 其 对 偶 图 . 实 例 19 G 的 对 偶 图 G*有 以 下 性 质 ：(1) G*是 平 面 图 ， 而 且 是 平 面 嵌 入 .(2) G*是 连 通 图(3) 若 边 e为 G中 的 环 ， 则 G*与 e对 应 的 边 e*为 桥 ， 若 e为 桥 ，则 G*中 与 e对 应 的 边 e*为 环 .(4) 在 多 数 情 况 下 ， G*为 多 重 图 （ 含 平 行 边 的 图 ） .(5) 同 构 的 平 面 图 （ 平 面 嵌 入 ） 的 对 偶 图 不 一 定 是 同 构 的 . 如 上 面 的 例 子 . 对 偶 图 的 性 质 20 平 面 图 与 对 偶 图 的阶 数 、 边 数 与 面 数 之 间 的 关 系定 理 17.17 设 G*是 连 通 平 面 图 G的 对 偶 图 ， n*, m*, r*和 n, m, r分 别 为 G*和 G的 顶 点 数 、 边 数 和 面 数 ， 则(1) n*= r(2) m*=m(3) r*=n(4) 设 G*的 顶 点 v*i位 于 G的 面 Ri中 ， 则 dG*(v*i)=deg(Ri)证 明 线 索(1)、 (2)平 凡 .(3) 应 用 欧 拉 公 式 .(4) 的 证 明 中 注 意 ， 桥 只 能 在 某 个 面 的 边 界 中 ， 非 桥 边 在 两个 面 的 边 界 上 . 21 平 面 图 与 对 偶 图 的阶 数 、 边 数 与 面 数 之 间 的 关 系定 理 17.18 设 G*是 具 有 k（ k2） 个 连 通 分 支 的 平 面 图 G的 对偶 图 ， 则(1) n*= r(2) m*=m(3) r*=nk+1(4) 设 G*的 顶 点 v*i位 于 G的 面 Ri中 ， 则 dG*(v*i)=deg(Ri)其 中 n*, m*, r*, n, m, r同 定 理 17.17. 证 明 (3) 时 应 同 时 应 用 欧 拉 公 式 及 欧 拉 公 式 的 推 广 . 22 自 对 偶 图定 义 17.8 设 G*是 平 面 图 G的 对 偶 图 ， 若 G*G， 则 称 G为 自对 偶 图 . 轮 图 定 义 如 下 ：在 n1（ n4） 边 形 Cn1内 放 置 1个 顶 点 ， 使 这 个 顶 点 与 Cn1上 的 所 有 的 顶 点 均 相 邻 . 所 得 n 阶 简 单 图 称 为 n阶 轮 图 . n为 奇数 的 轮 图 称 为 奇 阶 轮 图 ， n为 偶 数 的 轮 图 称 为 偶 阶 轮 图 ， 常将 n 阶 轮 图 记 为 Wn. 轮 图 都 是 自 对 偶 图 . 图 中 给 出 了 W 6和 W7. 请 画 出 它 们 的 对 偶 图 ，从 而 说 明 它 们 都 是 自 对 偶 图 . 23 第 十 七 章 习 题 课主 要 内 容l 平 面 图 的 基 本 概 念l 欧 拉 公 式l 平 面 图 的 判 断l 平 面 图 的 对 偶 图基 本 要 求l 深 刻 理 解 本 部 分 的 基 本 概 念 ： 平 面 图 、 平 面 嵌 入 、 面 、次 数 、 极 大 平 面 图 、 极 小 非 平 面 图 、 对 偶 图l 牢 记 极 大 平 面 图 的 主 要 性 质 和 判 别 方 法l 熟 记 欧 拉 公 式 及 推 广 形 式 ， 并 能 用 欧 拉 公 式 及 推 广 形 式证 明 有 关 定 理 与 命 题l 会 用 库 拉 图 斯 基 定 理 证 明 某 些 图 不 是 平 面 图 l 记 住 平 面 图 与 它 的 对 偶 图 阶 数 、 边 数 、 面 数 之 间 的 关 系 24 练 习 1解 设 G的 阶 数 、 边 数 、 面 数 分 别 为 n, m, r. (1) 否 则 ， 由 欧 拉 公 式 得 2m 5r = 5 (2+mn) 由 于 (G)3及 握 手 定 理 又 有 2m 3n 由 与 得 m30 又 有 r=2+mn 12 由 及 又 可 得 m30 , 是 矛 盾 的 . (2) 正 十 二 面 体 是 一 个 反 例 1. 设 G是 连 通 的 简 单 的 平 面 图 ， 面 数 r12， (G)3. (1) 证 明 G中 存 在 次 数 4的 面(2) 举 例 说 明 当 r=12时 ， (1) 中 结 论 不 真 . 25 2. 设 G是 阶 数 n11的 无 向 平 面 图 ， 证 明 G和 不 可 能 全 是平 面 图 . G证 只 需 证 明 G和 中 至 少 有 一 个 是 非 平 面 图 . 采 用 反 证 法 . 否 则 与 G 都 是 平 面 图 ， 下 面 来 推 出 矛 盾 .G与 的 边 数 m, m应 满 足 ( Kn的 边 数 ) 由 鸽 巢 原 理 知 m或 m， 不 妨 设 m， GG G 2 )1( nnmm 4 )1( nnm又 由 定 理 17.12 知 m 3n 6 由 与 得 n213n+24 0 由 解 得 2 n 10 与 n 11矛 盾 . 其 实 ， 当 n=9,10时 ， 命 题 结 论 已 真 . 练 习 2 26 3. 证 明 下 图 为 非 平 面 图 练 习 3 27 证 明证 用 库 拉 图 斯 基 定 理 证 明方 法 一 . 下 图 为 原 图 的 子图 ， 它 是 K3,3， 由 库 拉 图 斯基 定 理 得 证 命 题 . 方 法 二 . 下 图 为 原 图 的 子 图 （ 删除 边 (a,f)） ， 收 缩 本 图 中 的 (a,e)和 (f,g)所 得 图 为 K5, 由 库 拉 图 斯基 定 理 得 证 命 题 . 28图 20 图 19 练 习 44. 设 G为 n（ n3） 阶 极 大 平 面 图 ， 证 明 G的 对 偶 图 G*是 2-边连 通 的 3-正 则 图 .证 证 明 中 用 上 n3的 极 大 平 面 图 的 性 质 ， 以 及 平 面 图 与 对偶 图 的 关 系 ， 对 偶 图 的 连 通 性 等 .(1) 证 G*是 2-边 连 通 的 . 由 G*的 连 通 性 可 知 ， (G*)1， 又 因 为 G为 极 大 平 面 图 ， 故 G为 简 单 图 ， 所 以 G*中 无 桥 （ 因 为 G中 无 环 ） ， 所 以 ， (G*)2. 故 G*为 2-边 连 通 的 .(2) 证 G*是 3-正 则 图 . 易 知 G*为 简 单 图 ， 且 每 个 顶 点 的 度 数 均 为 3（ 由 定 理 17.7决 定 ） ， 故 G*为 3-正 则 图 .