图的染色问题.doc

图的染色问题应锡娜06990213（浙江师范大学 初阳学院，浙江 金华 321004）摘要：本文介绍了图染色问题的提出、应用及意义，主要对已取得的研究成果及当今的研究状况进行了阐述。关键词：图；染色；色数一、 引言图染色问题起源于著名的“四色猜想”1问题。早在一百多年前的1852年，英国Guthrie提出了用四种颜色就可对任意一张地图进行染色的猜想。即对世界地图或任何一个国家的行政区域地图，最多用四种颜色就可以对其染色，使得凡是相邻的国家或相邻的区域都着以不同的颜色。二、 研究与发展“四色猜想”提出后，一些数学家着手研究这个猜想，力图给出证明。时隔二十七年后，1879年Kempe给出了“四色猜想”的第一个证明，又过了十一年，1980年Hewood发现Kempe的证明是错误的。但他指出，Kempe的证明方法虽然不能证明“四色猜想”，却可以证明用五种颜色就够了。此后，“四色猜想”一直成为数学家们感兴趣而未能解决的世界数学难题。直到1976年6月美国数学家伊利诺斯大学教授Appel与Haken宣布：他们用计算机证明了“四色猜想”是正确的。因此，从1976年以后，就把“四色猜想”改称为“四色定理”了。2值得指出的是，Appel与Haken的证明，计算机运行了1200个小时。诚然用计算机证明数学难题实在是一个伟大的尝试或创举，但是，世界数学家们仍期待着用常规的数学方法证明“四色定理”。目前仍有许多数学家在潜心研究，寻求常规的证明方法。地图的特点在于，多个区域位于同一平面上，每个区域可以是毫无规则的各种形状，任意两个区域可以有公共边界，但不能有公共区域。于是人们开始研究所谓“平面图”。人们把地图中的每一个区域称为一个“面”，地图染色就是对“面”染色。进一步研究之后人们把地图中的每个区域的“面”视为一个点，若两个“面”相邻接，即地图中的两个区域有一段或几段公共边界，则在表示这两个区域的点之间连线，该连线可以是直线也可以是任意形状的曲线，并称之为边。如此，就可以把一张地图改画为一个平面上的图，人们把该图称为地图的对偶图。其特点是：所有的点及边均处在同一平面上，并且任意两条边除端点外可以不交叉，人们称这样的图为平面图。例如图1的对偶图如图2所示。图 1图 2若我们对图2中的点染色，凡是相互邻接的点染以不同的颜色，则对图2的点染色等价于对图1的面染色。显然，任意一张地图的对偶图均是一个平面图，或者说地图就是平面图。另外，值得指出的是，并非一切图均是一个平面图，即处于同一平面上的有些图存在着边交叉的情况。如图3所示的图，图中有4个点6条边处于同一平面上，其中边与边存在着交叉点，但是，图3可以改画为图4，而图4中不存在交叉边，即图4为平面图。 图3图4人们把可以改画为平面图的图称为可嵌入平面图或简称为可平面图，即图3是可平面图。而有的图，如图5所示，图中有5个点10条处于同一平面中，边与边及交叉且边与边及交叉，但无论怎样改画图5均不能避免边的交叉，人们称这样的图为非平面图。图51965年，Behzad M在他的博士论文中首次提出并研究了图全染色问题，提出了著名的“全染色猜想”4。所谓图全染色的问题，是指对一个图中的点、边、面全染色，并且使得凡相接或相关联的元素均染以不同的颜色。如图6所示图，其中5个点为，7条边为，4个面是。对图6全染色时，点与相邻接，故必须染以不同的色，边与相邻接也必须染上不同色，面与相邻接不能染以相同色。并且，点与边相关联也得染不同色，而边与面相关联也须染上不同的颜色。很显然，图6中共有16个元素，只要用16种颜色即可对其全染色，问题是所用颜色数能否减少？最少需要多少种颜色即可对其全染色，而这个最少的颜色数，人们称之为图的全色数3。Behzad M的全染色猜想为：对于简单连通图G有其中为图G的全色数，为图G的最大度。显然，是成立的，而至今尚未证明，这是图论界公认的又一个难题。根据“全染色猜想”，由图6的最大度为4，即图6中的点，得图6的全染色最多用6种颜色就够了。图6而图边染色可追溯到1880年，那时，Tait试图证明“四色猜想”，但从1881年到1963年没有多大的进展，1964年Vizing证明了每一个最大度为的图G至多用种颜色就可给边染色。这是边染色问题的一个惊人的突破。这一结论推广了Johnson的一个较早时候的称述：用四种颜色就能给立方图进行边染色。迄今，数学家们已经证明了对树、圈、完全图、完全多部图及外平面图等特殊图，“全染色猜想”是正确的，还证明了对和的图，“全染色猜想”也是成立的。三、 应用与意义研究图染色问题有什么应用价值及理论意义呢？若仅就地图染色而言，用四种色或更多一些颜色并无多大实用价值。然而，若将地图中的几个区域视为几种化学品，凡两个邻接的区域所代表的两种化学品有某种关系，例如该两种化学品若放在一起容易发生爆炸或引起变质等。现欲建造仓库来存放几种化学品，显然建造几个仓库分别存放这几种化学品是万无一失的。但建库费用大，怎样才能使建库数量最少，又能使这几种化学品的存放万无一失呢？显然，两两均无任何危险关系的几种化学品可存放于同一仓库中，即只要建造一个仓库就够了。可见，这一建库问题就转化为图点染色问题了，所以研究图染色问题是具有实用价值的。但是如此得到的图，一般并非平面图或可平面图，则可由研究非平面图的点染色问题求得解决。至于图边染色，在电网络、时间表问题、拉丁方构造等方面都有很好的应用实例，这里不一一列举了。虽然图染色问题已经取得了不少的理论研究及应用研究成果，但是染色问题的原本问题“四色猜想”迄今尚未得到令人满意的结果，致使“四色定理”的证明成为悬而未决的一大世界数学难题。由于这一数学难题历时150多年尚未解决，就不能不使一些数学家们想到：很可能“四色定理”的证明必然伴随着一个全新的数学方法的诞生，以至形成一个全新的数学分支。若果真如此，研究“四色定理”的意义就远远超出其染色本身了，这将是数学家们对数学发展的一个重大贡献。参考文献1卜月华 图论及其应用M 南京：东南大学出版社 2002 197-2252王邵文 图的染色问题综述J 北京机械工业学院学报 1