四色问

2019-11-30 11:06:50

英国人格思里于1852年提出四色问题(fourcolourproblem，亦称四色猜想），即在为一平面或一球面的地图着色时，假定每一个国家在地图上是一个连通域，并且有相邻边界线的两个国家必须用不同的颜色，问是否只要四种颜色就可完成着色。
　　
　　1878年英国数学家凯莱重新提出这问题，引起人们关注。次年，英国数学家肯普提出用可约构形证明四色问题，虽然他的证明过程有漏洞，但为该问题的解决指出方向。1890年英国人希伍德沿着这方向证明了任何地图只用五种颜色着色便够了，取得初步进展。1913年美国数学家伯克霍夫发现一些新的可约构形。1968年挪威数学家奥雷等人证明了用四种颜色一定可以把不超过四十个国家的地图着色，推进了四色问题的研究。70年代初人们努力寻找可约构形中的不可免完备集，因为用它可以通过数学归纳法证明四色问题。1976年美国数学家哈肯和阿佩尔花了1200多小时的电子计算器工作时间，找到一个由1936个可约构形所组成的不可免完备集，因而在美国数学会通报上宣称证明了四色猜想。后来他们又将组成不可免完备集的可约构形减至1834个。
　　
　　四色问题的研究对平面图理论、代数拓扑论、有限射影几何和计算器编码程序设计等理论的发展起了推动作用。
　　

相关推荐