选修课之四色问题.ppt

四色问题四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”

四色问题也称四色猜想或四色定理，是世界近代三大数学难题之一(另外两个是费马大定理和哥德巴赫猜想)。用数学语言表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”（这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。）
一、四色问题的诞生

四色问题，1852年最先是由一位叫古德里的英国大学生提出来的。
古德里在给一张英国地图着色时猜测：为给任意一张平面地图着色，并使任何具有公共边界线的区域的颜色不同，至多需要4种颜色。
他就请教自己的老师、著名的数学家德摩根，希望帮助找到证明，但是德摩根也不能证明。
德摩根主要在分析学、代数学、数学史及逻辑学等方面作出了重要的贡献。他的工作，对当时19世纪的数学具有相当的影响力。德摩根不能证明四色问题转而请假发明四元数的哈密顿，但是没有引起哈密顿的重视。
1823年7月7日，哈密顿以入学考试第一名的成绩进入著名的三一学院。
1823到1824年间他完成了多篇有关几何学和光学的论文，其中1824年12月送交爱尔兰皇家科学院会议的有关焦散曲线的论文，引起科学界的重视。
1827年6月10日，年仅22岁的哈密顿被任命为敦辛克天文台的皇家天文研究员和三一学院的天文学教授．
1832年，哈密顿成为爱尔兰皇家科学院院士。

二、四色问题的提出

1878年，英国当时最著名的数学家凯莱对此问题进行一番思考后，相信这不是一个可以等闲视之的问题，于是在《伦敦数学会文集》上发表了一篇《论地球着色》的文章，他的文章掀起了一场四色问题热。凯莱令闵可夫斯基尴尬的一堂课三、四色问题的证明

1879年一位叫肯普的英国律师宣称证明了四色问题，他的论文发表在《美国数学杂志》上，但是11年后，一位叫希伍德的青年指出肯泊证明中的严重错误。
希伍德对肯泊的方法作了适当的补救后，用它证明了五色定理。他一生坚持研究四色问题，但始终未能证明这条定理。
四色问题的证明

肯普的证明是这样的：
如果没有一个国家包围其他国家，或没有三个以上的国家相遇于一点，这种地图就说是“正规的”（左图）。如为正规地图，否则为非正规地图（右图）。
四色问题的证明

一张地图往往是由正规地图和非正规地图联系在一起，但非正规地图所需颜色种数一般不超过正规地图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正规地图是五色的，要证明四色猜想成立，只要证明不存在一张正规五色地图就足够了。
肯普是用归谬法来证明的，大意是如果有一张正规的五色地图，就会存在一张国数最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻国数少于六个，就会存在一张国数较少的正规地图仍为五色的，这样一来就不会有极小五色地图的国数，也就不存在正规五色地图了。
这样肯普就认为他已经证明了“四色问题”，但是后来人们发现他错了。不过肯普的证明阐明了两个重要的概念，对以后问题的解决提供了途径。四色问题的证明

第一个概念是“构形”。他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻国，不存在每个国家都有六个或更多个邻国的正规地图，也就是说，由两个邻国，三个邻国、四个或五个邻国组成的一组“构形”是不可避免的，每张地图至少含有这四种构形中的一个。另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。
他证明了只要五色地图中有一国具有四个邻国，就会有国数减少的五色地图。自从引入“构形”，“可约”概念后，逐步发展了检查构形以决定是否可约的一些标准方法，能够寻求可约构形的不可避免组，是证明“四色问题”的重要依据。但要证明大的构形可约，需要检查大量的细节，这是相当复杂的。11年后，即1890年，在牛津大学就读的年仅29岁的希伍德以自己的精确计算指出了肯普在证明上的漏洞。

他指出肯普说没有极小五色地图能有一国具有五个邻国的理由有破绽。人们发现他们实际上证明了一个较弱的命题——五色定理。就是说对地图着色，用五种颜色就够了。
后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。
进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。
1913年，美国著名数学家、哈佛大学的伯克霍夫利用肯泊的想法，结合自己新的设想；证明了某些大的构形可约。
后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了