有关图的染色问题的研究

《有关图的染色问题的研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、校级科研计划结题报告项目名称：有关图的染色问题的研究指导老师：王萃琦参与成员：田静信息与计算科学06-1陈广军信息与计算科学07李晨曦数学与应用数学07-4谷红平数学与应用数学07-2王琪应用物理07-1（一）序言：1.问题的提出：图的染色问题起源于著名的“四色猜想”问题。早在一百多年前的1852年，英国格色里提出了用四种颜色就可对任意一张地图进行染色的猜想。即对世界地图或任何一个国家的行政区域地图，最多用四种颜色就可对其染色，使得凡是相邻的国家或相邻的区域都着以不同的颜色。2．研究与发展：“四色猜想”提出后，一些数学家着手研究这个猜想，

2、力图给出证明。时隔二十七年后，1897年肯普给出了“四色猜想”的第一个证明，又过了十一年，1890年希伍德发现肯普的证明是错误的。但他指出，肯普德证明方法虽然不能证明地图染色用四种颜色足够，却可以证明用五种颜色就够了。此后,“四色猜想”一直成为数学家们感兴趣而未能解决的世界数学难题。（二）研究目标：对关于图的染色问题进行全面系统的研究。（三）研究方法：主要以阅读相关书籍和论文为主。（四）研究的主要内容：图的染色问题（五）研究成果：1.图的染色问题介绍及其背景图论发展到现在已有许多分支，着色理论是其中之一，且有着极其重要的地位。它起源于15

3、0年前的“四色猜想”，即在一个平面或球面上的任何地图都能够只用四种颜色着色，使得每个国家用一种颜色，且没有两个相邻的国家有相同的颜色。1976年K.Apple和w.Haken在J.Koch的协助下用计算机检验了“四色猜想”是正确的，从而“四色猜想”被“四色定理”所代替，在1997年，N.Robertson等又给出了一个简化的计算机证明。尽管迄今为止仍没有得到非计算机的理论性证明，但人们在冲击“四色猜想”的过程中所创造的新的思想、方法和技巧为图论宝库增添了一个又一个精彩结果。图着色理论的意义远不止如此。众所周知，生活及科学领域中许多问题的数

4、学模型都可以图的形式来建立，然后对图中某些对象按照一定规则进行分类，而所谓着色只是对其中分类方法的一种简单而直观的表达方式。所以着色问题是解决诸如时间表问题、排序问题、排课表问题、交通状态、运输安排、电路设计和贮藏问题等涉及任务分配的实际问题的基本方法。再者，图着色理论在离散数学领域有着非常重要的地位，其中许多貌似无关的问题都可以转化为图着色问题。例如，极图理论中的Erdos和Simonovits定理:给定图G，不包含子图G的具有n个顶点的图的边的最大数fnG(,)的性态取fnG(,)()2G决于G的色数():limG。因此，TR

5、.Jense。和B.Toft断言:2nG2()2图着色理论在离散数学中处于中心地位。近年来，关于图着色文体的研究得到了许多有趣而实用的结果，同时又拓展出一些新的着色分支，比如，除了经典的点着色、边着色之外，(点边)全着色、列表着色(可选择性)、强边着色(有两种不同的着色使用了这一名词)、邻强边着色、关联着色、圈着色、无圈着色、距离面着色、区间着色、子着色、(平面图)边面着色、点边面完备着色及动态着色等，已成为现在图着色领域新的热点。许多新的着色是一些过去未解决的问题转化而来，使原问题变得更加简单易懂，便于研究。研究范围的拓宽给着色领域

6、增加了许多尚未解决的问题。由此可见，图着色理论有着旺盛的生命力和广阔的发展前景。2.关于边染色问题图的染色理论是图论中的一个重要分支。图的染色种类有很多，诸如边染色、点染色、面染色和全染色等。其中研究最多，结果也较完善的就是图的边染色。而其中关于正常边染色的图的分类问题一直是研究的热点。图的正常的边染色就是把图的边集分解为一些互不相交的边的独立集的并的方法。2.1基本理论定义1：对图G的边进行着色，且相邻的边没有相同的颜色，称为图G的一个边着色。一个n边着色是用n种颜色的一个着色。定义2：使图G的n边着色最小的n，称为图n的边色数，记

7、作'G。考虑图G的边色数与度的关系，由于与任何一个顶点关联的边都必须着以不同的颜色，所以对任意图G的边色数有'G，其中指图G的最大度。1964年，苏联数学家V.G.Vizing给出了关于图边染色的一个突破性结论，他指出了简单图G的边色数与度之间的关系。Vizing定理：任意(简单，无向)图G的边着色数(edgechromaticnumber)'G有：'1G。2.2分类定理定义3：由Vizing定理可知'G或'1G。若'G，称图12G为第一类，记作GC；否则'1G

8、，称图G为第二类，记作GC。在将近半个世纪的漫长岁月里，人们一直在为解决简单图的分类问题做着不懈的努力。解决一般图的分类问题相当困难，因此人们关心平面图等特殊图的分类问题。对于简单平