四色定理

来自计算思维百科
跳转至: 导航搜索

地图上为区分相邻国家、省、市等区域,会给其着不同的颜色。一张地图最少需要几种颜色着色?解决这一问题的答案是数学史上的著名难题—“四色定理”,它的证明是也用穷举法实现的。

四色定理('Four-Color Theorem),又称四色问题、四色猜想,是世界近代三大数学难题之一。四色定理最早是由一位叫古德里(Francis Guthrie)的英国大学生提出的,其内容是:“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”。用数学语言表示,即“将平面任意地细分为不相重叠的区域,每一个区域总可以用1、2、3、4这四个数字之一来标记,而不会使相邻的有公共边界的两个区域得到相同的数字。”。

著名数学家德·摩尔根(Augustus De Morgan)在1852年10月23日致哈密顿的一封信中首次提到了四色问题的来源,并在信中简述了自己证明四色定理的设想与感受。之后的一个多世纪,四色定理都未得到证明。最终在1976年,美国数学家阿佩尔(K.Appel)与哈肯(W.Haken)用穷举法借助电子计算机获得了四色定理的证明。他们在两台不同的电子计算机上,用了1200个小时,作了100亿判断,完成了四色定理的证明。证明由两部分组成,第一部分,利用以前确立的结果,加上一些数学推理,证明一般问题可以归约到证明有限个特例上;第二部分,用计算机程序产生了所有的特例(大约1700个例子),通过穷举,发现所有特例都是四着色的。