四色问题四色ppt课件.pptx

《四色问题四色ppt课件.pptx》由会员分享，可在线阅读，更多相关《四色问题四色ppt课件.pptx（14页珍藏版）》请在三一办公上搜索。

1、费尔马大定理 四色问题 哥德巴赫猜想,世界数学三大猜想,任一不小于6之偶数，都可以表示成两个奇质数之和；任一不小于9之奇数，都可以表示成三个奇质数之和。 陈景润证明了1+2成立，即任何一个大偶数都可表示成一个素数与另一个素因子不超过2个的数之和。,费尔马大定理,四色问题 内容：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。” 数学语言：将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。 （相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。）,四色猜想的提出: 英国

2、毕业于伦敦大学的弗南西斯格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。他和在大学读书的弟弟格里斯决心试一试,可是研究工作没有进展。 著名数学家奥古斯都德摩根也没有能找到解决这个问题的途径，著名数学家威廉哈密顿对四色问题进行论证。但直到1865年哈密顿逝世为止，问题也没有能够解决。 18781880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。,肯普的证明： 正规地图和非正规地图：首先指出如果没有一个国家包围其他国家，或没有

3、三个以上的国家相遇于一点，这种地图就说是“正规的” 否则为非正规地图。 一张地图=正规地图+非正规地图，但非正规地图所需颜色种数一般不超过正规地图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正规地图是五色的，要证明四色猜想成立，只要证明不存在一张正规五色地图就足够了。 归谬法证明：大意是如果有一张正规的五色地图，就会存在一张国数最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻国数少于六个，就会存在一张国数较少的正规地图仍为五色的，这样一来就不会有极小五色地图的国数，也就不存在正规五色地图了。这样肯普就认为他已经证明了“四色问题”，但是后来人们发现他错了。,1890年，

4、在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。不久，泰勒的证明也被人们否定了。 人们发现他们实际上证明了一个较弱的命题五色定理。就是说对地图着色，用五种颜色就够了。 后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。 不过肯普的证明阐明了两个重要的概念: “构形” “可约性”,构形：他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻国，不存在每个国家都有六个或更多个邻国的正规地图，也就是说，由两个邻国，三个邻国、四个或五个邻国组成的一组“构形”是不可避免的，每张地图至少含

5、有这四种构形中的一个。 “可约”性:“可约”这个词的使用是来自肯普的论证。他证明了只要五色地图中有一国具有四个邻国，就会有国数减少的五色地图。 自从引入“构形”，“可约”概念后，逐步发展了检查构形以决定是否可约的一些标准方法，能够寻求可约构形的不可避免组，是证明“四色问题”的重要依据。但要证明大的构形可约，需要检查大量的细节，这是相当复杂的。,进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行：1913年美国伯克霍夫：肯普的想法+新的设想证明了某些大的构形可约1939年美国数学家富兰克林证明了22国以下的地图都可以用四色着色 1950年 ，有人从22国推进到35国1960年

6、，有人又证明了39国以下的地图可以只用四种颜色着色随后又推进到了50国这种推进仍然十分缓慢。 高速数字计算机的发明，促使更多数学家对“四色问题”的研究。从1936年就开始研究四色猜想的海克，公开宣称四色猜想可用寻找可约图形的不可避免组来证明。,对偶图：把每个国家的首都标出来，然后把相邻国家的首都用一条越过边界的铁路连接起来，除首都(称为顶点)及铁路(称为弧或边)外，擦掉其他所有的线，剩下的称为原图的对偶图。 到了六十年代后期，海克引进一个类似于在电网络中移动电荷的方法来求构形的不可避免组。在海克的研究中第一次以颇不成熟的形式出现的“放电法”，这对以后关于不可避免组的研究是个关键，也是证明四色定

7、理的中心要素。 电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。美国伊利诺大学哈肯在1970年着手改进“放电过程”，后与阿佩尔合作编制一个很好的程序。 1976年6月，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界。,几何证明： 在平面地图中，为了区分相邻的图形，相邻图形需要使用不同的颜色来上色，与这两个相邻图形都有邻边的图形需要使用第三种颜色 我们先假设四色定理成立，根据四色定理得出在一个平面内最多有四个互有邻边的图形，而因为第四个与三个互有邻边的图形都会包围一个图形，所

8、以一个平面内互有邻边的图形最多有四个，所以四色定理成立（互有邻边，举例： 三个互有邻边的图形A和B有邻边 C和AB都有邻边）,实际应用 虽然任何平面地图可以只用四个颜色着色，但是这个定理的应用是有限的 现实中的地图常会出现飞地，即两个不连通的区域属于同一个国家的情况（例如美国的阿拉斯加州），而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种情况下，只用四种颜色将会造成诸多不便。 实际中用四种颜色着色的地图是不多见的，而且这些地图往往最少只需要三种颜色来染色。此外，即便地图能够只用四种颜色染色，为了区分起见，也会采用更多的颜色，以提示不同地区的差别。,“四色问题”的被证明仅解决了一个历时100多年的难题，而且成为数学史上一系列新思维的起点。 在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。 不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。 不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍由不少数学家和数学爱好者在寻找更简洁的证明方法。,宇宙之大，粒子之微，火箭之速，化工之巧，地球之变，生物之谜，日用之繁，无处不用数学 华罗庚,