阅读量：

185

作者：

陶然

展开

摘要：

四色问题是图论研究领域中的核心问题,四色定理的证明就意味着所有与四色定理等价的命题如考夫曼叉积猜想,马季亚谢维奇建立的丢番图方程解的存在性猜想等都同时得到了证明.四色定理的证明不仅可以证明出现在图论以外其它领域的等价命题,而且可以解释这些领域中与图论同构的思想体系.因此论文的研究具有一定的理论价值. 论文首先介绍了四色问题的性质,分析了四色问题证明的几种不同思路以及各种证明方法的优点和不足,指出了四色问题与四着色算法之间的内在联系. 其次,研究了顶点着色理论以及基于顶点着色理论的四着色算法.介绍了肯普的四着色理论,分析了基于肯普理论的肯普-凯特尔算法的优点以及存在的不足,并给出了改进后的新的四着色算法,同时给出了一个实例分析,证明了新的四着色算法不仅对于不存在不可变肯普链缠结的情形有效,而且对某些存在不可变肯普链缠结的情形同样有效. 再次,研究了边着色理论以及基于边着色理论的四着色算法.分析了泰特的边着色理论及其缺陷,探讨了将肯普理论与泰特理论结合起来证明边着色定理的思路,从不局限于平面性的二部图角度运用匹配思想对四色定理提供了一个新的证明,并且据此构建了一个边着色的新四着色算法.最后,讨论了四着色算法在实际应用中的价值并结合四着色理论发展的一些前沿问题对四着色理论未来的发展的空间作出了一个展望.

展开

关键词：

图论 四色问题 四着色算法 顶点着色理论

学位级别：

硕士

学位年度：

2010

DOI：

10.7666/d.D620901