【计算机论文全套栏目提醒】:网学会员在计算机论文全套频道为大家收集整理了“C_,m_□C_,n_和P_,m_□C_,n_的均匀全着色 - 硕士论文“提供大家参考,希望对大家有所帮助!
大连理工大学 硕士学位论文Cltmgt□Cltngt和Pltmgt□Cltngt的均匀全着色 姓名:李智赫 申请学位级别:硕士 专业:计算机软件与理论 指导教师:林晓惠 20081201 大连理工大学硕十学位论文 摘 要 图着色问题是图论的重要研究内容之一,也是一个NP困难问题,并在组合优化等方面有广泛的应用。
经典的图着色问题只对顶点或边着色,随着在实际问题中的应用又出现了新的着色问题,全着色就是其中之一。
在这一研究领域,1965年Behzad提出了著名的全着色猜想(TCC):对于简单图G,其全着色数z。
(G)与最大度△(G)之间的关系为,z’(G)≤A(G)+2。
现已知对一些特殊的图类,如圈,完全图,完全二部图,外平面图,最大度不为6,7,8的平面图等猜想成立。
均匀全着色是全着色的一种特殊情况,在满足图G可以k全着色的基础上,还要求每种不同颜色所染的顶点和边的个数相差不超过l的最小整数k称为G的均匀全着色数。
1994年,Hung.1in Fu最早给出了图的均匀全着色和均匀全色数的概念,他猜想任意图G当后≥max{A”。
(G),△(G)+2}时可以后等全着色,Fu自己证明了此猜想对树,完全图,完全二部图等成立。
Wang提出了关于均匀全着色的另一个猜想,对于图G,有 Z(G)≤△(G)+2。
并证明了最大度小于等于3的多重图都可以5等全着色。
C卅口e是两个长度分别为m和rl的圈的笛卡尔积图(或称交图),对于这类图的全着色前人已做过大量的研究。
1997年,Seoud等人证明了当所≥3,Y/为奇数或者3的倍数时z。
(巳oc.)=A+I.Kemnitz和Marangio在2003年改进了这个结果,证明当m≥3,刀为5的倍数时也满足z。
(c卅oc.)=△+l。
本文用计算机算法与数学分析相结合的方法对图C卅口e的均匀着色进行了研究。
通过不断改进搜索图巴口C。
的5均匀全着方案的算法的效率,尽可能多的计算出朋和刀足够大时结果,从中归纳出了一套对任意m≥3,r/≥3都成立着色方案。
由此证明对任意整数m≥3,r/≥3图C卅oc的均匀全着色数为5。
.同时还对路径与圈的交图巴Kitn的均匀全着色进行了研究,证明了当所≥3,r/≥3时只pc的均匀全着色数也是5。
.关键词:笛卡尔积;全着色;均匀全着色 大连理工大学硕士学位论文 Equitable Total Coloring of G口G and PmDCn Abstract Graph coloring problem is a main research area of graph theory,and is wildly applied incombinational optimization.It is proved that graph coloring is NP-eomplete.To the classicalgraph coloring,only the vertexes and edges are considered.With the development ofapplication,new types of graph coloring problem are proposed.Total coloring is an importantone of them.In 1 965,Behzad showed the total coloring conjecture(TCC):For every simplegraph G,z。
(G)≤△(G)+2 where Z。
(G)is the total chromatic number and△(G) is themaximum degree of G.Conjecture TCC is proved to be true only for some special classes ofgraph,such