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