论文部分内容阅读
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。
二十世纪六十年代以来,图论在科学界突军异起,活跃非凡。图论中有很多著名的问题,如哈密顿问题,四色问题,中国邮递员问题等。并且,应用图论来解决化学,计算机科学,生物学等学科问题已显出极大的优越性。图论作为离散数学的一个重要分支,受到了各方面的普遍重视。
均匀染色问题作为图论里的一个重要问题,对于它的研究有着深远的意义。令G表示一个简单图。图的均匀染色,就是指正常染色中任意两个色类中的元素个数最多相差一个。这里主要考虑简单的非空有限图,这些图不包含环以及重边。
本文研究了图论中有关均匀染色的若干问题,具体地,我们从树的均匀染色入手,通过在树上加边的方式形成各种带圈的图,从而将简单图做了系统的归类,然后研究这几类加圈图的相关性质及其均匀染色数k的范围。上述问题可以概括如下:任意一个简单图G,其均匀染色数为k,为了方便确定k的范围,我们将G进行分类,按各类别的性质去确定其具体k的范围,达到更科学、更精确的目的。
全文共分为五章。
第一章,我们给出了一个简短而又相对完整的引言。首先,我们介绍了均匀染色的理论知识。然后,我们给出了一些基本的术语和定义。最后,我们列出本文的主要结果。
在第二章里,针对连通的简单图,我们先从简单一些的图类入手,这里是以树入手,巧妙借助已经存在的若干定理,来研究这类图的均匀染色数k。
在第三章里,我们对剩下的连通含圈简单图进行研究,将其分类细化,设计相关算法,寻求其均匀染色数七的范围。具体分成以下三大类:
第一类,图G里不存在奇圈。在这一类情况里,我们将图G看成二分图G(X,Y),然后按照二分图的性质来研究其均匀染色色数的范围。
第二类,图G中不存在偶圈。对于此类情况,我们不难得出其任意两个圈都不相交的结论。这样便大大简化了我们确定均匀染色色数的难度。而另外关键的一步是将此大类按照这样一个规则划成两小类,即,图G中是否存在满足||X|-|Y||≥2条件的子树Ti(X,Y)。如果不存在该条件的子树,则图G是3-均匀可染色的。反之,如果图G中存在满足条件的子树Ti(X,Y)时,我们便采用二分搜索方法来锁定均匀染色色数的范围。这里七是介于3和ki之间的数。在本部分,我们构造了相关例子来演示该方法。
第三类,图G中既存在奇圈,又存在偶圈。这里又可以分两种情况来讨论。分类标准是,图G里的圈是否相交。如果严格不存在相交的情况,便可以运用前面提到的第二类方法来解决此类问题;然而,如果存在相交的情况——这种情况相对来说比较复杂,我们便对其进行树分解,找到图G的树宽w,即w-退化的,借助树宽,可以确定该图G的均匀染色色数k的范围。
在第四章里,主要研究那些非连通简单含圈图的均匀染色数k。本文先从森林入手,将此类图划分为两类,即森林F和其他类别的图G,然后研究这两类图的均匀染色数k的范围。
最后,在第五章里,我们做了一些总结和相应的一些推广。