今 天 有 随 堂 练 习, 写 完 后 与 上 次 的 作 业 一 起 交 1
平 面 图 的 面 染 色 和 有 向 图 程 龚 (gcheng@nju.edu.cn)
本 节 课 的 主 要 内 容 7.7 平 面 图 的 面 染 色 和 四 色 猜 想 8.1 有 向 图 的 基 本 概 念 8.2 有 向 路 与 有 向 圈 8.3 有 向 图 的 连 通 性 及 无 向 图 的 强 连 通 定 向 8.5 竞 赛 图 3
五 色 定 理 定 理 6.2.4 除 完 全 图 和 奇 圈 以 外 的 连 通 简 单 图 G 满 足 χ Δ 定 理 7.7.3 对 于 任 何 平 面 图 G,χ(G) 5 4
五 色 定 理 ( 续 ) 定 理 7.7.3 对 于 任 何 平 面 图 G,χ(G) 5 证 明 : 数 学 归 纳 法 重 边 和 环 边 不 影 响 色 数 只 需 讨 论 简 单 图 ν 5 时, 显 然 成 立 假 设 ν=n-1 时 成 立, 则 ν=n 时 : 1. 定 理 7.2.8 设 G 是 ν 3 的 简 单 平 面 图, 则 δ 5 G 中 存 在 顶 点 满 足 d() 5 2. 如 果 d() 4, 你 能 完 成 G 的 正 常 5 染 色 吗? 归 纳 假 设 G- 是 5 色 可 染 的 染 上 与 所 有 邻 点 相 异 的 颜 色 G 是 5 色 可 染 的 得 证 5
五 色 定 理 ( 续 ) 定 理 7.7.3 对 于 任 何 平 面 图 G,χ(G) 5 证 明 : 3. 如 果 d()=5: 1. 将 的 邻 点 按 顺 时 针 编 号 2. 如 果 G- 的 正 常 5 染 色 中, 这 5 个 顶 点 存 在 撞 色, 你 能 完 成 G 的 正 常 5 染 色 吗? 3. 否 则, 这 5 个 顶 点 颜 色 互 不 相 同, 设 为 色 1 至 色 5 考 察 染 为 色 1 和 色 3 的 所 有 顶 点 在 G- 中 的 导 出 子 图 G 13 4. 如 果 其 中 和 3 不 在 G 13 的 同 一 个 连 通 分 支 中, 你 能 完 成 G 的 正 常 5 染 色 吗? 在 所 在 的 连 通 分 支 中, 对 换 色 1 和 色 3( 不 影 响 其 它 4 点 ) 5. 否 则, 存 在 到 3 的 路 2 和 4 在 G 24 的 不 同 连 通 分 支 中, 你 能 完 成 G 的 正 常 5 染 色 吗? 在 2 所 在 的 连 通 分 支 中, 对 换 色 2 和 色 4 ( 不 影 响 其 它 4 点 ) 5 2 4 3 6
Percy John Heawood, 英 国, 1861--1955 毕 其 一 生 研 究 四 色 定 理, 未 遂, 但 推 翻 了 前 人 的 错 误 证 明, 并 给 出 了 五 色 定 理 http://learn-math.info/history/photos/heawood.jpeg 7
平 面 图 的 面 染 色 http://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/world_using_the_four_color_theorem.png/800px- World_using_the_four_color_theorem.png 8
平 面 图 的 面 染 色 ( 续 ) 面 k 染 色 面 正 常 k 染 色 边 界 有 公 共 边 的 面 不 同 色 面 k 色 可 染 的 面 色 数 9
平 面 图 的 面 染 色 ( 续 ) 对 偶 图 面 à 点 公 共 边 界 上 的 边 à 连 接 两 点 的 边 割 边 à 环 10
平 面 图 的 面 染 色 ( 续 ) 你 能 不 能 借 助 对 偶 图 来 证 明 : 平 面 图 一 定 是 面 5 色 可 染 的? 定 理 7.7.1: 平 面 图 的 面 色 数 = 对 偶 图 的 色 数, 为 什 么? 所 有 对 偶 图 都 是 平 面 图 定 理 7.7.3: 平 面 图 的 色 数 5 你 能 就 此 给 出 一 个 平 面 图 的 面 染 色 算 法 吗? 11
四 色 猜 想 对 于 任 何 平 面 图 G,χ(G) 4? 12
四 色 猜 想 ( 续 ) 1. 三 角 剖 分 平 面 图 (triangulation) 每 个 面 的 度 数 都 为 3 的 简 单 平 面 图 2. 构 形 (configuration) 每 个 内 部 面 的 度 数 都 为 3 的 简 单 平 面 图 13
四 色 猜 想 ( 续 ) 3. 极 小 反 例 (minimal counterexample) χ>4 的 简 单 平 面 图 中 阶 最 小 的 一 个 不 失 一 般 性, 设 其 为 三 角 剖 分 平 面 图 否 则 : 加 边 使 其 成 为 三 角 剖 分 平 面 图, 且 加 边 之 后 显 然 还 是 一 个 极 小 反 例 4. 不 可 免 集 (unaoidable set) 构 形 的 集 合, 任 何 一 个 极 小 反 例 至 少 包 含 其 中 一 个 构 形 例 如, 以 下 是 一 个 不 可 免 集, 为 什 么? 定 理 7.2.8 设 G 是 ν 3 的 简 单 平 面 图, 则 δ 5 如 果 找 到 一 个 不 可 免 集, 其 中 每 个 构 形 都 不 可 能 出 现 在 极 小 反 例 中 ( 称 作 可 约 的,reducible), 就 出 现 了 矛 盾, 因 此 极 小 反 例 不 存 在, 四 色 猜 想 得 证 14
四 色 猜 想 ( 续 ) 5. 1879 年,Alfred Kempe 证 明 了 以 下 不 可 免 集 中 的 每 个 构 形 都 是 可 约 的 第 一 个 很 容 易 证 明, 你 能 看 出 来 吗? G 是 极 小 反 例 G- 是 4 色 可 染 的 G- 的 正 常 4 染 色 中, 的 邻 点 最 多 只 占 用 3 种 颜 色 可 以 染 第 四 种 颜 色 G 是 4 色 可 染 的 G 不 是 反 例 第 二 个 也 可 以 证 明 但 是 1890 年,Heawood 发 现 第 三 个 的 证 明 存 在 漏 洞 15
四 色 猜 想 ( 续 ) 6. 人 们 试 图 寻 找 更 多 的 可 约 构 形, 并 组 成 不 可 免 集 7. 1970 前 后,Heinrich Heesch 率 先 设 计 出 算 法 让 计 算 机 来 做 这 件 事, 眼 看 就 要 成 功 了 然 而 关 键 时 刻, 他 的 研 究 经 费 被 砍 掉 了 8. 1976-1977 年,Kenneth Appel Wolfgang Haken 和 John Koch, 宣 称 经 过 计 算 机 超 过 1000 小 时 的 计 算, 找 到 了 一 个 由 1936 个 可 约 构 形 组 成 的 不 可 免 集 9. 之 后, 一 些 bug 被 陆 续 发 现 和 修 复 10. 故 事 就 此 结 束 了 吗? 16
四 色 猜 想 ( 续 ) 11. 即 使 算 法 是 正 确 的, 如 何 保 证 计 算 机 在 运 行 ( 证 明 ) 的 过 程 中 没 有 出 错 呢? 无 法 保 证 12. 但 是, 这 个 证 明 的 工 作 量 太 大, 以 至 于 不 可 能 人 工 验 证, 或 者 说, 人 工 验 证 的 过 程 中 出 错 的 概 率 更 大 所 以, 我 们 选 择 相 信 计 算 机, 正 如 我 们 选 择 相 信 人 工 证 明 一 样 17
Alfred Kempe, 英 国, 1849--1922 尽 管 证 错 了, 但 他 对 于 四 色 定 理 证 明 的 推 动 仍 然 是 巨 大 的 http://upload.wikimedia.org/wikipedia/commons/a/ab/alfred_bray_kempe.jpeg 18
Heinrich Heesch, 德 国, 1906--1995 http://en.wikipedia.org/wiki/heinrich_heesch#/media/file:heesch,heinrich_1930_jena.jpg 19
Kenneth Appel, 美 国, 1932--2013 Wolfgang Haken, 德 国, 1928-- 没 有 照 片 的 John Koch 是 那 个 程 序 员 http://www.math.illinois.edu/people/ken-appel.jpg http://www.las.illinois.edu/images/news/2009/haken.jpg 20
最 后 四 次 课 的 安 排 5 月 25 日 : 网 络 流 习 题 讲 解 6 月 01 日 : 调 到 ( 暂 定 )6 月 13 日 7 8 节, 安 排 答 疑 6 月 08 日 : 图 论 的 应 用 6 月 15 日 : 期 末 考 试 21
考 试 安 排 最 后 一 次 课 随 堂 考 试 时 间 :6 月 15 日,8:00-10:00 地 点 : 仙 II-404 形 式 : 闭 卷 题 型 : 证 明 或 解 答 题, 包 括 应 用 题 开 放 性 问 题 内 容 : 每 个 专 题 约 1 题 图 的 基 本 概 念 连 通 匹 配 中 国 邮 递 员 问 题 和 旅 行 商 问 题 支 配 独 立 覆 盖 平 面 图 染 色 网 络 流 要 求 : 基 本 概 念 重 要 定 理 重 要 算 法 的 熟 练 应 用 难 度 : 与 作 业 类 似 22
有 序 对 无 序 对 (unordered pair) 含 有 2 个 或 1 个 元 素 的 集 合 (, 2 ) = {, 2 },( 2, 2 )={ 2 } 有 序 对 (ordered pair) <a 1,b 1 >=<a 2,b 2 > 当 且 仅 当 a 1 =a 2 且 b 1 =b 2 有 序 对 的 集 合 表 示 能 不 能 将 <a,b> 定 义 为 {a,b}? Kuratowski 的 定 义 :<a,b>={{a},{a,b}} 23
有 序 对 ( 续 ) 如 果 <a,b> 定 义 为 {{a},{a,b}}, 那 么 <a 1,b 1 >=<a 2,b 2 > 当 且 仅 当 a 1 =a 2 且 b 1 =b 2 证 明 : : a 1 =a 2 且 b 1 =b 2 {{a 1 },{a 1,b 1 }}={{a 2 },{a 2,b 2 }} <a 1,b 1 >=<a 2,b 2 > : 如 果 a 1 =b 1 :<a 1,b 1 > = {{a 1 },{a 1,b 1 }} = {{a 1 },{a 1,a 1 }} = {{a 1 }} = <a 2,b 2 > = {{a 2 },{a 2,b 2 }} {a 1 }={a 2 }={a 2,b 2 } a 1 =a 2 =b 1 =b 2 如 果 a 1 b 1 :<a 1,b 1 >=<a 2,b 2 > {{a 1 },{a 1,b 1 }}={{a 2 },{a 2,b 2 }} 如 果 {a 1 }={a 2,b 2 } a 1 =a 2 =b 2 {{a 1 },{a 1,b 1 }}={{a 2 },{a 2,b 2 }}={{a 1 }} a 1 =b 1 矛 盾 这 种 情 况 不 可 能 {a 1 }={a 2 } 略 24
有 向 图 弧 G=<V,A> V: 顶 点 集 A: 弧 集 (arc set) 弧 集 是 一 个 有 向 对 的 集 合 弧 又 称 有 向 边 (directed edge) 一 些 术 语 弧 的 尾 (tail) 弧 的 头 (head) 环 弧 : 头 尾 相 同 的 弧 并 行 弧 : 具 有 相 同 头 和 相 同 尾 的 弧 简 单 有 向 图 : 无 环 弧 无 并 行 弧 // 我 们 一 般 只 讨 论 简 单 有 向 图 反 向 弧 : 简 单 有 向 图 中, 头 尾 相 反 的 弧 2 a 1 a 3 a 6 a 7 5 a a 5 2 a 8 a 4 3 4 25
度 和 邻 点 出 度 (outdegree):d + () 入 度 (indegree):d - () 最 小 出 度 :δ + 最 小 入 度 :δ - 最 大 出 度 :Δ + 最 大 入 度 :Δ - 定 理 8.1.1 对 于 任 何 有 向 图 G, 都 有 V d ( G ) a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 4 3 4 + ( ) = d V ( G ) - ( ) = d 2 ( ) = ε 出 邻 点 和 入 邻 点 26
途 径 迹 路 圈 有 向 途 径 顶 点 和 弧 交 替 出 现 的 序 列 与 弧 的 方 向 一 致 有 向 迹 弧 不 重 复 出 现 有 向 路 顶 点 不 重 复 出 现 有 向 圈 起 点 和 终 点 相 同 a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 4 3 4 27
有 向 图 的 关 联 矩 阵 矩 阵 中 应 该 填 什 么? a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 2 3 4 5 a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 4 3 4 28
有 向 图 的 邻 接 矩 阵 矩 阵 中 应 该 填 什 么? 2 3 4 5 2 3 4 5 a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 4 3 4 它 还 是 对 称 矩 阵 吗? 如 何 基 于 邻 接 矩 阵 求 顶 点 的 出 入 度? 29
底 图 和 定 向 底 图 (underlying graph): 有 向 图 à 无 向 图 定 向 (orientation): 无 向 图 à 有 向 图 不 唯 一 竞 赛 图 (tournament): 完 全 图 的 定 向 a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 4 3 4 底 图 定 向 a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 4 3 4 30
连 通 弱 连 通 的 (weakly connected) 底 图 是 连 通 的 强 连 通 的 (strongly connected) 任 取 顶 点 u 和, 存 在 u 到 的 有 向 路 强 连 通 分 支 (strong component) 极 大 强 连 通 子 图 强 连 通 分 支 之 间 会 不 会 有 公 共 顶 点? 强 连 通 分 支 图 这 个 图 中 会 不 会 存 在 有 向 圈? a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 4 3 4 S 1235 S 4 31
强 连 通 的 充 要 条 件 定 理 8.3.2 G 是 强 连 通 有 向 图 的 充 要 条 件 是 G 的 所 有 顶 点 在 一 条 有 向 闭 途 径 上 证 明 : : 你 能 自 己 证 明 吗? V 1 à V 2 à à V ν à V 1 : 你 能 自 己 证 明 吗? 通 过 所 有 顶 点 的 有 向 闭 途 径 包 含 任 两 顶 点 之 间 的 有 向 路 32
强 连 通 定 向 定 理 8.3.3 无 向 图 G 可 定 向 成 强 连 通 图 的 充 分 必 要 条 件 为 :G 连 通 且 无 割 边 证 明 : ν=1 时, 显 然 成 立 ν>1 时 : : 反 证 法, 你 能 自 己 证 明 吗? : 构 造 法 1. G 无 割 边 G 中 有 圈 G 1 G 1 可 定 向 为 强 连 通 的 2. 如 果 G 1 不 是 G 的 生 成 子 图 G 1 外 存 在 一 点 3. 边 形 式 的 Menger 定 理 的 推 论 (2.4.2):k- 边 连 通 图 任 二 顶 点 被 k 条 两 两 无 公 共 边 的 路 所 连 到 G 1 存 在 两 条 无 公 共 边 的 路, 与 G 1 并 为 G 2 G 2 可 定 向 为 强 连 通 的 4. 如 果 G 2 仍 不 是 G 的 生 成 子 图, 重 复 这 个 过 程, 由 于 顶 点 是 有 限 的, 必 然 终 止 于 G 的 生 成 子 图 G n, 且 G n 可 定 向 为 强 连 通 的 5. 剩 余 边 任 意 定 向 G 1 构 造 法 同 时 也 是 一 种 算 法 但 还 存 在 更 加 高 效 的 算 法 33
竞 赛 图 王 (king) 到 其 它 任 何 顶 点 都 有 长 不 超 过 2 的 有 向 路 未 必 唯 一 2 5 3 4 34
竞 赛 图 ( 续 ) 定 理 8.5.2 竞 赛 图 中 出 度 最 大 的 顶 点 必 为 王 证 明 : 设 是 出 度 最 大 的 顶 点 如 果 d + ()=ν-1: 显 然 成 立 如 果 d + ()<ν-1, 设 的 出 邻 点 为,, k, 入 邻 点 为 k+1,, ν-1 : 对 于 k+1,, ν-1 中 的 每 个 j :,, k 中 必 有 j 的 入 邻 点 从 到 j 有 长 为 2 的 有 向 路 得 证 d + ( j ) d + (),, k 不 可 能 都 是 j 的 出 邻 点 k k+1 j ν-1 35
竞 赛 图 ( 续 ) 定 理 8.5.3 竞 赛 图 中 一 个 顶 点 是 唯 一 的 王 当 且 仅 当 的 出 度 为 ν-1 证 明 : : 反 证 法 1. 假 设 唯 一 的 王 满 足 d + ()<ν-1 的 所 有 入 邻 点 导 出 的 子 竞 赛 图 有 自 己 的 王 u 2. u 到 有 弧 u 到 的 出 邻 点 有 长 为 2 的 有 向 路 u 也 是 原 图 的 王 不 是 唯 一 的 王 矛 盾 :d + ()= ν-1 是 王 且 无 入 邻 点 是 唯 一 的 王 u 36
课 堂 练 习 1. 证 明 或 者 否 定 : 具 有 10 个 顶 点 的 简 单 有 向 图 中, 顶 点 的 出 度 不 可 能 两 两 都 互 不 相 同 2. 证 明 或 者 否 定 : 存 在 一 个 具 有 n 个 顶 点 (n>0) 的 竞 赛 图 且 每 个 顶 点 的 出 度 和 入 度 都 相 等, 当 且 仅 当 n 是 奇 数 37