极大平面图略型着色的计算机辅助研究

论文摘要

本文描述了一批例图的四着色情况。在许寿椿教授的编写的两个程序(程序getSome4colors和getTfc)的基础上,给出了加强搜索的方法,进一步增加批量着色的数量。在此批量着色的基础上,程序getTfc能找到更多的更难以发现的点数较少的四着色树,并使所得四着色总数更接近全部着色数。然而,对于图库中大多数图来说,getTfc程序则不能找出全部着色。因此,需要加强搜索法作为补充,使我们得到的四着色数更多。 1999年,许寿椿教授用图的四着色解成功求出图的自同构群。此种方法先要求出图的全部四着色解,再从中选出一类四着色解(如路路型着色),最终求出图的自同构群。而求图的全部四着色解的算法是指数级的,对于图g37a耗时近4个半小时,那么对于100个点以上的图计算机将无能为力。本文对图库中点数少的图通过上述方法求得图的四着色解进行分类,筛选出四着色解中最简单的一类即路路型着色进行处理。并发现得到的所有路路型着色总共可分为三类,作者记此三类为pp1型、pp2型和pp3型。其中pp1型路路分解最适宜计算机计算查找。作者给出了避开求全部解而直接寻找pp1型路路分解的方法即“取点法”,其算法复杂性是多项式级的。对于一百多个点的图也能顺利求解。本文以例图g102为例介绍“取点法”。 本文还介绍了极大平面图的导出四正则图,给出了极大平面图的导出四正则图的两种构造方式、等价性及性质,证明了导出四正则图的三着色与原极大平面图四着色的一一对应关系,并且找出了导出四正则图的三种颜色与原极大平面图四着色的三组对偶二色子图之间的关系.还用导出四正则图的三着色与原极大平面图四着色的一一对应关系编写程序求图的ppl型路路分解即“取边法”.关键词极大平面图,四着色算法,对偶二色子图,路路分解,自同构群

论文目录

• 第一章 前言
• 第二章 相关术语及符号
• 第三章 工具与方法
• 第四章 对本文处理图库的说明
• 第五章 对许寿椿教授的程序的改进
• 第六章 求图库中图的四着色并对路型着色进行分类
• 第七章 直接寻找路型着色的取点法
• 第八章 极大平面图的导出四正则图的三着色
• 第一节 两种导出方式及其等价性
• 第二节 导出四正则图的若干性质
• 第三节 导出四正则图的三着色
• 第九章 直接寻找路型着色的取边法
• 第十章 结语
• 参考文献
• 附录一
• 附录二
• 附录三