四色问题

四色问题 一、四色问题及其由来 四色问题的一般叙述为:对任何一张地图上的国家染色，是否只四色问题探索 需要四种颜色就能保证任意两个相邻的国家都可以染上不同的颜 色, 山西焦化集团有限公司子弟中学 作为一个数学问题来要求，上述提法显然有含混不清的地方。例 如，两个在边界上只有一个或几个公共点的国家算不算是相邻的,一姜彦林 个国家是否允许有两块或两块以上互不相毗邻的领土,等等。 摘要:本文介绍了著名的四色问 题及其由来，给出了四色问题的确切 ，并且证明了四色定理的成立; 最后，对他进行推广，得出一个新的 首先两国相邻是指它们的公共;边界上至少包含一段连续曲线， 因此两个只在一个或有限个点接壤的国家不算相邻。否则我们可以象结论，同时介绍了他的一些应用。 图1.1那样构造出任意多个在一点彼此相邻的国家，当然绝对不能用 四种颜色对它们染色使得任何两个相邻的国家染上的颜色都不同。其 次，国家是指由一条或若干条不自交的连续闭曲线围起来的连通闭曲 域，但是一个国家不能有两块或两块以上互不毗邻的领土。如果不这 样约定，四色问题的答案就是否定的。例如图1.2中的国A分成了两块，关键词:相邻、贪婪算法、两两显然用四种颜色无法使A中的两块都不同。最后，约定地图上国家的 数目是有限的，如果把至少属于三个国家的边界上的点看成图上的顶相邻、对偶图。 点，连接两个顶点的两国的公共边界看成边，又当另一个国家完全包 围时，就在其公共边界的闭曲线上任取一点作为顶点，这样一来，地 图就成为一个平图，国家对应于平图上的面。 1852年弗兰西斯?嘉思瑞(Francis Guthris)在和他弟弟弗雷 德里克?嘉思瑞(Fredrick Guthris)的通信中提出了四色问题， 弗雷德里克求教于他们的老师德?摩根(De Morgan)，摩根与他的 朋友在通信中讨论过这个问题，但无法解决。1878年凯莱在伦敦数学 会宣布了这个问题，这才引起数学界的广泛注意。肯佩(Kempe)和 泰特(P.G.Tait)分别在1879年和1880年发文章,声称证明了四色问 题。十一年后，希伍德(P.J.Heawood)于1890年指出了肯佩证明中 的错误，但却利用肯佩的方法证明了五色定理，即任何一个简单平面。 如图2.2中的(a)、(b)、(c)三种情况图的色数不超过5。1891年彼得森指出了泰特证明中的错误，利用泰 特的方法彼得森证明四色猜测与如下命题等价:任何一个2边连通3正 则平面图的边色数为3。经过一百多年之后，这个貌似简单的四色猜 测才被美国的阿佩尔(K.Appel)和哈肯(W.Haken)于1976年借助电子 计算机给出了证明。由于证明异常繁冗，而且其中某些部分必须借助 于计算机来验证，当前仍有人对此持保留态度，也曾有人声称发现了 证明中的错误。不过迄今为止，在公开发表的文章和籍中对其证明 还是肯定的。给出四色定理一个无需借助于计算机的证明一直是一个 未获解决的问题。下面我给出一个初等的证明方法，供大家一同探讨。 由以上的情况，我们即可得出不存在五个国家两两相邻。因为第 五个国家要与两两相邻的四个国家都相邻，那么在上面的图中。他只二、四色定理的证明 能处在三角形的外部或?、?、?这四个部分之中，然而不论在那个为了证明四色定理的成立，我们首先引入一种算法，叫做贪婪算 部分，我们所得的结果总是有一个划两个甚至三个国家不能与他相法:就是只顾眼前的最佳选择，而不管整体的效果如何的算法。在这 邻 ，所以我们说，不存在五个国家 两两相邻，即至多有四个国家可里，我们的贪婪算法就是在给地图进行染色时，从一个国家开始，总 以两两相邻。也就是说，用贪婪算法，可以证明用四种颜色对地图上是试图用标号最小的颜色去给下一个国家染色。 的国家染色，就能保证任意两个相邻的国家都染上不同的颜色。 有了贪婪算法，那么我们只需要证明在平图上最多只有四个国家 证明:(用反证法)要证明四色定理成立，只需证明不存在有五可以两两相邻，我们就可以认为四色定理成立，也就是不存在有五个 个国家可以两两相邻即可。 可以两两相邻。 国家 假设存在有五个国家两两相邻，则其中任意四个国家都两两相定理:地图上，在一定意义上来讲，最多只存在有四个国家可以 邻。 两两相邻。 取其中的四个国家A、B、C、D，其分布只能如前图所示。这四个;在我们约定的意义上来讲，两国相邻必须有一段连续的曲 国家把平面上的其他部分最多分成四类区域，考虑第五个国家E所处线来作为他们的公共边界。三国两两相邻则至少人三段连续的曲线来 的位置。 作为他们的公共边界。其情况有如下两种，如图2.1，分A、B两种情 显然E不可能处在四个国家外侧的部分，因为如此则不能与D相况。 邻。 不妨设，E处在区域?内，则由分析过程可知，他不能与C相邻， 同理E也不能处在区域?或?内。 所以说不存在有五个国家两两相邻，即最多可以有四个国家可以 两两相邻。也就是说，在任何地图上，至多需要四种颜色就可以把所 有相邻的国家都分开。 四个国家两两相邻，则他们的公共边界至少有C,6段连续的曲三、四色定理的推广及应用 线。那么我们有如下几种情况: 由以上证明，我们推广到其他维的情况，可以得到在一条直线上，a:如图2.1(b)中，以中间部分D作为第四个国家，b、c、d分别 只需要两种颜色就可以把一条直线分成无数段。 三维情况下，则不存在任何数目的定理可以成立。因为如果我们拿一条绳子，由若干股细绳拧成，而这些细线显然是可以两两相邻的。因而我们不能用有限种颜色把他们分开，而且使相邻的颜色均不同。 在探索以上证明的过程中，我发现把一个国家与其他国家相邻的公共边界看成边，把至多属于三个国家的点看作顶点。我们可以的把地图上所有的国家都看成多边形，如果一个国家完全包含于另一个国家，我们把这个国家看作三角形，一个国家只与两个国家相邻，把这个国家看作四边形。如此以来，因为每一个简单多边形，可以用这个多边形内部的彼此不相交的对角线，将其分解成若干三角形之和(证明见附录)，又因为每一个三角形只有三条边与其他三角形相邻。因此能够得出，只需四种颜色就可以把平面分成无限多个三角形组成的小区域。由此推广开来，对于简单多面体，我们是否也可以用这个多面体内部的对角面，将其分解成若干个四面体之和呢, 我们把地图看作一个平图G，其中的国家看作面，考虑他的对偶图G*，则G*是一个无割边的多边形组成的平图，其中的顶点即为原来的国家。那么一个顶点周围与他相邻的顶点依次相邻就构成一个环状。而这个环状如果有奇数个顶点，我们要三种颜色就能把他们间隔开;如果有偶数个顶点，我们要两种颜色就能把他们间隔开。由此也可以四色定理成立。这点应用到跳棋上，我发现，在跳棋的棋盘上，把棋子所处的位置看作顶点，则按一个棋子所能跳到的点分类，可以把棋盘上的点分成四个等价类，这一点可以延伸到整个平面。 参考文献: 1、陈子歧、朱必文、刘峙山编《图论》 1990年5月版，高等教育出版社出版 2、亨斯贝尔格?R著 新数学译丛《数学中的智巧》 1990年5月版，北京出版社出版