平面图4-着色的两类新算法

摘要

平面图着色问题在图论和组合优化中具有重要地位,同时在很多其它领域具有广泛的应用。它的研究起源于著名的四色猜想(即至多用四种颜色给平面或球面上的地图着色,使相邻的区域着上不同的颜色)。虽然K.Appel,W.Haken和J.Koch在1976年借助计算机给出了四色猜想证明,但该证明仅仅给出了理论结果,对于具体平面图的实际4-着色问题并没有帮助。因此,平面图的着色算法,特别是正常4-着色算法,一直是图论研究的热点之一,然而该问题自身的复杂性决定此类算法的研究异常困难。本文首先介绍了平面图着色理论的发展和相关成果,接着深入探讨了乌力吉教授提出的4-着色布尔方程组的性质,然后给出了两种极大平面图4-着色算法:1.在第三章中,我们给出了求极大平面图4-着色全部解算法。该算法与以往算法相比较,具有两大优势:其一,得到一个极大平面图正常4-着色的全部解;其二,由于算法没有试探步骤,避免了无谓计算,提高了算法效率。虽然该算法得到了任意平面图的全部正常4-着色方案,但它的计算量在理论上是边数的指数函数。2.在第四章中,为了克服上述缺点,我们给出了快速求极大平面图一个正常4-着色的加权算法,利用它可以迅速求得极大平面图的一个正常4-着色。该算法的复杂度是边数的线性函数。

目录

摘要

Abstract

第一章 绪论

1 基本背景

2 基本概念

3 平面图与极大平面图

4 染色及其相关成果

5 本文的主要工作

第二章 极大平面图4-着色布尔方程组

1 极大平面图4-着色的布尔方程组的引入

2 极大平面图4-着色的布尔方程组的性质

第三章 求极大平面图4-着色全部解算法

1 算法思想和原理

2 算例和复杂度分析

第四章 求极大平面图4-着色部分解的加权算法

1 算法思想和原理

2 算例和复杂度分析

总结与展望

参考文献

致谢

附录