地图着色的四色猜想问题溯源

 

作者：我是生命我是人

 

       1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)在一家科研单位从事地图着色工作时，发现“任何一张地图似乎只用四种颜色就能使具有共同边界的国家着上不同的颜色。”
       用数学语言来表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这就是源于地图着色的四色猜想问题。这里所指的相邻区域，是指有一整段边界是公共边界。如果两个区域只相遇于一点或有限多点，就不叫相邻。因为用相同的颜色给它们着色不会引起混淆。
       能否从数学上对此加以严格证明呢？他和正在大学读书的弟弟格里斯决心一试。兄弟二人为此证题使用了稿纸一大叠，却没有任何进展。弟弟格里斯只好就此请教他的老师、著名数学家德·摩尔根（A，DeMorgan，1806～1871）。摩尔根也没能证明此题，于是写信向他的好友、著名数学家哈密尔顿爵士请教。
       摩尔根在1852年10月23日致汉密尔顿的一封信提供了有关地图四色猜想最原始的记载。他在信中这样简述了自己证明四色猜想的设想与感受：
       “我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（附图1）。现在的问题是是否会出现需要五种或更多种颜色的情形。就我目前的理解，若四个不定分割的区域两两具有公共边界线，则其中三个必包围第四个而使其不与任何第五个区域相毗邻。这事实若能成立，那么用四种颜色即可为任何可能的地图着色，使除了在公共点外同种颜色不会相邻。”
       “现画出三个两两具有公共边界的区域ABC，那么似乎不可能再画第四个区域与其他三个区域的每一个都有公共边界，除非它包围了其中一个区域（附图2）。但要证明这一点却很棘手，我也不能确定问题复杂的程度。对此您的意见如何呢？并且此事如果当真，难道从未有人注意过吗？我的学生说这是在给一幅英国地图着色时提出的猜测。我越想越觉得这是显然的事情。如果您能举出一个简单的反例来，说明我像一头蠢驴，那我只好重蹈斯芬克斯的复辙了……。”
       汉密尔顿随即也试图对该问题进行论证。但是直到十多年之后的1865年，哈密尔顿去世的时候，他也没有能证明此题。
       1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这一难题，于是关于地图着色的四色猜想就成了世界数学界关注的问题。
       世界上许多一流的数学家都曾试图证明四色猜想。在1878年至1880年的两年之间，著名的律师兼数学家肯普和泰勒分别提交了证明四色猜想的论文，宣布证明了四色定理，大家从此以为四色猜想终获解决。
       肯普的证明是这样的：首先指出如果没有一个国家包围其他国家，或没有三个以上的国家相遇于一点，这种地图就说是“正规的”（附图3左图）。如为正规图，否则为非正规图（附图3右图）。一张地图往往是由正规图和非正规图组合而成，但非正规图所需颜色种数一般不超过正规图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正规图是五色的，要证明四色猜想成立，只要证明不存在一张正规五色图就足够了。
       肯普是用归谬法来证明的，大意是如果有一张正规的五色图，就会存在一张国数最少的“极小正规五色图”，如果极小正规五色图中有一个国家的邻国数少于六个，就会存在一张国数较少的正规图仍为五色的，这样一来就不会有极小五色图的国数，也就不存在正规五色图了。这样肯普就认为他已经证明了“四色问题”，但是后来人们发现他错了。
       不过肯普的证明阐明了两个重要的概念，对后人解决此题提供了途径。
       肯普提出的第一个概念是“构形”。他证明了在每张正规图中至少有一国具有两个、三个、四个或五个邻国，不存在每个国家都有六个或更多个邻国的正规图，也就是说，由两个邻国，三个邻国、四个或五个邻国组成的一组“构形”是不可避免的，每张地图至少含有这四种构形中的一个。
       肯普提出的另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他证明了只要五色地图中有一国具有四个邻国，就会有国数减少的五色地图。自从引入“构形”，“可约”概念后，逐步发展了检查构形以决定是否可约的一些标准方法，能够寻求可约构形的不可避免组，是证明“四色猜想”的重要依据。但要证明大的构形可约，需要检查大量的细节，这是相当复杂的。
       但是，时隔十一年之后，即1890年，在牛津大学就读的年仅29岁的数学家赫伍德以自己的精确计算，指出肯普的证明是错误的。他指出肯普说没有极小五色地图能有一国具有五个邻国的理由有破绽。不久，泰勒的证明也被否定了。
       人们发现肯普和泰勒实际上是证明了一个较弱的命题——五色定理。就是说对地图着色，用五种颜色就够了。
       后来，许多涉足此题的数学家全都一无所获。于是，人们开始认识到，这个貌似简单的猜想，其实是一个堪与费马猜想相媲美的难题。
       进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。
       1913年，美国著名数学家、哈佛大学的伯克霍夫在肯普的基础上，结合自己创新的技巧，证明了某些大的构形可约。
       美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。
       1950年，有人从22国推进到35国。
       1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。
       不过看来这种进展确实十分缓慢。       
       从1936年就开始研究四色猜想的海克，宣布四色猜想可用寻找可约构形的不可避免组来证明。他的学生丢雷写了一个计算程序，海克不仅能用这程序产生的数据来证明构形可约，而且描绘可约构形的方法是从改造地图成为数学上称为“对偶”图形着手。
       海克把地图上每个国家的首都全都标示出来，然后把相邻国家的首都用一条越过边界的铁路连接起来，除首都(称为顶点)及铁路(称为弧或边)外，擦掉其他所有的线，剩下的就称为原图的对偶图。
       到了六十年代后期，海克引进一个类似于在电路网络中移动电荷的方法，来求解构形的不可避免组。在海克的研究中，第一次以颇不成熟的形式出现的“放电法”则是后人研究寻找可约构形不可避免组的一个关键，这也是证明四色猜想的核心要素之所在。
       随着电子计算机演算速度的迅速提高，加之人机对话的出现，大大加快了证明四色猜想的进程。
       1976年，在J. Koch的算法支持下，美国伊利诺斯大学的哈肯(Wolfgang Haken)在1970年着手改进“放电过程”，后与阿佩尔(Kenneth Appel)合作编制了一个很好的程序。他们于1976年6月在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。
       阿佩尔和哈肯的证明方法将地图上的无限种可能情况减少为1,936种状态（随后又减少为1,476种），这些状态由计算机逐一个进行核实。这一核实求证的工作由不同的程序在不同的计算机上独立地进行。
       四色猜想的计算机证明，轰动了世界。它不仅解决了一个历时100多年的难题，而且有可能成为数学史上，采用计算机证明数学定理的奠基之作。这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这一难题获得解决。
       1996年，Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas等人使用了类似的证明方法，使用电脑核查了633种特殊的状态。
       一个多世纪以来，在“四色猜想”的研究证明过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容，所引进的概念与方法刺激了拓扑学与图论的生长、发展。不仅如此，“四色猜想”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。
       地图四色猜想是第一个主要由计算机完成证明的数学难题。尽管这一证明，由于不能由人工直接验证，而且也缺乏数学通常的解题规范，目前尚未被所有的数学家接受。人们并不满足于计算机取得的成就，他们认为应该有可能存在一种更加简捷明快的书面证明方法。所以直到现在，仍然有不少的数学家和众多数学爱好者都在寻找更简洁的证明方法。

 

图五.采用四种颜色着色的世界地图

 

图六.采用四种颜色绘制的美国地图

 

图七.采用四种颜色绘制的法国地图

 

[附录一] 《拓扑学溯源》
发表的作者杨万翔的文章：

 

       拓扑学，数学的一门分科，研究几何图形在一对一的双方连续变换下不变的性质。不少门萨题，来自拓扑学，其典例，即是《四种颜色与地图》。此例在拓扑学中大名鼎鼎，叫做“四色问题”。

       拓扑理论用途广泛，涉及空间规划、网络设计、通讯邮递乃至心理分析等诸多领域，人们不大了解罢了。说来趣怪，致使这门学科得以诞生的契机却是一款很是独特的消闲。

       话说俄罗斯有座哥尼斯堡市，两条河于此间汇合，汇合处有个小岛，小岛跟其相对的3处河岸架设了7座桥。市民经常沿着河岸和小岛散步，于是很自然地就提出了一个实际问题：有无可能找到一条路线，能够沿它行走，经过全部7座桥却又不会重踏其中任何一座？

       时为18世纪中叶，著名数学家、瑞士人欧拉旅游至该市，他对这个消闲点子作了一番琢磨，确定了这条路线。当其时，欧拉的指划，只不过是逢场作戏，被称为“七桥问题”。

       迨至19世纪上半叶，有心人对欧拉的思路作了认真研究，在“七桥问题”基础之上，居然建立起一门崭新学科！显然极具文史素养的某位数学专家给这门学科起了个跟欧拉的原初研究无比贴切的学名———Topology！Topology是英文，其实质性部分Topo是一个同音同义的古希腊词的英文形变，意思是“地方、方位”。logy这个后缀也来自古希腊文，原意是“词语的聚集”，明治维新期间日本人大量翻译西方典籍，把它通译为“学科”之“学”。因之，若然对Topology作汉语直接对译，当为“方位学”。

       按，欧拉破解“七桥问题”之际，把3处河岸和1座小岛绘画成4个点，把7座桥绘画成7条线，点线相连，构成一个封闭的几何图形。想想看，以Topology概括欧拉的整个思路，是不是浑然天成？

       有位中国人把Topo译为“拓扑”！谁？江泽涵先生是也！江泽涵（1902-1994年），安徽旌德人，1926年毕业于南开大学，1930年获哈佛大学博士学位，1931年任北京大学数学系教授，1955年当选为中国科学院数理学部委员。他是把拓扑学引入中国的第一人，他出版的《拓扑学引论》是中国人编写的第一部拓扑学教材。译Topo为拓扑，音义兼顾，形神俱备———“拓”者，对土地之开发也，“扑”者，全面覆盖也。