书城科普读物探索未知-诗歌与数学
8885000000003

第3章 诗中的“四色猜想”

世界地图在今天已不算什么稀奇的东西,但在20世纪初的中国,它的出现,却还算得一件新鲜事。近代我国有个名叫杨圻(1875-1941年)的诗人,曾做过中国驻新加坡的总领事,他就曾因房中挂了一幅世界地图而专门写了一首题为《咏五洲地图》的长诗来抒发感受:入门屋大乾坤窄,八荒四极在我室。

手扪五岳皆平地,坐视沦海忽壁立。

恍如上界一俯瞩,三分尘土水居七。

又如置身洪荒前,当时不见一人迹。

昆仑之外原无山,余气磅礴散万脉。

东南诸国临大水,西北川原岂终极!

乃知大块非无垠,直若盆水浮败叶。

关塞古今称形胜,自我视之皆智力。

图中斑驳五色分,人种国界辨明晰。

世上沿革血染成,此图变更乍朝夕。

人间无日无干戈,一万年后知何色?

起来取图裂粉碎,无地存身计亦得。

回顾新月照空墙,似闻吴刚嫦娥微叹息。

这诗的前半首着重写有关地球的科学知识,扫清了自古以来人们对大地的糊涂观念。诗中将平面的、静态的地图与立体的、复杂的地球的实体进行巧妙的联系与对比,想象奇特,比喻新巧,写来妙趣横生。作者所处的时代,正是鸦片战争以后,中国受到列强的侵略,面临被瓜分的危险。所以,作者在描写了地球的状态之后,笔锋一转,抒发对时事的感慨。当今世界正是你争我夺,弱肉强食之秋。诗中用“世上沿革血染成,此图变更乍朝夕”两句,从纵向和横向概括了人类世界的历史和现状。诗人强烈地表达了对列强掠夺战争的愤恨,宁愿自己无地存身,也要亲自动手把反映列强掠夺的地图撕得粉碎。最后更发挥丰富的想象,从人间写到了天上,善良的吴刚与嫦娥这些神仙们,也在为人间的不平而微微地叹息哩!

诗中还有这样的两句“图中斑驳五色分,人种国界辨明晰”。不知道是诗人所见的地图确实只用了5种不同的颜色,还是泛指五颜六色的意思。不过,不管诗人的原意如何,用了5种颜色,总是可以把一张地图的国界分得清清楚楚的。这个问题还牵涉到数学史上一段极为有趣的史实哩。

根据惯例,在绘制彩色地图时,任何两个相邻的国家(所谓相邻是指两国有一段公共的边界)都必须使用不同的颜色,使能保证区别,这是一个原则。人们很早就发现,任何地图,不论国家多少,也不论其分布怎样复杂,只要有4种不同的颜色,就一定可以找到一种着色方法,使得相邻的国家都有不同的颜色。以下为了说话的方便,我们把满足这种要求的着色方法称为“正确着色”。

很容易举出实例,用3种不同的颜色是不能正确着色的。如下面那样的地图,它包含4个国家,3个国家把第四国环绕于其中。外面的3个国家必须用3种不同的颜色来着色,第四国就无法着色了。

于是,人们想到,3与4是否就是地图能否正确着色的分界线呢?即:任何地图,只要使用4种不同的颜色,就一定可以正确着色。这就是数学史上有名的“四色猜想”。

证明“四色猜想”的问题,似乎最早是由麦比乌斯于1840年提出来的,此后,德摩根于1850年又重新提及,1878年又再次提出。“四色猜想”刚提出来时,并没有引起人们的重视,连一些第一流的数学家也低估了它的难度。据说,爱因斯坦的老师闵可夫斯基(1864-1909年)是一位很有成就的数学大师,他曾为爱因斯坦的相对论提供了四维空间的数学结构。闵可夫斯基为人一向谦虚谨慎,偏偏有一次在给大学生讲课时,错误地把“四色猜想”的证明看得太简单了。他说,“四色猜想”之所以一直没有获得解决,只是因为当今世界一些第一流的数学家没有去研究它罢了。说罢,他拿起一支粉笔,竟要当堂给学生推导出来,结果他没能如愿。下一节课他又去试,又没推出来,以后长时间研究也毫无进展。终于有一天,他疲惫不堪地走进教室向学生宣布,他解决不了“四色猜想”问题。这时,恰巧碰上雷声大作,他愧疚地说:“你们看,老天爷也在责备我狂妄自大了!”

1879年,肯普对“四色猜想”终于作出了一个“证明”,但不到一年,海伍德就发现了肯普证明中的错误。不过,还值得庆幸的是,海伍德在指出肯普的错误时,得到了一个重要的副产品:“用5种不同的颜色总可以将一张地图正确着色。”人们称之为“五色定理”。

以后近一个世纪,一直没有人能证明“四色猜想”。一直到现代超大型电子计算机问世以后,1976年美国伊利诺州立大学的两位科学家阿培尔和哈肯在计算机专家柯奇的帮助下,使用电子计算机证明了“四色猜想”。他们成功地运用了一种“不可避免性理论”,从1万多张地图中挑选了2000千张进行检验,对每一张地图都使用20万种可能的方法着色。计算机经过了1200小时的计算,作了200亿个逻辑判定,终于在1976年6月解决了这一数学悬案,证明“四色猜想”是正确的,从此,“四色猜想”成为“四色定理”。

令人震惊的是:“四色定理”的证明如此之难,而“五色定理”的证明却出人意外地简单。下面我们来介绍“五色定理”证明的基本思路。

我们只限于讨论各区域的边界都是由圆弧组成的简单多边形,每个顶点都恰好是3条弧相交的那种地图(这种图称为正则的),如下图a所示的那种地图。

图a图b如果某一顶点处相交的弧多于3个,例如上图b中的A点,只要将该点扩大为一个圆,把小圆当作某一区域,那么所有的顶点就都成为只有3条弧相交了,如果新得的正则图可以用5种颜色正确着色,着色后将此圆再缩成点,返回到原来的地图仍然是正确着色的。所以,我们只对正则图证明“五色定理”就可以了。

首先证明:每一个正则图中一定有一个区域的边数小于6。

用Fn表示正则图中边数为n的区域的个数,要证明正则图中有一个区域的边数小于6,只要能证明F2,F3,F4和F5这4个数中,至少有一个不为0就可以了。例如,如果有F4不为0,这就意味着,至少有一个区域它的边数为4。

用F表示一张正则图中区域的总个数,则F=F2+F3+F4+F5+…(1)。

因为每段弧都连2个顶点,而每个顶点连3条弧,所以,如果用E表示弧数,V表顶点数,就有3V=2E(2)。

另一方面,以n段弧为边界的区域有n个顶点,而每个顶点又属于3个区域,所以又有3V=2F2+3F3+4F4+…(3)。

根据欧拉公式,一个图中的区域数F,边数E,顶点数V之间具有关系V-E+F=2(4)。

将(4)乘以6,得6V-6E+6F=12。

由(2)得6E=9V,代入上式得6F-3V=12。

再将(1)和(3)分别代入上式,即得6(F2+F3+…)-(2F2+3F3+4F4+5F6+6F6+7F7+…)=12。

或者4F2+3F3+2F4+F5-F7-2F8-…=12。

要上式成立,因F7,F8…都是非负数,必然有4F2+3F3+2F4+F5>0,即F2,F3,F4,F5至少有一个是正的。

这就证明了,任何一个正则图M都至少有一个区域的边数小于6。

(一)如果M包含一个边界数为2,3,4的区域A,将A的一条边界去掉(图c),就得到一个只有n-1个区域的正则图M′,若M′可用5种颜色正确着色,则M也可以。因为M中与A毗邻的区域最多只有4个,一定还有一种颜色可用。

(二)如果M包含有5条边界的区域A。考虑与A邻接的5个区域B、C、D、E、F,其中总能找到两个互不邻接的区域,例如图d中的C与F,去掉A与这两个区域相邻的边界就得一有n-2个区域的新正则图M′。如果M′可用5种颜色正确着色,则当恢复边界后,A将与不多于4种颜色接触,(因为C、F的颜色相同),因此总可以把A改为第五种颜色。即M也可用5种颜色正确着色。

由此可知,对任一个有n个区域的正则图M,总可以制造一个只有n-1个或n-2个区域的另一正则图M′,当M′可用5种颜色正确着色时,M也可以。不断地继续这个过程,就得到一个区域数不断地减少的正则图系列M,M′,M″……

由于区域数不断减少,在这个系列中最后必然出现区域不超过5个的正则图,它必可用5种颜色正确着色。一步一步向M回溯,最后必然M也可用5种颜色正确着色。