- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
（4）转到（2），直到所有顶点都着色为止 （2）标顶点vi (i=1,2,…,n)的颜色集Ci的第一种颜色ck
c2 v2 v3
v4
v1 c1
C1={c1}
v7
C2={c2}
C3={c2,c3}
C4={c1,c2,c3,c4}
v6
C5={c2,c3,c4,c5}
C6={c2,c3,c4,c5,c6}
2020/3/7
平面图的面着色
2020/3/7
面着色的定义
2020/3/7
面着色猜想
2020/3/7
面着色的性质
面着色可以转化为点着色来完成
【定理】地图G是k-面可色的，当且仅当它 的对偶图G*是k-可色图。 【定理】若图G是一个简单平面图，则该图 中至少存在一个度数小于或等于5的结点。
例题
2020/3/7
例题
2020/3/7
例题
【解】（1）该问题可用如图所示二分图G的边着色方法 求解。一节课的时段对应边的一个着色组。由于G是二分 图，故边色数是G的最大度35，即最少总课时时段为35节 。故平均每天要安排7节课。 （2）若每天安排8节课，则由G的总边数240知需要 240/40=6间教室。
例题
2020/3/7
例题
【例】证明图（a）所示的图G不是平面图。
2020/3/7
平面图与着色问题
平面图的概念与性质 ☺ 平面图的对偶图 着色问题与算法
2020/3/7
计算机应用技术研究所
33
对偶图的概念
2020/3/7
例题
2020/3/7
对偶图的性质
2020/3/7
四色猜想：连通简单平面图的色数不超过4。
2020/3/7
结点着色算法
2020/3/7
例题
对下图顶点进行着色。
v1 v2
v7
v3
v4
v6
v5
例题
（1）对i=1,2,…,n,作Ci={c1,c2,…,ci}；
v1
v2 v3
v4
v7
v6 v5
C1={c1} C2={c1,c2} C3={c1,c2,c3} C4={c1,c2,c3,c4} C5={c1,c2,c3,c4,c5} C6={c1,c2,c3,c4,c5,c6} C7={c1,c2,c3,c4,c5,c6,c7}
v5
C7={c2,c3,c4,c5,c6,c7}
（3）对顶点vi的所有邻接点vj( j>i)，作Cj= Cj-{ck}；
c2 v2 v3
v4
v1 c1
C1={c1}
C2={c2}
v7
C3={c23,}c3}
C4={c1,c2,c3,c4}
C5={c2,c3,c4,c5}
结点着色
2020/3/7
例题
2020/3/7
例题
2020/3/7
例题
2020/3/7
点色数的性质
2020/3/7
布鲁克斯定理
2020/3/7
例题
2020/3/7
例题
2020/3/7
边着色
2020/3/7
维津定理
2020/3/7
例题
2020/3/7
欧拉公式
2020/3/7
定理
2020/3/7
定理
2020/3/7
非平面图的判定
2020/3/7
例题
2020/3/7
定理
2020/3/7
例题
2020/3/7
定义
2020/3/7
例题
2020/3/7
定义
2020/3/7
库拉托夫斯基定理
2020/3/7
平面图与着色问题
2020/3/7
计算机应用技术研究所
4
平面图与着色问题
☺ 平面图的概念与性质 平面图的对偶图 着色问题与算法
2020/3/7
计算机应用技术研究所
5
应用实例
2020/3/7
交叉点与交叉边
2020/3/7
可平面图
2020/3/7
平面图的定义
2020/3/7
非平面图
2020/3/7
最大平面图
2020/3/7
面与边界思想
2020/3/7
面与边界的定义
2020/3/7
对面理解
2020/3/7
例题
2020/3/7
一点说明
2020/3/7
次数与边的关系
2020/3/7
欧拉公式
2020/3/7
欧拉公式
2020/3/7
离散数学
Discrete Mathematics
汪荣贵 教授
合肥工业大学计算机与信息学院
20210/3/7
计算机应用技术研究所
1
第10章 特殊图模型与算法
(下)
2020/3/7
计算机应用技术研究所
2
本章学习内容
3 平面图与着色问题 4 网络流图及其优化问题 5 特殊图模型的应用
2020/3/7
例题
Hale Waihona Puke （2）标顶点vi (i=1,2,…,n)的颜色集Ci的第一种颜色ck；
v2 v3
v4
v1 c1 v7
v6 v5
C1={c1} C2={c1,c2} C3={c1,c2,c3} C4={c1,c2,c3,c4} C5={c1,c2,c3,c4,c5} C6={c1,c2,c3,c4,c5,c6} C7={c1,c2,c3,c4,c5,c6,c7}
对偶图的定理
2020/3/7
平面图与着色问题
平面图的概念与性质 平面图的对偶图 ☺着色问题与算法
2020/3/7
计算机应用技术研究所
38
四色猜想
2020/3/7
应用实例
【解】可用一个无向图模型表示 上述问题，图的每个结点分别代 表一种食物，如果两种食物不能 放在一起，则在这两种食物之间 画一条无向边。
2020/3/7
应用实例
可通过对该图的结进行着色的方法实现对上述问题的求 解。具体地说，就是对图中每个结点分别涂上或者标注 一种颜色，并满足相邻的结点之间具有不同的颜色，将 相同颜色结点所代表的食物放在同一个隔间，则所需要 的最少颜色数目显然就是所求的冰箱隔间数目。 一种着色方案：
2020/3/7
（3）对顶点vi的所有邻接点vj( j>i)，作Cj= Cj-{ck}；
v2 v3
v4
v1 c1 v7
v6 v5
C1={c1}
CC22=={{cc12,c} 2} CC33=={{cc12,c, 2c,3c}3} C4={c1,c2,c3,c4}
CC55=={{cc12,,cc23,,cc34,,cc45,}c5} CC66=={{cc12,,cc23,,cc34,,cc45,,cc56,}c6} CC77=={{cc12,,cc23,,cc34,,cc45,,cc56,,cc67,}c7}
