图的染色问题应锡娜 06990213@（浙江师范大学 初阳学院，浙江 金华321004）摘要：木文介绍了图染色问题的提出、应用及意义，主要对已取得的研究成杲及 当今的研究状况进行了阐述关键词：图；染色；色数一、 引言图染色问题起源于著名的“四色猜想”[1]问题早在一百多年前的1852年, 英国Guthrie提出了用四种颜色就可对任意一张地图进行染色的猜想即对世界 地图或任何一个国家的行政区域地图，最多用四种颜色就可以对其染色，使得凡 是相邻的国家或相邻的区域都着以不同的颜色二、研究与发展“四色猜想”提出后，一些数学家着手研究这个猜想，力图给出证明吋隔 二十七年后，1879年Kempe给出了 “四色猜想”的第一个证明，又过了十一年, 1980年Hewood发现Kempe的证明是错误的但他指出,Kempe的证明方法虽 然不能证明“四色猜想”，却可以证明用五种颜色就够了此后，“四色猜想”一 直成为数学家们感兴趣而未能解决的世界数学难题直到1976年6刀美国数学 家伊利诺斯大学教授Appel与Haken宣布：他们用计算机证明了“四色猜想”是 正确的因此，从1976年以后，就把“四色猜想”改称为“四色定理” 了。
⑵ 值得指出的是，Appel与Haken的证明，计算机运行了 1200个小时诚然 用计算机证明数学难题实在是一个伟大的尝试或创举，但是，世界数学家们仍期 待着用常规的数学方法证明“四色定理”目前仍有许多数学家在潜心研究，寻 求常规的证明方法地图的特点在于，多个区域位于同一平面上，每个区域可以是毫无规则的各 种形状，任意两个区域可以有公共边界，但不能有公共区域于是人们开始研究 所谓“平而图”人们把地图中的每一个区域称为一个“而”,地图染色就是对“而” 染色进一步研究之后人们把地图中的每个区域的“面”视为一个点，若两个“面” 相邻接，即地图中的两个区域有一段或几段公共边界，则在表示这两个区域的点 之间连线，该连线可以是直线也可以是任意形状的曲线，并称之为边如此，就 可以把一张地图改画为一个平面上的图，人们把该图称为地图的对偶图其特点 是：所有的点及边均处在同一平而上，并但任意两条边除端点外可以不交叉，人 们称这样的图为平面图例如图1的对偶图如图2所示 图1若我们对图2中的点染色，凡是相互邻接的点染以不同的颜色，则对图2的点染色等价于对图1的而染色显然，任意一张地图的对偶图均是一个平而图, 或者说地图就是平面图。
另外，值得指出的是，并非一切图均是一个平面图，即 处于同一平面上的有些图存在着边交叉的情况如图3所示的图，图中有4个点 6条边处于同一平面上，其中边％=伉宀）与边乞=（人宀）存在着交叉点，但是, 图3可以改画为图4,而图4中不存在交叉边，即图4为平面图图3图4人们把可以改画为平面图的图称为可嵌入平面图或简称为可平面图，即图3 是可平面图而有的图，如图5所示，图中有5个点10条处于同一平面中，边勺 与边％及匕交叉且边如与边勺及勺交叉，但无论怎样改画图5均不能避免边的 交叉，人们称这样的图为非平面图图51965年，Behzad M在他的I■専士论文中首次提出并研究了图全染色问题，提 出了著名的“全染色猜想” [4]所谓图全染色的问题，是指对一个图中的点、 边、面全染色，并11使得凡相接或相关联的元索均染以不同的颜色如图6所示 图，-其中5个点为弘宀，…宀，7条边为勺,S 4个面是/1,/2,/3,/4o对图 6全染色时，点片与「2相邻接，故必须染以不同的色，边勺与勺相邻接也必须染 上不同色，面f占扎相邻接不能染以相同色并且，点儿与边勺相关联也得染 不同色，而边勺与而久相关联也须染上不同的颜色。
很显然，图6冇16个 元素，只要用16种颜色即可对其全染色，问题是所用颜色数能否减少？最少需 要多少种颜色即可对其全染色，而这个最少的颜色数，人们称之为图的全色数[3]o Behzad M的全染色猜想为：对于简单连通图G冇A（G）+l |V（G）- 4的图，“全 染色猜想”也是成立的。
三、应用与意义研究图染色问题有什么应用价值及理论意义呢？若仅就地图染色而言，用四 种色或更多一些颜色并无多大实用价值然而，若将地图中的几个区域视为几种 化学品，凡两个邻接的区域所代表的两种化学品有某种关系，例如该两种化学品 若放在一起容易发生爆炸或引起变质等现欲建造仓库来存放几种化学品，显然 建造儿个仓库分别存放这儿种化学品是力无一失的但建库费用大，怎样才能使 建库数量最少，又能使这几种化学品的存放万无一失呢？显然，两两均无任何危 险关系的几种化学品可存放于同一仓库中，即只要建造一个仓库就够了可见， 这一建库问题就转化为图点染色问题了，所以研究图染色问题是具有实用价值 的但是如此得到的图，一般并罪平而图或可平而图，则可由研究非平而图的点 染色问题求得解决至于图边染色，在电网络、时间表问题、拉丁方构造等方面都有很好的应用 实例，这里不一一列举了虽然图染色问题已经取得了不少的理论研究及应用研究成果，但是染色问题 的原本问题一一“四色猜想”迄今尚未得到令人满意的结果，致使“四色定理” 的证明成为悬而未决的一大世界数学难题由于这一数学难题历时150多年询未 解决，就不能不使一•些数学家们想到：很可能“四色定理”的证明必然伴随着一 个全新的数学方法的诞生，以至形成一个全新的数学分支。
若果真如此，研究“四 色定理”的意义就远远超出其染色本身了，这将是数学家们对数学发展的一个重 大贡献参考文献［1］ 卜月华图论及其应用［M］南京：东南大学出版社2002 197-225［2］ 王邵文图的染色问题综述［J］北京机械工业学院学报1995 10 (2) 59-65［3］ 王邵文图的色数问题研究［J］北京机械工业学院学报1997 12 (1) 15-20［4］ 胡代强图的全着色与度序列［J］太原机械学院学报1994增刊⑸H・P •叶著，姚兵、顾同新、张建勋译图论中的若干专题［M］合肥：科 学技术大学出版社1992。