全程干货四色定理(四色定理证明出来了吗)

人类并不是智慧，只是被智慧经过的风景

 

独立思考是突破颜值文化的唯一出路

古哥古点 2015年11月30日《四色定理和机器证明》四色定理大概算得上是那种知名度最高的数学界的至尊难题了，因为题面很容易理解最通俗的讲法是给一张地图上色，结果你会发现如果要保证任何两个接壤的国家不同色，整个地图用四种颜色就足够了。

在数学上，具体来说是在数论领域还有更严谨的对四色定理的定义，即在平面图上，为所有顶点着色，只需不超过四种颜色即可确保任何一条边不会连接两个同色顶点四色定理出名还有一个原因，就是它是世界范围内第一个广为人知的无赖式证明，也就是说它不是完全凭借数学家的巧妙构思而是硬证出来的。

研究者只把题目的证明进度推进到了一个需要极大量运算来逐个验证的程度，到这就摞挑子了，不干了反正，这里面对的极大量不像有些问题那样极大到了上穷碧落下黄泉也算不完的程度，花大量时间还是可以算的，那干脆就交给计算机硬扛，愣是让机器把这些枚举验证工作给做完了，输出结果是四色定理成立。

所以到现在为止，虽然越来越多的研究者都承认这种机器证明的合法性，毕竟人们已经用好几种不同方式各自独立的进行了机器验证，可仍然有相当数量的人类证明至上主义者是不承认这个结果的，所以它们仍然称之为四色猜想而不是四色定理。

四色猜想最早登场是1852年，一个叫弗朗西斯·古思里（Francis Guthrie）的人在给英格兰地图上色时提出了这个问题，他当时就注意到让各个连接区块用不同颜色加以区分，总共使用四种色彩就够了从伦敦大学毕业后不久，他继续学习法律。

这时，他的弟弟弗雷德里克·古思里（Frederick Guthrie）已经成为著名数学家奥古斯特·德·摩根（August De Morgan）的学生弗朗西斯（Francis）向弗雷德里克（Frederick）分享了他最初的观察以及他徒劳无功的证明尝试，要求弗雷德里克，也邀请其老师德·摩根共同思考这个问题。

事实证明，德·摩根立即被吸引住了，但是他无法给出答案1852年10月23日，他对爱尔兰著名数学家和天文学家威廉·汉密尔顿（William Hamilton）写了如下内容：“我的一名学生今天要我给他关于一个事实的成立原因，可实际上我当时并不知道这是否是事实，且到现在也还不知道。

他说，如果任意的分割一个图形并且为各个部分着色，使具有公共边界的任何区域都具有不同的颜色-这可能需要四种色彩，但不会更多-以下是一个需要四种颜色的例子……无法创造出需要五种颜色的必要性如果你能找出一个简单反例来反驳的话，这会令我像一个愚蠢的动物，我想我一定会像斯芬克斯那样去做……。

”德·摩根（De Morgan）在信尾的自嘲幽默实际上反映出这个问题带来的一种神奇的迷惑感，这和大多数人对它的第一印象相吻合无论如何，现在这个问题开始走进这个时代最杰出的数学家们的视野，它像野火一样迅速蔓延，并开启了对此猜想的证明竞赛。

大约又过了三十年，一个叫亚瑟·凯利（Arthur Cayley）的人对这个看起来颇为简单的问题仍旧悬而未决感到惊讶他在参加伦敦数学协会的一次会议时，当会议进行到一半，他问与会人员是否有人找出了解决方案由于没有人愿意去尝试，回家后他开始直面这个挑战。

不到一年，即1879年，凯利就返回了伦敦并向皇家地理学会提交了一份名为《地图着色》的小册子他并没带来确切的证明，但是提供了他的一些思考和对自己失败方法的总结，这些线索实际上大幅推进了迟滞已久的四色问题或许这里面最有价值的是他创造的一个反诘性思路：假设某幅地图已经成功用四色进行了染色，现在再添加另外一个区域，那么还能够保持相同的颜色方案吗？。

下一个登场的也是一位伦敦律师，名叫阿尔弗雷德·坎普（Alfred Bray Kempe）坎普在剑桥跟随凯利学习数学，他尝试用了不可能的方法获得了令人吃惊的丰硕成果1879年7月上旬，坎普在《自然》杂志上宣称他证实了四色猜想。

坎普证明的核心依赖于一个已证明的定理，一种现在很常见的图论运算还有一种古老的处理手法证明关键在于一个已证明的事实，每个平面图至少含有一个顶点，其顶点度小于6所谓顶点的度就是连接一个顶点的边的条数根据这一认知，坎普通过不断删除或成块去掉包含四个或小于四个顶点的子图来进行操作。

为什么要去除四个或更少顶点的子图呢？因为每一块具有四个或更少顶点的子图毫无疑问肯定是满足四色性的抛开所有这些次级顶点（少于四个的顶点）后，继续寻找子图和着色，直到剩余原始图为止坎普证明的最大诀窍是他所发明的剩余子图着色技巧。

实际上坎普发现在很多情况下，根本都用不到四种颜色，甚至两种就够了坎普的方式有点类似于现在计算机科学中的启发式算法，就是先按照一般性规则优先的处理大片任务，其余未被覆盖的的或特异的部分再另行处理具体来说，他发明了被称作“坎普链”的涂色方案。

就是像串羊肉串一样，一块瘦的，一块肥的，间隔着安排色块例如染中国地图，先把黑吉辽一路向下经中南六省区贯穿的这个序列看做一个串，用“坎普链”方法染色凡是没有被主链碰到的省区就新开另一条支链继续沿用坎普链填色。

直到坎普链开不动了，假如还有未被染色的剩余，再另行处理坎普就是用这种方法获得了他所声称的定理证明至少在十年内，他一直享受着这项创举带来的荣耀，甚至一度被册封为爵士可惜好景不长，坎普的定理还是被发现了错误。

1890年，英格兰的讲师珀西·海伍德（Percy John Heawood）发表了一份出版物，把四色定理重新打回到四色猜想海伍德本人并不能给出正确证明，所以他遗憾的写道：“这里的目标是毁设而非建设，因为它将指出广为接受的证明中存在的瑕疵。

”

地图上的坎普链不破不立，既然四色定理重回猜想状态，人们破解难题的热情重新高涨起来首先是美国数学家伯克霍夫（George David Birkhoff）做出了贡献，他通过找到某些大型可简化构型来限制坎普理论。

以此为基础，麻省理工学院的数学家菲利普·富兰克林对伯克霍夫的工作进行扩展，证明四色定理适用于所有具有25个以下顶点的图在接下来的1910到1950年代，研究者通过一系列合作，把这个可确保四色方案的顶点数目的上限不断推高，从而接近最终想要的一般性证明。

到1968年，四色定理的任何潜在反例已经被卡到41个顶点以上除了大型的可简化构型外，这些方法的一个重点是所谓的不可避免集合海因里希·海斯（Heinrich Heesch）发明了一种出名的被称为"卸载”的技巧，专门用于寻找不可避免集合。

因为看到了可简化构型和不可避免集合之间保持平衡的必要性，海斯可能是第一个公开表达了下面一种思路的数学家，即通过找出可简化构型的不可避免集合来证明四色猜想最后，同样重要的是，海斯还观察到，一个必要的集合最多可以包含上万个构型。

而要想用手动方式来计算证明这上万个场景，无疑是极为艰巨的任务幸运的是，计算机在此时应运而生，让高速计算称为可能，也为四色定理的证明带来了曙光然而早期计算机的能力是极为有限的，以一个顶点被围绕的顶点数目作为图构型复杂度的指标被称为环尺寸。

上世纪60年代的计算机最大的能力也不过可以处理环尺寸在12以下的图这对于整个证明来说是不够的但是作为最初的方法可行性验证，计算机进行辅助计算仍然意义非凡由于海斯自己不精通计算，他和一个叫卡尔·德（Karl Durre）的高中老师搭伙，在四色定理提出差不多一个世纪之后的1965年11月23日，他们利用一台汉诺威技术研究所的CDC1604计算机用一个月时间对一个此前未判定可简化性的环尺寸为9的未知构型进行了试算，结果证明这个算法非常有效。

当然，海斯马上意识到德国的计算资源是不足的，为此他多次前往美国寻求使用更大的计算机，但问题仍然没有得到解决渐渐地，海斯也失去了德国的资金支持海斯设法把自己的事业交棒给一位学生沃尔夫冈·哈肯（Wolfgang Haken），后者在一次讲座中对四色猜想产生了极大兴趣并下决心用一生来解决这个难题。

他和海斯重新努力，但奋斗了两年后，经费再次成为制约因素年事已高的海斯实在无力坚持，哈肯虽然热情犹在，但没有导师的情况下他也感到了迷失，他自己宣布：“现在我要退出了，我认为这是难以再超越的节点”恰在这个迷茫的关键时刻，一位疲惫的战士的信心重新被另一个新站出来的士兵所鼓舞。

这个伊利诺伊大学的数学家兼程序员叫肯斯·阿波（Kenneth Appel），当他听到哈肯打算放弃的消息后，表示愿意和哈肯一起结伴努力哈肯再度振作，终于在1976年，他们在反复检查了几百页的输出结果和长达1200小时的计算之后，终于借助当时强大的计算机完成了四色猜想的证明。

阿波选择的庆祝方式非常简单，他只是在系里的黑板上写下了这样一句话：“透过认真检查，看起来四种颜色足够了”此后，他们在数学会议上宣布了自己的结果，并将证明详细的进行整理与修改，最终他们的证明工作归结为对1936个构型例子的可简化性计算。

正如前面提到的一样，故事到这里没有结束，机器证明带来了众多质疑由于这每个构型的判断都涉及到最多50万次逻辑运算，谁能保证这当中机器不会出错呢？尽管，寻找简单的手工证明的努力还在继续，但更多的成果则集中在对机器证明运算量的简化。

最近的一个进展出现在1996年，尼尔·罗伯逊（Neil Robertson）、丹尼尔·桑德斯（Daniel Sanders）等人将待判断的例子数目降低到663个这当然是巨大的飞跃，但从性质上来说，它仍然是靠机器证明的而非人脑，所以它仍然无法解除怀疑论者的不安。

一个貌似简单地在画地图时信手拈来的问题后来表现出如此复杂，而最后竟然是用最简单的枚举计算加以解决从这简单到简单之间，无法安置的是许多人对于旁路人类智慧而得来的成果的焦虑或许正如数学史研究者戴维·伯顿（David Burton）所总结的一样：。

不能排除找到一个简短而令人信服的证明的可能，但也可以想见，唯一有效的证明必需涉及计算机协助下的大量计算如果是这种情况，我们必须承认已经出现了一种新的有趣的定理类型，它无法通过传统上被接受的方式加以验证承认这些定理的存在将意味着数学证明的安全性概念将要被修改。

人类并不是智慧，只是被智慧经过的风景。