数学史-四色问题
四色问题
一、 四色问题的概念
“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”
用数学语言表示,即“将平面任意地细分为不相重叠的区域,每一个区域总可以用1,2,3,4这四个数字之一来标记,而不会使相邻的两个区域得到相同的数字。”(这里所指的相邻区域,是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点,就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。)
二、 四色问题的发现 四色问题又称四色猜想,是世界近代三大数学难题之一。 ( 世界近代另外两大大数学难题:
费马最后定理 :当整数n > 2时,关于x, y, z 的不定方程x n +y n =z n ,无正整数解。
哥德巴赫猜想 :任一大于2的整数都可写成三个质数之和。 )
四色猜想的提出来自英国。1852年,毕业于伦敦大学的弗南西斯·格思里来到一家科研单位搞地图着色工作时,发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢?他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠,可是研究工作没有进展。弟弟格里斯只好就此请教他的老师、著名数学家德·摩尔根(A ,Demorgan ,1806~1871)。摩尔根也没能证明此题,于是写信向他的好友、著名数学家哈密尔顿爵士请教。哈密尔顿随即也试图对该问题进行论证。但是直到十多年之后的1865年,哈密尔顿去世的时候,他也没有能证明此题。从此,这个问题在一些人中间传来传去,当时,三等分角和化圆为方问题已在社会上“臭名昭著”,而“四色瘟疫”又悄悄地传播开来了。
三、 四色问题的提出
1872年,英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题,于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。( 凯利一生仅出版一本专著,便是1876年的《椭圆函数初论》,但发表了近1000篇论文,其中一些影响极为深远。凯利在劝说剑桥大学接受女学生中起了很大作用。他在生前得到了他所处时代一位科学家可能得到的几乎所有重要荣誉。)
四、 四色问题的证明---一波三折
在1878年至1880年的两年之间,著名的律师兼数学家肯普和泰勒分别提交了证明四色猜想的论文,宣布证明了四色定理,大家从此以为四色猜想终获解决。
但是,时隔十一年之后,即1890年,在牛津大学就读的年仅29岁的数学家赫伍德以自己的精确计算,指出肯普的证明是错误的。不久,泰勒的证明也被否定了。 人们发现肯普和泰勒实际上是证明了一个较弱的命题——五色定理。就是说对地图着色,用五种颜色就够了。后来,许多涉足此题的数学家全都一无所获。于是,人们开始认识到,这个貌似简单的猜想,其实是一个堪与费马猜想相媲美的难题。
入20世纪以来,科学家们对四色猜想的证明基本上是按照肯普的想法在进行。 1913年,美国著名数学家、哈佛大学的伯克霍夫在肯普的基础上,结合自己创新的技巧,证明了某些大的构形可约。
美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。 1950年,有人从22国推进到35国。
1960年,有人又证明了39国以下的地图可以只用四种颜色着色;随后又推进到了50国。
不过看来这种进展确实十分缓慢。
随着电子计算机演算速度的迅速提高,加之人机对话的出现,大大加快了证明四色猜想的进程。
1976年,在J. Koch的算法支持下,美国伊利诺斯大学的哈肯(Wolfgang Haken) 在1970年着手改进“放电过程”,后与阿佩尔(Kenneth Appel) 合作编制了一个很好的程序。他们于1976年6月在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿判断,终于完成了四色定理的证明。
五、 四色问题的后续
四色猜想的计算机证明,轰动了世界。它不仅解决了一个历时100多年的难题,而且有可能成为数学史上,采用计算机证明数学定理的奠基之作。这是一百多年来吸引许多数学家与数学爱好者的大事,当两位数学家将他们的研究成果发表的时候,当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳,以庆祝这一难题获得解决。
一个多世纪以来,在“四色猜想”的研究证明过程中,不少新的数学理论随之产生,也发展了很多数学计算技巧。如将地图的着色问题化为图论问题,丰富了图论的内容,所引进的概念与方法刺激了拓扑学与图论的生长、发展。不仅如此,“四色猜想”在有效地设计航空班机日程表,设计计算机的编码程序上都起到了推动作用。
地图四色猜想是第一个主要由计算机完成证明的数学难题。尽管这一证明,由于不能由人工直接验证,而且也缺乏数学通常的解题规范,目前尚未被所有的数学家接受。人们并不满足于计算机取得的成就,他们认为应该有可能存在一种更加简捷明快的书面证明方法。所以直到现在,仍然有不少的数学家和众多数学爱好者都在寻找更简洁的证明方法。
六、 四色问题之小插曲
接下去的戏就得由闵可夫斯基来演了。
令闵可夫斯基尴尬的一堂课
闵可夫斯基
19世纪末,德国有位天才的数学教授叫闵可夫斯基,他曾是爱因斯坦的老师。爱因斯坦因为经常不去听课,便被他骂作“懒虫”。万万没想到,就是这个“懒虫”后来创立了著名的狭义相对论和广义相对论。闵可夫斯基受到很大震动,他把相对论中的时间和空间统一成“四维时空”,这是近代物理发展史上的关键一步。
在闵可夫斯基的一生中,把爱因斯坦骂作“懒虫”恐怕还算不上是最尴尬的事„„ 一天,闵可夫斯基刚走进教室,一名学生就递给他一张纸条,上面写着:“如果把地图上有共同边界的国家涂成不同颜色,那么只需要四种颜色就足够了,您能解释其中的道理吗?”
闵可夫斯基微微一笑,对学生们说:“这个问题叫四色问题,是一个著名的数学难题。其实,它之所以一直没有得到解决,仅仅是由于没有第一流的数学家来解决它。” 为证明纸条上写的不是一道大餐,只是小菜一碟,闵可夫斯基决定当堂掌勺,问题就会变成定理„„
下课铃响了,可“菜”还是生的。一连好几天,他都挂了黑板。后来有一天,闵可夫斯基走进教室时,忽然雷声大作,他借此自嘲道:“哎,上帝在责备我狂妄自大呢,我解决不了这个问题。”
他虽然没有成功,可自认第一流倒也并非自不量力。要知道,19世纪末20世纪初,德国格丁根大学能成为世界数学中心,就是由于他和希尔伯特、克莱因“三巨头”的努力。四色瘟疫在英国蔓延时,还真没有一个研究过它的数学家比得上闵可夫斯基。