13 平面图的面染色和有向图

Size: px

Start display at page:

Download "13 平面图的面染色和有向图"

征径廖
7 years ago
Views:

1 今天有随堂练习, 写完后与上次的作业一起交 1

2 平面图的面染色和有向图程龚

3 本节课的主要内容 7.7 平面图的面染色和四色猜想 8.1 有向图的基本概念 8.2 有向路与有向圈 8.3 有向图的连通性及无向图的强连通定向 8.5 竞赛图 3

4 五色定理定理除完全图和奇圈以外的连通简单图 G 满足 χ Δ 定理对于任何平面图 G,χ(G) 5 4

5 五色定理 ( 续 ) 定理对于任何平面图 G,χ(G) 5 证明 : 数学归纳法重边和环边不影响色数只需讨论简单图 ν 5 时, 显然成立假设 ν=n-1 时成立, 则 ν=n 时 : 1. 定理设 G 是 ν 3 的简单平面图, 则 δ 5 G 中存在顶点满足 d() 5 2. 如果 d() 4, 你能完成 G 的正常 5 染色吗? 归纳假设 G- 是 5 色可染的染上与所有邻点相异的颜色 G 是 5 色可染的得证 5

ν 5 时, 显然成立假设 ν=n-1 时成立, 则 ν=n 时 : 1. 定理 7.2.

6 五色定理 ( 续 ) 定理对于任何平面图 G,χ(G) 5 证明 : 3. 如果 d()=5: 1. 将的邻点按顺时针编号 2. 如果 G- 的正常 5 染色中, 这 5 个顶点存在撞色, 你能完成 G 的正常 5 染色吗? 3. 否则, 这 5 个顶点颜色互不相同, 设为色 1 至色 5 考察染为色 1 和色 3 的所有顶点在 G- 中的导出子图 G 如果其中和 3 不在 G 13 的同一个连通分支中, 你能完成 G 的正常 5 染色吗? 在所在的连通分支中, 对换色 1 和色 3( 不影响其它 4 点 ) 5. 否则, 存在到 3 的路 2 和 4 在 G 24 的不同连通分支中, 你能完成 G 的正常 5 染色吗? 在 2 所在的连通分支中, 对换色 2 和色 4 ( 不影响其它 4 点 )

否则, 这 5 个顶点颜色互不相同, 设为色 1 至色 5 考察染为色 1 和色 3 的所有顶点在 G- 中的导出子图 G 13 4.

7 Percy John Heawood, 英国, 毕其一生研究四色定理, 未遂, 但推翻了前人的错误证明, 并给出了五色定理 7

8 平面图的面染色 World_using_the_four_color_theorem.png 8

9 平面图的面染色 ( 续 ) 面 k 染色面正常 k 染色边界有公共边的面不同色面 k 色可染的面色数 9

10 平面图的面染色 ( 续 ) 对偶图面 à 点公共边界上的边 à 连接两点的边割边 à 环 10

11 平面图的面染色 ( 续 ) 你能不能借助对偶图来证明 : 平面图一定是面 5 色可染的? 定理 7.7.1: 平面图的面色数 = 对偶图的色数, 为什么? 所有对偶图都是平面图定理 7.7.3: 平面图的色数 5 你能就此给出一个平面图的面染色算法吗? 11

12 四色猜想对于任何平面图 G,χ(G) 4? 12

13 四色猜想 ( 续 ) 1. 三角剖分平面图 (triangulation) 每个面的度数都为 3 的简单平面图 2. 构形 (configuration) 每个内部面的度数都为 3 的简单平面图 13

14 四色猜想 ( 续 ) 3. 极小反例 (minimal counterexample) χ>4 的简单平面图中阶最小的一个不失一般性, 设其为三角剖分平面图否则 : 加边使其成为三角剖分平面图, 且加边之后显然还是一个极小反例 4. 不可免集 (unaoidable set) 构形的集合, 任何一个极小反例至少包含其中一个构形例如, 以下是一个不可免集, 为什么? 定理设 G 是 ν 3 的简单平面图, 则 δ 5 如果找到一个不可免集, 其中每个构形都不可能出现在极小反例中 ( 称作可约的,reducible), 就出现了矛盾, 因此极小反例不存在, 四色猜想得证 14

15 四色猜想 ( 续 ) 年,Alfred Kempe 证明了以下不可免集中的每个构形都是可约的第一个很容易证明, 你能看出来吗? G 是极小反例 G- 是 4 色可染的 G- 的正常 4 染色中, 的邻点最多只占用 3 种颜色可以染第四种颜色 G 是 4 色可染的 G 不是反例第二个也可以证明但是 1890 年,Heawood 发现第三个的证明存在漏洞 15

16 四色猜想 ( 续 ) 6. 人们试图寻找更多的可约构形, 并组成不可免集前后,Heinrich Heesch 率先设计出算法让计算机来做这件事, 眼看就要成功了然而关键时刻, 他的研究经费被砍掉了年,Kenneth Appel Wolfgang Haken 和 John Koch, 宣称经过计算机超过 1000 小时的计算, 找到了一个由 1936 个可约构形组成的不可免集 9. 之后, 一些 bug 被陆续发现和修复 10. 故事就此结束了吗? 16

17 四色猜想 ( 续 ) 11. 即使算法是正确的, 如何保证计算机在运行 ( 证明 ) 的过程中没有出错呢? 无法保证 12. 但是, 这个证明的工作量太大, 以至于不可能人工验证, 或者说, 人工验证的过程中出错的概率更大所以, 我们选择相信计算机, 正如我们选择相信人工证明一样 17

18 Alfred Kempe, 英国, 尽管证错了, 但他对于四色定理证明的推动仍然是巨大的 18

19 Heinrich Heesch, 德国,

20 Kenneth Appel, 美国, Wolfgang Haken, 德国, 没有照片的 John Koch 是那个程序员

http://www.math.illinois.edu/people/ken-appel.

21 最后四次课的安排 5 月 25 日 : 网络流习题讲解 6 月 01 日 : 调到 ( 暂定 )6 月 13 日 7 8 节, 安排答疑 6 月 08 日 : 图论的应用 6 月 15 日 : 期末考试 21

22 考试安排最后一次课随堂考试时间 :6 月 15 日,8:00-10:00 地点 : 仙 II-404 形式 : 闭卷题型 : 证明或解答题, 包括应用题开放性问题内容 : 每个专题约 1 题图的基本概念连通匹配中国邮递员问题和旅行商问题支配独立覆盖平面图染色网络流要求 : 基本概念重要定理重要算法的熟练应用难度 : 与作业类似 22

23 有序对无序对 (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

24 有序对 ( 续 ) 如果 <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

25 有向图弧 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

26 度和邻点出度 (outdegree):d + () 入度 (indegree):d - () 最小出度 :δ + 最小入度 :δ - 最大出度 :Δ + 最大入度 :Δ - 定理对于任何有向图 G, 都有 V d ( G ) a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a ( ) = d V ( G ) - ( ) = d 2 ( ) = ε 出邻点和入邻点 26

27 途径迹路圈有向途径顶点和弧交替出现的序列与弧的方向一致有向迹弧不重复出现有向路顶点不重复出现有向圈起点和终点相同 a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a

28 有向图的关联矩阵矩阵中应该填什么? a 1 a 2 a 3 a 4 a 5 a 6 a 7 a a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a

29 有向图的邻接矩阵矩阵中应该填什么? a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 它还是对称矩阵吗? 如何基于邻接矩阵求顶点的出入度? 29

30 底图和定向底图 (underlying graph): 有向图 à 无向图定向 (orientation): 无向图 à 有向图不唯一竞赛图 (tournament): 完全图的定向 a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a 底图定向 a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a

31 连通弱连通的 (weakly connected) 底图是连通的强连通的 (strongly connected) 任取顶点 u 和, 存在 u 到的有向路强连通分支 (strong component) 极大强连通子图强连通分支之间会不会有公共顶点? 强连通分支图这个图中会不会存在有向圈? a 2 a 3 a 6 a 7 5 a a 5 2 a 8 a S 1235 S 4 31

32 强连通的充要条件定理 G 是强连通有向图的充要条件是 G 的所有顶点在一条有向闭途径上证明 : : 你能自己证明吗? V 1 à V 2 à à V ν à V 1 : 你能自己证明吗? 通过所有顶点的有向闭途径包含任两顶点之间的有向路 32

33 强连通定向定理无向图 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

34 竞赛图王 (king) 到其它任何顶点都有长不超过 2 的有向路未必唯一

35 竞赛图 ( 续 ) 定理竞赛图中出度最大的顶点必为王证明 : 设是出度最大的顶点如果 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

36 竞赛图 ( 续 ) 定理竞赛图中一个顶点是唯一的王当且仅当的出度为 ν-1 证明 : : 反证法 1. 假设唯一的王满足 d + ()<ν-1 的所有入邻点导出的子竞赛图有自己的王 u 2. u 到有弧 u 到的出邻点有长为 2 的有向路 u 也是原图的王不是唯一的王矛盾 :d + ()= ν-1 是王且无入邻点是唯一的王 u 36

37 课堂练习 1. 证明或者否定 : 具有 10 个顶点的简单有向图中, 顶点的出度不可能两两都互不相同 2. 证明或者否定 : 存在一个具有 n 个顶点 (n>0) 的竞赛图且每个顶点的出度和入度都相等, 当且仅当 n 是奇数 37

类似地, 又可定义变下限的定积分 : ( ). 与 ψ 统称为变限积分. f ( ) d f ( t) dt,, 注在变限积分 (1) 与 () 中, 不可再把积分变量写成的形式 ( 例如 ) 以免与积分上下限的

类似地, 又可定义变下限的定积分 : ( ). 与 ψ 统称为变限积分. f ( ) d f ( t) dt,, 注在变限积分 (1) 与 () 中, 不可再把积分变量写成的形式 ( 例如 ) 以免与积分上下限的 5 ( 一 ) 微积分学基本定理当函数的可积性问题告一段落, 并对定积分的性质有了足够的认识之后, 接着要来解决一个以前多次提到过的问题在定积分形式下证明连续函数必定存在原函数. 一变限积分与原函数的存在性设 f 在 [,] 上