图的染色问题

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

1、图的染色问题应锡娜06990213@zjnu.net（浙江师范大学初阳学院，浙江金华321004）摘要：木文介绍了图染色问题的提出、应用及意义，主要对已取得的研究成杲及当今的研究状况进行了阐述。关键词：图；染色；色数一、引言图染色问题起源于著名的“四色猜想”[1]问题。早在一百多年前的1852年,英国Guthrie提出了用四种颜色就可对任意一张地图进行染色的猜想。即对世界地图或任何一个国家的行政区域地图，最多用四种颜色就可以对其染色，使得凡是相邻的国家或相邻的区域都着以不同的颜色。二、研究与发展“四色猜想”提出后，一些数学家着手研究这个猜想，力图给出证明。吋隔二十七年后，187

2、9年Kempe给出了“四色猜想”的第一个证明，又过了十一年,1980年Hewood发现Kempe的证明是错误的。但他指出,Kempe的证明方法虽然不能证明“四色猜想”，却可以证明用五种颜色就够了。此后，“四色猜想”一直成为数学家们感兴趣而未能解决的世界数学难题。直到1976年6刀美国数学家伊利诺斯大学教授Appel与Haken宣布：他们用计算机证明了“四色猜想”是正确的。因此，从1976年以后，就把“四色猜想”改称为“四色定理”了。⑵值得指出的是，Appel与Haken的证明，计算机运行了1200个小时。诚然用计算机证明数学难题实在是一个伟大的尝试或创举，但是，世界数学家们仍期

3、待着用常规的数学方法证明“四色定理”。目前仍有许多数学家在潜心研究，寻求常规的证明方法。地图的特点在于，多个区域位于同一平面上，每个区域可以是毫无规则的各种形状，任意两个区域可以有公共边界，但不能有公共区域。于是人们开始研究所谓“平而图”。人们把地图中的每一个区域称为一个“而”,地图染色就是对“而”染色。进一步研究之后人们把地图中的每个区域的“面”视为一个点，若两个“面”相邻接，即地图屮的两个区域有一段或几段公共边界，则在表示这两个区域的点之间连线，该连线可以是直线也可以是任意形状的曲线，并称之为边。如此，就可以把一张地图改画为一个平面上的图，人们把该图称为地图的对偶图。其特点

4、是：所有的点及边均处在同一平而上，并但任意两条边除端点外可以不交叉，人们称这样的图为平面图。例如图1的对偶图如图2所示。图1若我们对图2屮的点染色，凡是相互邻接的点染以不同的颜色，则对图2的点染色等价于对图1的而染色。显然，任意一张地图的对偶图均是一个平而图,或者说地图就是平面图。另外，值得指出的是，并非一切图均是一个平面图，即处于同一平面上的有些图存在着边交叉的情况。如图3所示的图，图屮有4个点6条边处于同一平面上，其中边％=伉宀）与边乞=（人宀）存在着交叉点，但是,图3可以改画为图4,而图4中不存在交叉边，即图4为平面图。图3图4人们把可以改画为平面图的图称为可嵌入平面图或

5、简称为可平面图，即图3是可平面图。而有的图，如图5所示，图中有5个点10条处于同一平面中，边勺与边％及匕交叉且边如与边勺及勺交叉，但无论怎样改画图5均不能避免边的交叉，人们称这样的图为非平面图。图51965年，BehzadM在他的I■専士论文中首次提出并研究了图全染色问题，提出了著名的“全染色猜想”[4]。所谓图全染色的问题，是指对一个图屮的点、边、面全染色，并11使得凡相接或相关联的元索均染以不同的颜色。如图6所示图，-其屮5个点为弘宀，…宀，7条边为勺,S4个面是/1,/2,/3,/4o对图6全染色时，点片与「2相邻接，故必须染以不同的色，边勺与勺相邻接也必须染上不同色，面

6、f占扎相邻接不能染以相同色。并且，点儿与边勺相关联也得染不同色，而边勺与而久相关联也须染上不同的颜色。很显然，图6屮共冇16个元素，只要用16种颜色即可对其全染色，问题是所用颜色数能否减少？最少需要多少种颜色即可对其全染色，而这个最少的颜色数，人们称之为图的全色数[3]oBehzadM的全染色猜想为：对于简单连通图G冇A（G）+l

7、最多用6利

8、颜色就够了。v1e5v2f2e3e6e7v5f3e4f4v6图6而图边染色可追溯到1880年，那吋，Tait试图证明“四色猜想”，但从1881年到1963年没有■多大的进展，1964年Vizing证明了每一个最大度为△的图G至多用A+1种颜色就可给边染色。这是边染色问题的一个惊人的突破。这一结论推广了Johnson的一个较早时候的称述：用四种颜色就能给立方图进行边染色。迄今，数学家们己经证明了对树、圈、完全图、完全多部图及外平面图等特殊图，“全染色猜想”是正确的，还证明了对A（G