四色问题 | 玄数

2014-08-19

四色问题,是世界近代三大数学难题之一。

其内容是:“任何一张地图只用4种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示,即“将平面任意地细分为不相重迭的区域,每一个区域总可以用1,2,3,4这四个数字之一来标记,而不会使相邻的两个区域得到相同的数字。”

四色地图

在公元1852年,毕业于英国伦敦大学并从事地图着色工作的弗兰西斯 ·格里斯,发现了一个奇怪的现象:无论多么复杂的地图,只要用四种颜色,就可以区分有公共边界的国家和地区。弗兰西斯觉得其中一定有什么奥妙,于是请教其兄佛德雷克。当他绞尽脑汁依然不得要领时,只好请教自己的老师——英国数学家摩根。

摩尔根也没有能找到解决这个问题的途径,于是写信向自己的好友、著名数学家汉密尔顿爵士请教。他在信中写道希望能证明“如果一张地图,图上任意分成许多部分,要求有共同边界的两部分涂不同颜色,那么只要四种颜色就够了”,要么构造出一个需要五种或更多种颜色的图来。然而,对两者哈密尔顿都没做到。他耗费了整整13心血,终于一筹莫展,抱恨逝去。

又过了13年,一位颇有名望的英国数学家凯莱(Caylaey, 1821~1895)在一次数学年会上把这问题归纳为“四色猜想”。并于1879年,在英国皇家地理会刊的创刊号上,公开征求对“四色猜想”的解答。于是四色猜想成了世界数学界关注的问题。

同年,一位叫肯普的数学家发表了对四色定理的证明。他的证明运用归谬法,并阐明了两个重要的概念,对以后问题的解决提供了途径。第一个概念是“构形”。他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻国,不存在每个国家都有六个或更多个邻国的正规地图,也就是说,由两个邻国,三个邻国、四个或五个邻国组成的一组“构形”是不可避免的,每张地图至少含有这四种构形中的一个。另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他证明了只要五色地图中有一国具有四个邻国,就会有国数减少的五色地图。

人们普遍认为“四色猜想”已经成为历史。不料11年后,即1890年,在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。赫伍德利用肯普提供的方法证明了“五色定理”,即用五种颜色就能够区分地图上相邻的国家。这也是一个重大的突破!设f2为边界只有两个顶点的国家数, f3为边界只有两个顶点的国家数,……那么国家总数f为  f = f2 + f3 + f4 + … …

由于f2这类国家有两个顶点,因而有两条边界,从而这类国家共有2 f2条边界。同理f3这类国家共有3f3条边界… …从而边

2e = 2 f2 + 3f3 + 4f4 + … …

现我们只讨论顶点是3个国家界点的地图,对于顶点总数v有

3v = 2 f2 + 3f3 + 4f4 + … …

由此可得 2e = 3v

根据欧拉定理 v + f = e + 2 消去e 可得:  6f = 3v + 12

即                    6(f2 + f3 + f4 + … …)= (2 f2 + 3f3 + 4f4 + … …)+ 12

化简得                   4f2 + 3f3 + 2f4 + f5 = 12 + f7 + 2f8 + … …

由于上式右端不小于12,因此左端必有一项大于0。这样,赫伍德便得到一个很重要的结论:“每张交点有三个国家相遇的地图,至少有一个国家边界数不多于5。” 赫伍德的证明还用了归纳法(省略)。

后来,越来越多的数学家虽然对此绞尽脑汁,但一无所获。于是,人们开始认识到,这个貌似容易的题目,其实是一个可与费马猜想相媲美的难题。

1922年,有人证明了国家数f ≤ 25时四色猜想成立;1938年,国家数f推进到32;1969年又推进到45。但是,这种推进十分缓慢。这确是一条布满荆棘的道路!

就在这时,科学的地平线上出现了一道曙光!电子计算机的运用,使四色猜想的证实有了希望。公元1976年,美国伊利诺斯大学的数学家阿佩尔和哈肯教授,运用每秒计算400万次的电子计算机,在运转1200小时后,终于成功地完成了“四色定理”的证明工作。数学史上的三大难题之一,在人与计算机的合作下,终于被征服了!

不过不少数学家并不满足于计算机取得的成就,他们认为应该有一种简捷明快的书面证明方法。直到现在,仍由不少数学家和数学爱好者在寻找更简洁的证明方法。

中国四色地图

 

中国四色地图

四色问题