四色定理:数学定理-中文百科频道

发展简史

来自地图的启示

相传四色问题是一名英国绘图员提出来的此人叫格思里。1852年他在绘制英国地图的发现如果给相邻地区涂上不同颜色那么只要四种颜色就足够了。需要注意的是任何两个国家之间如果有边界那么其边界不能只是一个点否则四种颜色就可能不够。

格思里把这个猜想告诉了正在念大学的弟弟。弟弟认真思考了这个问题结果既不能证明也没有找到反例于是向自己的老师、著名数学家德·摩根请教。德·摩根解释不清当天就写信告诉自己的同行、天才的哈密顿。可是直到哈密顿1865年逝世为止也没有解决这个问题。从此这个问题在一些人中间传来传去当时三等分角和化圆为方问题已在社会上“臭名昭着”而“四色瘟疫”又悄悄地传播开来了。

问题的证明一波三折

1878年凯莱正式向伦敦数学会提出了这个问题。凯莱可是英国响当当的数学家他看中的问题必定不同凡响。消息传到了律师肯普的耳朵里引起了他的极大兴趣。不到一年肯普就提交了一篇论文声称证明了四色问题。人们以为事情到此就已经完结了。谁知到1890年希伍德在肯普的文章中找到一处不可饶恕的错误。

不过让数学家感到欣慰的是希伍德没有彻底否定肯普论文的价值运用肯普发明的方法希伍德证明了较弱的五色定理。这等于打了肯普一记闷棍又将其表扬一番总的来说是贬大于褒。真不知可怜的肯普律师是什么心情。追根究底是数学家的本性。一方面五种颜色已足够另一方面确实有例子表明三种颜色不够。那么四种颜色到底够不够呢？这就像一个淘金者明明知道某处有许多金矿，结果却只挖出一块银子你说他愿意就这样回去吗？

接下去的戏就得由闵可夫斯基来演了。这里得说他几句好话他虽然没有成功可自认第一流倒也并非自不量力。要知道19世纪末20世纪初德国格丁根大学能成为世界数学中心就是由于他和希尔伯特、克莱因“三巨头”的努力。四色瘟疫在英国蔓延时还真没有一个研究过它的数学家比得上闵可夫斯基。

令闵可夫斯基尴尬的一堂课

19世纪末德国有位天才的数学教授叫闵可夫斯基他曾是爱因斯坦的老师。爱因斯坦因为经常不去听课便被他骂作“懒虫”。万万没想到就是这个“懒虫”后来创立了著名的狭义相对论和广义相对论。闵可夫斯基受到很大震动他把相对论中的时间和空间统一成“四维时空”这是近代物理发展史上的关键一步。

在闵可夫斯基的一生中把爱因斯坦骂作“懒虫”恐怕还算不上是最尴尬的事……一天闵可夫斯基刚走进教室一名学生就递给他一张纸条上面写着“如果把地图上有共同边界的国家涂成不同颜色那么只需要四种颜色就足够了您能解释其中的道理吗”

闵可夫斯基微微一笑对学生们说“这个问题叫四色问题是一个著名的数学难题。其实它之所以一直没有得到解决仅仅是由于没有第一流的数学家来解决它。”为证明纸条上写的不是一道大餐只是小菜一碟闵可夫斯基决定当堂掌勺问题就会变成定理……

下课铃响了可“菜”还是生的。一连好几天他都挂了黑板。后来有一天闵可夫斯基走进教室时忽然雷声大作，Minkowski很严肃的说：“上天被我的骄傲激怒了，我的证明是不完全的……”。

缓慢的进展

当时由大数学家黎曼、康托尔、庞加莱等创立的拓扑学之发展可谓一日千里后来竟盖过大数学家高斯宠爱的数论成为雍容华贵的数学女王。四色问题就是属干拓扑学范畴的一个大问题。拓扑学不仅引进了全新的研究对象也引进了全新的研究方式。对数学来说它不啻是一场革命。回顾拓扑学的历史就可以说明为什么四色问题对于20世纪数学来说是重要的。通俗地说连续变换就是你可以捏、拉一个东西但不能将其扯破也不能把原先不在一起的两个点粘在一起。比如对于26个大写英文字母一些拓扑学家就认为可将其分成3类

第一类

第二类

第三类。

第一类在连续变换下都可以变成第三类则都可变成I。

因为4是平面的色数它也是一种示性数可见示性数有很多种体现了平面的拓扑性质与国家的形状无关将平面弯成曲面也没关系。数学家必须确定这个数究竟是5还是4这很重要。如果国家分布在一个环面上画地图最多得要七种颜色。

吊起数学家胃口的还有一个原因。乍一看环面似乎更复杂事实上环面的七色定理却比较容易证明希伍德当时就做到了到1968年其他所有复杂曲面的色数均已确定唯有平面或球面的四色问题依然故我。看来平面没有人们想象的那么简单

1913年伯克霍夫引进了一些新的技巧导致1939年弗兰克林证明22国以下的地图都可以用四色着色。1950年温恩将22国提高为35。1968年奥尔又达到了39国。1975年有报道52国以下的地图用四色足够。可见其进展极其缓慢。

计算机帮助人们圆梦

不过情况也不是过分悲观。数学家希奇早在1936年就认为讨论的情况是有限的不过非常之大大到可能有10000种。对于巨大而有限的数，最好由谁去对付？今天的人都明白：计算机。

从1950年起希奇就与其学生丢莱研究怎样用计算机去验证各种类型的图形。这时计算机才刚刚发明。两人的思想可谓十分超前。

1972年起黑肯与阿佩尔开始对希奇的方法作重要改进。到1976年他们认为问题已经压缩到可以用计算机证明的地步了。于是从1月份起他们就在伊利诺伊大学的IBM360机上分1482种情况检查历时1200个小时，作了100亿个判断最终证明了四色定理。在当地的信封上盖“Four colorssutfice”四色，足够了的邮戳就是他们想到的一种传播这一惊人消息的别致的方法。

人类破天荒运用计算机证明著名数学猜想应该说是十分轰动的。赞赏者有之，怀疑者也不少，因为真正确性一时不能肯定。后来也的确有人指出其错误。1989年，黑肯与阿佩尔发表文章宣称错误已被修改。1998年托马斯简化了黑肯与阿佩尔的计算程序但仍依赖于计算机。无论如何四色问题的计算机解决给数学研究带来了许多重要的新思维。

定理定义

四色问题又称四色猜想、四色定理是世界近代三大数学难题之一。地图四色定理(Four color theorem)最先是由一位叫古德里Francis Guthrie的英国大学生提出来的。德·摩尔根Augustus De Morgan1806-1871，1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明四色定理的设想与感受。一个多世纪以来数学家们为证明这条定理绞尽脑汁所引进的概念与方法刺激了拓扑学与图论的生长、发展。1976年美国数学家阿佩尔K.Appel与哈肯W.Haken宣告借助电子计算机获得了四色定理的证明又为用计算机证明数学定理开拓了前景。

地图四色定理(Four color theorem)最先是由一位叫古德里Francis Guthrie的英国大学生提出来的。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示即“将平面任意地细分为不相重叠的区域每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”也就是说在不引起混淆的情况下一张地图只需四种颜色来标记就行。

拓扑学问题，找出给地图着色所需用的不同颜色的最小数目，使所有相邻的区域都有不同的颜色。最早在1852年由一名英国数学学者F.格思里提出。这个问题由K.阿佩尔和W.哈肯于1976年在计算机的辅助下验算解决。

定理意义

一个多世纪以来，数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。

定理推广

虽然任何平面地图可以只用四个颜色着色，但是这个定理的应用却相当有限，因为现实中的地图常会出现飞地，即两个不连通的区域属于同一个国家的情况（例如美国的阿拉斯加州），而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种情况下，只用四种颜色将会造成诸多不便。

实际中用四种颜色着色的地图是不多见的，而且这些地图往往最少只需要三种颜色来染色。此外，即便地图能够只用四种颜色染色，为了区分起见，也会采用更多的颜色，以提示不同地区的差别。

验证推导

地图上任何一个区域必将存在邻域，且又通过邻域与其他非邻域发生间接联系，我们可以将任何一个地图以图论图形的表示出来。

假设存在一张至少需要种着色的地图，那么决定该地图必须要用种着色的条件有且只有一个，即该地图至少存在这样一个区域，与该区域相邻的所有区域必须满足着色。首先满足这个条件后，只能用第种颜色，其次如果这个推论一是错误的，对于着色地图不存在这样的区域，那么地图上任何一个区域的邻域只能满足少于的着色，那么整个地图势必不需要中颜色，这与假设相矛盾，所以这是一个充分必要条件。（推论一）

假设随意取一张任意结构的至少着色的地图，其上满足上述条件的区域有个，那么将图论图形中的这个区域及其与邻域的关系线我们可以全部去掉，这样我们就将构建一个至少着色地图的问题转化成了一个在至少需要着色地图上添加个满足推论一条件的区域问题。

如果五着色地图存在且能构建成功，那么必然存在构建这样五着色的四着色模型图，而要存在这样的四着色模型图必然存在构建该四着色的三着色模型图，同理要存在这样的三着色模型图必然要存在构建它的二着色模型图，那么我们来构建一下五色图是否存在：

二着色地图是由一着色而来的一种简单的着色地图模型，我们很容易得到满足二着色的地图仅有的两种类型的结构，一种是不闭合的链状结构，如图一；另一种是由第一种衍生出来的闭合的环状结构且环所联系的区域为偶数个，称为偶数环，如图二。

我们看下二着色结构特点发现，图一图二都是一个原理就是奇偶位置决定着色，任何两个区域的任何联系链条只有相隔偶数个区域才满足两区域着色不同，我们定义这两个区域为偶隔域。

我们随意取一张任意结构的二着色的地图，来构建一个具有个满足推论一条件区域的地图，构建方式有且只有一个，就是在图论图形中我们如何去掉的这个区域及其与邻域的关系线，我们接怎么给它添加回去。我们任取这个区域中一个区域为例，只要我们在地图上将必须满足二着色的几个区域直接联系到上，这样就满足推论一中的条件而使必须为三着色。

而要满足二着色则必定含有偶隔域，如果有个区域和发生直接联系，则上出去的关系线有个，那么我们一定可以将该复杂的联系分解成个不可分解关系环，其中至少有一个不可再分的关系环是中的偶隔域与联系的，（推论二）假设这个推论是错误的，所有不可再分的环全部是奇隔域，那么这些环拼接回去时满足每个小环的间隔区域数相加再减去共用的区域，仍旧是奇隔域，这样便不满足二着色，所以这些不可再分环中一定有偶隔域和发生联系而构成奇数环（环连的区域为奇数），并且导致必须使用第三色的就是这些不可再分的奇数环。

由于满足二着色的只有偶隔域一种条件，那么构造的三着色地图中决定三着色的条件也只有一种，存在不可再分的奇数环。

在上面构建的三色着色地图基础上我们再来构建四着色地图，假如存在满足推论一条件的区域有个，同样的方法，我们任取中一个区域，只要我们在地图上将必须满足三着色的几个区域直接联系到上，这样就满足推论一中的条件而使必须为四着色。

而要满足三着色则必定含有奇数环并且组成奇数环的区域都能够与发生联系（保证奇数环没有被包围在其他闭合环内的部分），如果有个区域和发生直接联系，则上出去的关系线有个，那么导致为第四色原因是可发生联系的奇数环，既只要有一个这样的奇数环存在就一定会导致使用第四色（推论三），假设这一推论不成立那么没有这样的奇数环存在，则由前面二着色建立三着色正经得到，除了奇数环再没有能使地图为三着色的条件了，或者当奇数环区域不能全部与发生联系，这样必然的不需要第四色了。

故我们的推论三成立。由于三着色条件唯一而使得四着色的条件唯一，我们来看四着色条件的特点，当与发生联系后，不管有多少满足条件的奇数环，势必最终只能有包括在内的三个区域能与外界区域发生联系。因为和上的任何两个区域都可以构成一个封闭的三角形，而当我们选的上这俩区域与关系线是最外侧的关系线时，则上其他区域一定不能在三角形外，不然或造成以上两根关系线不再是最外侧或者有关系线出现交叉，所以上剩馀区域必定在三角形内而造成四着色图最多只有三个区域能与外界发生联系。