《均匀染色的新途径》由会员分享，可在线阅读，更多相关《均匀染色的新途径（54页珍藏版）》请在金锄头文库上搜索。
1、。一 董。? 厂焉 、 番 弩 作者 盗窒量 专 业一选羟! 茎垒亟塑陋 导师 垒! 蜜至丞盘 合作导师 o 。I1 年；月6 日 Lr， ，| 一l L S e e i n gt h ee q u i t a b l e c o l o r i n g si nad i f f e r e n tv i e w Z H A N GW e n y u ( A d v i s o r ：P r o f L iG u o - j u n ) S c h o o lo fm a t h e m a t i c s S h a n d o n gU n i v e r s i t y J i n a
2、n2 5 01 0 0 ，P R C h i n a -厂 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：递垒量l - 日期： 泣呼叫日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容
3、编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：涯童互导师签 f 一 目录 中文摘要I 英文摘要 符号说明V 第一章简介1 1 1 图论、均匀染色的相关背景1 1 2 基本的概念和定义3 1 3 主要结论6 第二章不带圈的连通简单图G 的均匀染色1 1 第三章带圈的连通简单图G 的均匀染色1 7 3 1 图G 里不存在奇圈1 7 3 2 图G 中不存在偶圈1 8 3 3 图G 中既存在奇圈，又存在偶圈2 3 第四章非连通的简单带圈图G 的均匀染色2 7 4 1 森林的均匀染色2 7 4 2 其他情况2 8
4、第五章总结3 1 参考文献3 3 致谢3 5 个人简介3 7 C h i n e s e A b s t r a c t I E n g l i s h A b s t r a c t N o r a t i o n 1 I ， C h a p t e r1I n t r o d u c t i o na n dM a i nR e s u l t s 1 】【】【I n t r o d u c t i o n 1 1 2B a s i cc o n c e p t sa n dd e f i n i t i o n s 3 1 3O u t l i n et h em a i nr e s
5、u l t s 6 C h a p t e r2E q u i t a b l ec o l o r i n go nt h es i m p l e ，c o n n e c t e dg r a p hw i t h o u t c i r c l e s 1 1 C h a p t e r3E q u i t a b l ec o l o r i n go nt h es i m p l e ，c o n n e c t e dg r a p hw i t h S O m e c i r c l e s 1 7 3 1T h e r ea r en oo d dc y c l e s 1
6、 7 3 2T h e r ea r en oe v e nc y c l e s 1 8 3 3T h e r ea r es o m eo d d c y c l e so re v e nc y c l e s 2 3 C h a p t e r 4E q u i t a b l ec o l o r i n go nt h es i m p l e ，n o tc o n n e c t e dg r a p h 2 7 4 1E q u i t a b l ec o l o r i n go nf o r e s t s 2 7 4 2E l s e ：1 8 C h a p t e
7、 r 5 C o n c l u s i o n s ：；1 R e f e r e n c e s ：；：； A c k n o w l e d g e m e n t s 。3 5 u l u mV i t a e 3 7 山东大学硕士学位论文 均匀染色的新途径 张文昱 山东大学数学学院 运筹学与控制论 山东济南2 5 0 1 0 0 摘要 图论( G r a p h T h e o r y ) 是数学的一个分支。它以图为研究对象。图论中的图 是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事 物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具 有这
8、种关系。 二十世纪六十年代以来，图论在科学界突军异起，活跃非凡。图论中有很多 著名的问题，如哈密顿问题，四色问题，中国邮递员问题等。并且，应用图论来 解决化学，计算机科学，生物学等学科问题已显出极大的优越性。图论作为离散 数学的一个重要分支，受到了各方面的普遍重视。 均匀染色问题作为图论里的一个重要问题，对于它的研究有着深远的意义。 令G 表示一个简单图。图的均匀染色，就是指正常染色中任意两个色类中的元 素个数最多相差一个。这里主要考虑简单的非空有限图，这些图不包含环以及重 边。 本文研究了图论中有关均匀染色的若干问题，具体地，我们从树的均匀染色 入手，通过在树上加边的方式形成各种带圈的图，从
9、而将简单图做了系统的归类， 然后研究这几类加圈图的相关性质及其均匀染色数k 的范围。上述问题可以概括 如下：任意一个简单图G ，其均匀染色数为k ，为了方便确定k 的范围，我们将 G 进行分类，按各类别的性质去确定其具体k 的范围，达到更科学、更精确的目 的。 全文共分为五章。 第一章，我们给出了一个简短而又相对完整的引言。首先，我们介绍了均匀 染色的理论知识。然后，我们给出了一些基本的术语和定义。最后，我们列出本 文的主要结果。 在第二章里，针对连通的简单图，我们先从简单一些的图类入手，这里是以 山东大学硕士学位论文 树入手，巧妙借助已经存在的若干定理，来研究这类图的均匀染色数k 。 在第三
10、章里，我们对剩下的连通含圈简单图进行研究，将其分类细化，设计 相关算法，寻求其均匀染色数k 的范围。具体分成以下三大类： 第一类，图G 里不存在奇圈。在这一类情况里，我们将图G 看成二分图 o ( x ，】，) ，然后按照二分图的性质来研究其均匀染色色数的范围。 第二类，图G 中不存在偶圈。对于此类情况，我们不难得出其任意两个圈 都不相交的结论。这样便大大简化了我们确定均匀染色色数的难度。而另外关键 的一步是将此大类按照这样一个规则划成两小类，即，图G 中是否存在满足 I N - y l l 2 条件的子树乃( x ，】，) 。如果不存在该条件的子树，则图G 是3 一均匀 可染色的。反之，如果
11、图G 中存在满足条件的子树互( X ，y ) 时，我们便采用二分 搜索方法来锁定均匀染色色数的范围。这里七是介于3 和毛之间的数。在本部分， 我们构造了相关例子来演示该方法。 第三类，图G 中既存在奇圈，又存在偶圈。这里又可以分两种情况来讨论。 分类标准是，图G 里的圈是否相交。如果严格不存在相交的情况，便可以运用 前面提到的第二类方法来解决此类问题；然而，如果存在相交的情况这种情 况相对来说比较复杂，我们便对其进行树分解，找到图G 的树宽w ，即w 退化 的，借助树宽，可以确定该图G 的均匀染色色数k 的范围。 在第四章里，主要研究那些非连通简单含圈图的均匀染色数k 。本文先从森 林入手，将
12、此类图划分为两类，即森林F 和其他类别的图G ，然后研究这两类 图的均匀染色数k 的范围。 最后，在第五章里，我们做了一些总结和相应的一些推广。 关键字：图：均匀染色；树；圈；二分搜索法；树分解 山东大学硕士学位论文 S e e i n gt h ee q u i t a b l ec o l o r i n g si na d i f f e r e n tv i e w Z H A N GW e n y u S c h o o lo fM a t h e m a t i c s ，S h a n d o n gU n i v e r s i t y O p e r a t i o n a lR e a s e a r c h J i n a n2 5 0 1 0 0 P R C h i n a A b s t r a c t G r a p hT h e o r yi sab r a n c ho fm a t h e m a t i c s T h e s eg r a p h sa r es t u d i e di ng r a p h t h e o
