三色原理是什么?

以前我忘记了

世界近代三大数学难题之一。四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”这个结论能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。

　　1852年10月23日，他的弟弟就这个问题的证明请教他的老师、著名数学家德·摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1865年哈密尔顿逝世为止，问题也没有能够解决。

　　1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。

　　11年后，即1890年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题：先辈数学大师们的努力，为后世的数学家揭示四色猜想之谜铺平了道路。

　　进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。1913年，伯克霍夫在肯普的基础上引进了一些新技巧，美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。看来这种推进仍然十分缓慢。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，在J. Koch的算法的支持下，美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。四色猜想的计算机证明，轰动了世界,当时中国科学家也有在研究这原理。它不仅解决了一个历时100多年的难题，而且有可能成为数学史上一系列新思维的起点。

　　证明方法将地图上的无限种可能情况减少为1,936种状态（稍后减少为1,476种），这些状态由计算机一个挨一个的进行检查。这一工作由不同的程序和计算机独立的进行了复检。在1996年，Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas使用了一种类似的证明方法，检查了633种特殊的情况。这一新证明也使用了计算机，如果由人工来检查的话是不切实际的。

　　四色定理是第一个主要由计算机证明的理论，这一证明并不被所有的数学家接受，因为它不能由人工直接验证。最终，人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任。

　　缺乏数学应有的规范成为了另一个方面；以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿！”

德·摩尔根：地图四色定理

地图四色定理最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。德??摩尔根（A，DeMorgan，1806～1871）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明四色定理的设想与感受。一个多世纪以来，数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken）宣告借助电子计算机获得了四色定理的证明，又为用计算机证明数学定理开拓了前景。以下摘录德??摩尔根致哈密顿信的主要部分，译自J． Fauve1 and J.Gray（eds.），The History of Mathematics ：A Reader，pp． 597～598。

德·摩尔根致哈密顿的信（1852年10月23日）

我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。现在的问题是是否会出现需要五种或更多种颜色的情形。就我目前的理解，若四个不订分割的区域两两具有公共边界线，则其中三个必包围第四个而使其不与任何第五个区域相毗邻。这事实若能成立，那么用四种颜色即可为任何可能的地图着色，使除了在公共点外同种颜色不会。

现画出三个两两具有公共边界的区域ABC，那么似乎不可能再画第四个区域与其他三个区域的每一个都有公共边界，除非它包围了其中一个区域（图2）。但要证明这一点却很棘手，我也不能确定问题复杂的程度一对此您的意见如何呢？并且此事如果当真，难道从未有人注意过吗？我的学生说这是在给一幅英国地图着色时提出的猜测。我越想越觉得这是显然的事情。如果您能举出一个简单的反例来，说明我像一头蠢驴，那我只好重蹈史芬克斯①的覆辙了……。