浅析四色猜想的证明.doc

浅析四色猜想的证明 学生姓名：杨彩娟 指导老师：冯源 摘 要 四色定理是世界三大数学难题之一，许多数学家多年来都热衷于它的证明，力求寻找更好的非计算机证明方法，而四色猜想的讨论和证明也大大推动了图论的发展。 关键词： 图论； 四色猜想； 四色证明； 可约化构形 引言： 在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻国家的颜色不同。这样的着色效果能使每一个国家 能清楚地显示出来。但要证明这个结论却是一个著名的世界难题，最终借助计算机才得以解决，之后诸多数学学者都在寻找其严格数学证明方法。 图论是当今数学中较为发达的一门学科，它被广泛应用于道路交通、通讯工程、经营管理等诸多领域，如今图论还衍生出网络理论这种新生事物。世界上许多事物以及它们之间的联系都可以用图形来直观表示，这时人们所研究的对象往往用结点表示事物，用边表示它们之间的联系。这种由结点和边构成的图形就是图论里研究的平面图，而其与平面几何中的图不相同,这里只关心图中有多少个点,点与点之间有无连线,至于连线的方式是直线还是曲线,点与点的相对位置如何,都是无关紧要的。总之,这里所讲的图是反映对象之间关系的一种工具。在图的理论研究和实际中,图的平面化问题具有非常重要的意义，而四色猜想的讨论大大推动了图论的发展。 地图是我们生活中不可或缺的一项实用工具。在绘制地图时相邻区域最好涂上不同的颜色以示区别，而这样的结果只会使地图看起来花花绿绿，然而实际上只需要四种颜色就能保证相邻两个地区颜色不重复。这就是著名的四色猜想（也称作四色问题）。 英国青年弗朗西斯·葛斯瑞于1852年在给一张英国地图着色时发现了四色问题，但之后很多人都无法解释这个问题。直到英国数学家凯莱于1878年在皇家学会上正式提出并在《皇家地理学会会报》上发表，这才使得四色问题得到广泛关注。随后各国数学中心和数学杂志都收到大量的证明，正像许多这种提法简单而证明极为困难的大猜想一样，许多的证明完全是错的。到了1890年，剑桥大学三一学院的毕业生肯普在《美国数学杂志》上发表的四色猜想的证明被数学大师希伍德指出有漏洞，尽管四色猜想没有得到证明，但肯普和希伍德两位数学大师对于后来图论的发展做出了决定性的贡献。迄今为止，四色猜想仍然是电脑证明数学难题绝无仅有的例子，但它昭示了计算机证明时代的到来，它也可能成为数学上一系列新思维的起点，四色猜想同时也是第一个应用计算机辅助证明的大定理，但主导整个证明过程的仍然是数学家。四色猜想看起来是一个带有数学游戏性质的孤立问题，但它创造出图论许多新的分支。证明四色定理也需在概念上下功夫，特别是需要寻找可约化的构形，即把复杂的事物变成简单的对象，把区域多的问题简化为区域少的情形。那么四色问题可以做这样的化简：一个区域不妨看成一个点，任何两个区域或者相邻或者不相邻。如果代表两个区域的点相邻，那么我们就在两点之间连上一条线，否则就不连线。这样的结构就称作图。这时四色问题也就变成图的顶点着色问题，也就是两顶点如果有线相连，就必须涂上不同的颜色。任意一个图，它可能的最小着色数称为它的色数。20世纪60年代，证明四色猜想的构型大约有8000到10000个，这在当时用计算机是办不到的。后来阿沛尔与哈肯利用计算机进行有哪些信誉好的足球投注网站，发现构型不到2000个，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这一难题获得解决。它不仅解决了一个历时100多年的难题，而且有可能成为数学史上一系列新思维的起点。不过也有不少数学家并不满足于计算机取得的成就，他们还在寻找一种简捷明快的书面证明方法1：任何直达的（直接相连接的）两点，必须采用不相同的颜色。（注：本文均采用“点着色”的方法） 公理 2：任何不能直达的两点可以采用相同的颜色着色。 公理3：在“平面”或“球面”上任何一个“封闭圈”（指若干条首尾相连的“线”所构成的图形）都可将“平面”或“球面”“分断隔离”成为不能直达的两部份，即这一部份内（即这个“圈”内）的点必须经过“封闭圈”（以后简称为“圈”）上的点才能到达另一部份内（即这个“圈”外）的点（在着色问题中，“线”与“线”之间是不能交叉的。因为如果“线”与“线”之间交叉则它们显然不能处于同一“平面”或“球面”上了。 公理 4：在“环面”（形如普通的救生圈）上有些“封闭圈”是不能起到“分断隔离”的作用的。即“圈”一侧的“点”可以不必非要通过“圈”上的点就可以到达“圈”的另一侧的点。（这种“环面”实际上是“七可