线、页和图的着色

本书是国家自然科学基金“基于工程联接知识的装配序列规划(51175200)”的研究成果总结，主要讨论平面图着色问题：将平面图转化成线图，使平面图的着色问题转化成两个页面树上对应节点之间的着色问题，*后线图只需四种颜色就可完成着色。

本书通过对图论及平面图着色方面的研究，提出了线的概念，在线的基础上提出了页的概念，然后利用线和页所构成的线图对平面图的着色问题特别是四色着色问题进行研究。 全书共包括13章。第1章简要介绍图的基本概念。第2章提出了线的定义。第3章介绍了几种常用图的线表示。第4章讨论了图的平面映射和嵌入。第5章介绍了线图的基本构建方法，主要介绍了极大平面线图的构建方法。第6章分析了线图的特征。第7章提出了页和册的概念。第8章讨论平面图的人工着色。第9章描述了极大平面线图的着色过程。第10章介绍了极大平面线图的着色结构及其特征，主要介绍涉及着色的一些术语和着色结构。第11章至第13章均介绍了极大平面线图的着色方法，其中第11章介绍了直接着色方法，给出了六色定理的证明，而第12章讨论了原色调整着色方法，第13章讨论了可用色着色方法，给出了四色定理的两种不同的证明。 本书可供高等院校的本科生、研究生及研究人员阅读，也可供对四色着色问题有兴趣的人员阅读。

1998年在华中理工大学机械科学与工程学院获工学博士学位1988年在上海交通大学船舶动力工程系获工学硕士学位1985年在上海交通大学船舶动力工程系获工学学士学位开发了华中科技大学CAD中心暨天喻软件公司三维设计系统InteSolid中装配模型系统。开发了面向问题分析与决策专家系统软件系统及在公路工程和水运工程的2个应用系统。

第1章 图
1.1 图的基本概念
1.2 图的图形
1.3 图的一些基本术语
1.4 树
1.5 平面图
1.6 哈密顿图
1.7 本章小结
第2章 线
2.1 线的定义
2.2 实线和虚线
2.3 本章小结
第3章 几种常用图的线表示
3.1 线图的构成
3.2 接近图的线表示
3.3 哈密顿图的线表示
3.4 本章小结
第4章 图的平面映射和嵌入
4.1 图的平面嵌入方法
4.2 单圈的平面性
4.3 面块点
4.4 两个圈之间的关系
4.5 平面图的判断
4.6 本章小结
第5章 线图构建方法
5.1 线图的构建
5.2 平面图的线表示
5.3 极大平面图的线表示
5.4 本章小结
第6章 线图的特征
6.1 线图的形成
6.2 单线图和复合线图
6.3 附着点
6.4 TL算法的问题和修正
6.5 包容性
6.6 相似性
6.7 隔离性
6.8 平面性
6.9 中心性
6.10 完整性
6.11 线图的语义
6.12 本章小结
第7章 页和册
7.1 页和册的定义
7.2 极大平面线图和极大页面线图
7.3 线图的册表示
7.4 第*页和第二页
7.5 极大平面线图中的跨弧
7.6 图的分页
7.7 页面树
7.8 主册和分册
7.9 本章小结
第8章 典型平面图的人工着色
8.1 着色对象的选择
8.2 正多面体及人工着色
8.3 经典算例
8.4 逐页着色
8.5 Heawood反例图的人工着色
8.6 人工着色分析
8.7 本章小结
第9章 极大平面线图的着色
9.1 着色流程
9.2 第*页和第二页的着色
9.3 第三页的着色过程
9.4 第四页的着色过程
9.5 着色三角形
9.6 分册的着色过程
9.7 极大平面图和平面图的色数
9.8 本章小结
第10章 极大平面线图的着色结构及其特征
10.1 着色基本术语
10.2 主要节点类型
10.3 着色特性
10.4 着色结构
10.5 包容体
10.6 本章小结
第11章 直接着色方法
11.1 基本方法
11.2 原色冲突的产生及特征
11.3 第四页的原色冲突
11.4 第三页的新增色
11.5 第三页对第四页的反作用
11.6 本章小结
第12章 原色调整着色方法
12.1 原色调整的基本方法
12.2 原色冲突节点和第三页结构关系
12.3 整体原色调整的特征
12.4 原色冲突跨弧三角形的原色调整
12.5 一般原色冲突跨弧的原色调整
12.6 四面体和类四面体法则
12.7 局部原色调整
12.8 包容体的分割
12.9 新增色点的作用
12.10 包容体的调色
12.11 着色算法
12.12 原色调整着色定理
12.13 本章小结
第13章 可用色着色方法
13.1 可用色和相邻色
13.2 无解的判断和基本消除方法
13.3 解和无解的形成
13.4 单个无解三角形的消除
13.5 无解三角形的相连
13.6 相连无解三角形的消除
13.7 当前着色点的位置影响
13.8 无解三角形消除定理
13.9 回溯爆炸的原因
13.10 可用色着色算法
13.11 可用色着色定理
13.12 本章小结
参考文献