四色猜想-四色猜想 四色定理.doc

四色猜想-四色猜想四色定理

地图四色定理(Four color theorem)最先是由一位叫古德里Francis Guthrie的英国大学生提出来的。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示即“将平面任意地细分为不相重叠的区域每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”也就是说在不引起混淆的情况下一张地图只需四种颜色来标记就行
发展历史
不过情况也不是过分悲观。数学家希奇早在1936年就认为讨论的情况是有限的不过非常之大大到可能有10000种。对于巨大而有限的数,最好由谁去对付?今天的人都明白:计算机。
从1950年起希奇就与其学生丢莱研究怎样用计算机去验证各种类型的图形。这时计算机才刚刚发明。两人的思想可谓十分超前。
1972年起黑肯与阿佩尔开始对希奇的方法作重要改进。到1976年他们认为问题已经压缩到可以用计算机证明的地步了。于是从1月份起他们就在伊利诺伊大学的IBM360机上分1482种情况检查历时1200个小时,作了100亿个判断最终证明了四色定理。在当地的信封上盖“Four colorssutfice”四色,足够了的邮戳就是他们想到的一种传播这一惊人消息的别致的方法。
人类破天荒运用计算机证明著名数学猜想应该说是十分轰动的。赞赏者有之,怀疑者也不少,因为真正确性一时不能肯定。后来也的确有人指出其错误。1989年,黑肯与阿佩尔发表文章宣称错误已被修改。1998年托马斯简化了黑肯与阿佩尔的计算程序但仍依赖于计算机。无论如何四色问题的计算机解决给数学研究带来了许多重要的新思维。
问题影响
一个多世纪以来,数学家们为证明这条定理绞尽脑汁,所引进的概念与方法刺激了拓扑学与图论的生长、发展。在“四色问题”的研究过程中,不少新的数学理论随之产生,也发展了很多数学计算技巧。如将地图的着色问题化为图论问题,丰富了图论的内容。四色猜想不仅如此,“四色问题”在有效地设计航空班机日程表,设计计算机的编码程序上都起到了推动作用。
实际应用
虽然任何平面地图可以只用四个颜色着色,但是这个定理的应用却相当有限,因为现实中的地图常会出现飞地,即两个不连通的区域属于同一个国家的情况,而制作地图时我们仍会要求这两个区域被涂上同样的颜色,在这种情况下,只用四种颜色将会造成诸多不便。
实际中用四种颜色着色的地图是不多见的,而且这些地图往往最少只需要三种颜色来染色。此外,即便地图能够只用四种颜色染色,为了区分起见,也会采用更多的颜色,以提示不同地区的差别。
四色原理的一种逻辑证明
地图上任何一个区域必将存在邻域,且又通过邻域与其他非邻域发生间接联系,我们可以将任何一个地图以图论图形的表示出来。
假