论文部分内容阅读
图论是数学的一个重要分支,它为离散数学证明技巧的探索提供了极其丰富的背景,并且它的许多结果在计算科学、社会科学以及自然科学等方面有着广泛的应用。作为图论研究的一个重要领域,图的着色问题(即着色问题)也就成为了我们研究的一个目标,它起源于著名的四色问题。图的着色理论不仅在组合分析和离散数学等数学问题的研究上有应用,而且在其他领域也有非常重要的应用,比如为了避免冲突合理安排考试及会议的日程问题,避免化学药品相互反应的安全存储问题等。图的着色问题的研究有着极其重要的意义。 本文主要研究的是图的2-距离着色问题。它是建立在图的正常的顶点着色的基础之上的一种着色。本文具体内容可分为以下四部分: 第一部分(即第一章)介绍了图论及其着色问题的起源发展及研究意义,并给出了本文所研究的内容及目的。 第二部分(即第二章)主要给出了图的着色问题中的一些基本概念,并着重介绍了图的L(p, q)标号问题和2-距离着色的概念,并对它们的研究现状进行了总结概括。 第三部分(即第三、四章)本章是论文最重要的部分。在这一部分,重点探讨了平面图的2-距离着色问题及若干特殊图的2-距离着色。第三章给出了某些非Hamilton图的2-距离着色,通过对这些具体图的着色规律的分析,发现可以通过调换某些顶点颜色的着色方法将图的部分着色进行延拓。第四章,结合图的2-距离着色的特点,先给出了最小反例图所满足的结构,然后适当变形欧拉公式,再利用设计好的权值分配规则给出了平面图是(D+2)-2-距离着色的一个充分条件。 第四部分(即第五章)总结了文章研究的主要工作及结论,指明了文章的创新之处及后续可以展开的研究工作。