地图四色定理.doc

地图四色定理 ? 地图四色定理最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。德?摩尔根（A，DeMorgan，1806～1871）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明 四色定理的设想与感受。一个多世纪以来，数学家们为证明这条定理绞尽脑汁， 所引进的概念与方法刺激了拓扑学与图论的生长、发展。1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken）宣告借助电子计算机获得了四色定理的证明， 又为用计算机证明数学定理开拓了前景。以下摘录德?摩尔根致哈密顿信的主要 部分，译自J． Fauve1 and J.Gray（eds.），The History of Mathematics ：A Reader，pp． 597～598。 我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。 他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜 色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。现在的问题是是否会出现需要五种或更多种颜色的情形。就我目前的理解，若四 个不订分割的区域两两具有公共边界线，则其中三个必包围第四个而使其不与任 何第五个区域相毗邻。这事实若能成立，那么用四种颜色即可为任何可能的地图 着色，使除了在公共点外同种颜色不会 画出三个两两具有公共边界的区域ABC，那么似乎不可能再画第四个区域 与其他三个区域的每一个都有公共边界，除非它包围了其中一个区域（图2）。 但要证明这一点却很棘手，我也不能确定问题复杂的程度一对此您的意见如何 呢？并且此事如果当真，难道从未有人注意过吗？我的学生说这是在给一幅英国 地图着色时提出的猜测。我越想越觉得这是显然的事情。如果您能举出一个简单 的反例来，说明我像一头蠢驴，那我只好重蹈史芬克斯?的复辙了??。 研究过程 1852年10月23日，英国数学家摩尔根在一封信中提到这样一件事：有一 个学生格思里问他，为什么无论多么复杂的地图，都可以仅用四种颜色就能将相 邻的国家分开来？希望能在数学上给予证明，这样便出现了“四色定理” 。 “四色定理”提出后，并没有引起很大注意，很多数学家低估了它的难度， 就连以谦虚著称的数论专家明可夫斯基，在大学上拓扑课时也说四色问题之所以 一直没有获得解决，那仅仅是由于没有第一流数学家来解决它。他拿起粉笔，竟 要当堂给学生推导出来，结果挂了黑板，下一节他又去试，仍没成功。几个星期 后仍无进展。有一天凑巧他刚进教室，雷声大作，震耳欲聋，他马上对学生说： “上天在责备我自大，我也没发解决四色问题。”四色问题成了世界最著名的问 题之一。一百多年来，“四色定理”使数学家们深为困扰，没有人能证明它，也 没人推翻它。 1976年6月，世界名题“四色定理”获得证明，成了轰动一时的新闻。这 个定理获证的方法很特殊，它是由美国数学家阿沛尔和哈肯利用大型电子计算机 工作1200个小时才完成的。这些复杂的证明步骤，一个人即使一辈子连续工作 也是无法完成的。靠人与机器合作就有可能完成许多连最著名的数学家至今也缩 手无策的任务。因此，这个做法本身标致着人类认识能力的一个飞跃，大大推动 了以计算机为基础的人工智能的发展。