| 词条 | 四色定理 |
| 释义 | § 问题的发现 （下图是上下对折，再左右对折形成一个轮胎，有7个区域两两相连，即7色定理，外国数学家构造）因为：Np=[(7+√1+48p)/2].当p=1时，N1=7。一个多世纪以来，数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken）宣告借助电子计算机获得了四色定理的证明，又为用计算机证明数学定理开拓了前景。 毕业于伦敦大学的弗南西斯·格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。 § 内容 四色定理四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。” 这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。 20世纪80-90年代中国曾邦哲从系统论观点（结构论）将其命题转换为“四色定理”等价于“互邻面最大的多面体是四面体”的问题。 § 曲折的证明历程 著名数学家哈密尔顿对“四色猜想”产生了极大的兴趣，经过长达13年的努力，直到1865年去世，其研究工作依然毫无结果。 四色猜想刚被提出时，并没引起很大的注意，许多数学家低估了它的难度。爱因斯坦的老师闵可夫斯基是著名的数论专家，也是一位非常谦虚的人。他曾认为四色猜想的证明并不复杂，其所以一直没有获得解决，仅仅是因为当时世界上一流的数学家没有研究它。有一次给学生上课时，偶然谈到了这个猜想，他说可以给出证明，并试图当堂证给学生看。可是他证得满头大汗，却是一筹莫展，只好第二次上课时接着证。一连几堂课，费尽九牛二虎之力，仍然证不出来。有一次，证明时正好天下大雨，雷声震耳，他惭愧地对学生说：“老天在责备我讲大话了，我证明不了四色猜想。” 此后，许多数学家都曾声称给出了这个猜想的证明，但后来逐渐都被发现其证明是有毛病的。这样，四色问题就成了世界上著名的难题之一。一百多年来，没有人能证明它成立，也没有人能举出反例来推翻它，它使数学家们深受困扰。 § 计算机解决了问题 1879年，肯普曾宣布他证明了四色问题。他的证明虽然在11年后被数学家赫伍德否定了，但是人们认为他的证明思路，有很多可取之处。20世纪以来，许多人一直在继续按照他的思路，推进着四色问题的证明工作，并且取得了不少成就。可惜这些成就所提供的检验方法太复杂，人们难以实现。例如有人在 1970年设计的方案，用当时的计算机来算，也需要连续不断地工作十万个小时，也就是说，要连续不断地计算11年以上，才能得出结论，所以难以证实。 之后，人们又大大地改进了证明方案，而且计算机的能力及其使用方法也有了飞快的进步，为机器证明四色猜想创造了条件。 本世纪70年代中期，美国伊利诺斯州立大学的数学家阿佩尔和哈肯独树一帜，利用高速计算机对 “四色猜想”进行证明。他们运用了一种“不可避免性”理论，从一万多张地图中挑选了近两千张上机检验，对每一张地图都使用了二十万种可能的方法着色，计算机作了两百亿个逻辑判定，经过1200小时的计算，终于在1976年6月证明了这个数学名题。伊利诺斯数学杂志的审稿人，对阿佩尔与哈肯证明的审查，也是通过计算机来实现的。 阿佩尔与哈肯的工作，使延续了124年之久的四色问题得到证明，成为四色定理。计算机在证明数学难题方面立下了功勋。这一成果轰动世界，引起了极大的反响。 四色定理本身没有多少实用价值，人们可以用四种颜色绘制地图，也可用更多的颜色区分填充。但它曲折的证明历程使人深思，激发人们敢于面对困难，迎接挑战，去探索问题的真谛。美国数学家的贡献主要不在于证明四色定理本身，而在于用计算机解决了人们多年来无法解决的理论问题。它表明，靠人与机器合作，有可能完成连最著名的数学家至今也束手无策的工作，标志着人类认识能力的一个飞跃，极大地推动了以计算机为基础的人工智能的发展。目前，尚有一些问题留待人们去解决：已有的证明能不能简化？可不可以不用计算机而给出证明？这些问题仍吸引着有志者继续进行探索。 § 证明 定理：用4种颜色可以给任一平面简单连通图G=〈V,E〉正常着色。 图1证:对图的顶点数n作归纳。 当n<5时,显然成立。假设n-1个顶点时成立,现证明n个顶点时也成立。由于图G至少存在一顶点其度数d(v0)≤5(见欧拉定理推论证明略)。在图G中删去度数最小的一点v0 得图G-{v0},由归纳假设知该图可用4种颜色正常着色。然后将v0又加回去,有三种可能: 1、 d(v0)＜4、d(v0)=4或d(v0)=5但和v0邻接的点着的颜色数小于4。则v0极易着色,只要选与四周顶点不同的颜色着色即可。 2、d(v0)=4且和v0邻接的4点着的颜色数为4, 如图1所示v0与v1、v2、v3、v4依次相邻，v 1- v 4分别着以颜色1、2、3、4。 图2 图3 如从v1到v3存在由颜色1及颜色3组成的13链（如图2），那么就不存在v2到v4的24链，于是可以将包含v2的所有24链子集中的颜色2与颜色4互换，此时不会改变v4及v1、v3的着色（如图3），这样可将v0着以颜色2即可，定理成立。 、 图4 如从v1到v3不存在由颜色1及颜色3组成的13链，那么可以将包含v1的所有13链子集中的颜色1与颜色3互换，此时不会改变v3及v2、v4的着色（如图4），这样可将v0着以颜色1即可，定理成立 图5 3、d(v0)=5且和v0邻接的5点着的颜色数为4, 如图5所示v0与v1、v2、v3、v4、v 5依次相邻，v 1- v 4分别着以颜色1、2、3、4，v 5只可能着以颜色2或3（结构都是一样的，在此我们不防设为2）。 图6 图7 如 v1到v3不存在由颜色1及颜色3组成的13链 或者v1到v4不存在由颜色1及颜色4组成的14链， 那么可以将包含v1的所有13链子集中的颜色1与颜色3互换（如图6），此时不会改变v3及v2、 v4、v5的着色。 或者可以将包含v1的所有14链子集中的颜色1与颜色4互换（如图7），此时不会改变v4及v2、v3、v5的着色，这样均可将v0着以颜色1即可，定理成立 图8 如 v1到v3存在由颜色1及颜色3组成的13链 而且v1到v4存在由颜色1及颜色4组成的14链如图8， 图9那么就不存在v2到v4的24链而且也不存在v5到v3的23链， 于是可以将包含v2的所有24链子集中的颜色2与颜色4互换，此时不会改变v4及v1、v3、v5的着色，将包含v5的所有23链子集中的颜色2与颜色3互换，此时不会改变v3及v1、v2、v4的着色（如图9）； 这样可将v0着以颜色2即可，定理成立。 证毕。 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。