最终被计算机所证明的百年数学难题——四色定理

和费马大定理，庞加莱猜想一样，四色定理也是那种叙述起来非常简单，证明起来却极其困难的百年数学难题。但四色定理非常特殊的一点在于，它的最终证明并不是传统的数学逻辑证明，而是借助计算机分析所有可能的情形后完成的。这也就是说，四色定理的证明迄今为止仍非单独的人力所能及，我们仍然没有找到理论上的逻辑证明，但借助计算机强大的计算能力，的确又可以解决这个难题。

四色猜想

四色猜想最早并不是由职业数学家提出的，而是由从事地图制作的费兰西斯.古色利（Francis Gurthire）发现的。在为不同的地图着色过程中，细心的古色列发现，对于相邻(具有公共边界)的地区，若它们着不同颜色，那么只要四种颜色就可以完成这张地图。好奇心强烈的古色列对这个猜想的正确性非常感兴趣，但苦于自己不具备专业的数学知识，于是他将这个问题告诉了自己在伦敦大学学数学的弟弟费雷德里克·古色利（Frederick Guthrie），但弟弟也无能为力，后来他又寻求老师，著名数学家德·摩根(de Morgan,1806~1871，提出了集合论中著名的德·摩根定律)的帮助。但令兄弟二人震惊的是，即使是德·摩根这样出色的数学家也对这个问题无能为力。

德·摩根

但德·摩根算得上是四色猜想的第一位先驱，实际上他证明了至少需要四种颜色，并且因此留下了关于四色猜想最早的正式文字记录。同样，德·摩根向许多当时著名的数学家咨询过这个问题，但都一无所获，直到英国著名数学家凯莱(Arthur Cayley，1821～1895，矩阵论创始人)在1878年向伦敦数学会提交这个问题后，四色猜想才开始广为人知，并吸引了众多数学家来研究这个问题。

凯莱

在凯莱正式向数学界提出四色猜想后不到一年时间内，毕业于剑桥大学数学系的律师肯普(Kempe)给出了一个看似正确的证明，但直到十一年后，希伍德(Heawood)才发现了肯普证明中的错误，由此证明四色猜想的努力再次破产。但肯普的证明并不是一无是处，实际上，希伍德利用肯普的方法，成功证明了五种颜色的情形，迈出了实质性的一步。作为研究四色猜想的先驱，肯普和希伍德留下的思想和方法贯穿了之后整个四色猜想的研究过程，并且还深刻影响了图论这门数学学科的发展。

进入20世纪后，对四色猜想的研究并没有取得理论上的突破，数学家所采用的的仍然是来自肯普和希伍德的思想，即“肯普链”和构造极小反例。1922年，富兰克林证明了25个区域情形时的四色猜想，自此之后，数学家们利用越来越复杂的技巧艰难地提高数目，但直到60年代，这个数字才不过96而已。

四色定理

到了70年代，数学界已经意识到，盲目地提升使得四色猜想成立的区域数目对于最终的证明意义不大，必须寻求理论上的突破才行。为此，德国数学家希什(Heesch)提出了可约化构形的概念，其核心思想就是将区域数目想办法减少，把无限多的情形化简为有限的情况，这一概念成为最终证明的关键。

希什曾经猜测不可约构形数目的上限可能是一万，也就是说，挨个验证差不多一万种不同的情况就能证明四色猜想，但如此庞大的计算量在当时几乎不可能完成。而为了有效地减少计算量，希什模仿电路中移动电荷放电的过程，引入了“电荷法”，从而使得极其复杂的计算成为可能。万事俱备，只欠东风，但可惜的是，希什本人并未完成最终的证明，但放眼整个四色猜想的证明，希什无疑是至关重要的人物。

不久之后，阿佩尔(Appel)和哈肯(Haken)在希什的基础上，创造性地改进了电荷法，重点着眼于那些看上去不可能可约的构形，然后重新设计放电算法以排除这些特殊构形。同时，随着计算机的兴起，他们所设计的计算过程也成为可能。最终在1976年，他们找到最终的1482种可能，并且借助当时的IBM360计算机，运行长达1200个小时后，验证了所有可能的情况，在历史上首次得到了四色猜想的证明！自此四色猜想成为四色定理。

四色定理之后

尽管如今我们已经公认阿佩尔和哈肯的计算证明过程是对的，但他们的证明在当时却引发了数学界的轩然大波，甚至是质疑。他们的所有证明和计算过程，完全写出来居然超过了700页，并且由于计算过程太过复杂，已经超过了人力所能理解的范围，以至于许多人对这样的证明产生怀疑。

之后一二十年，随着计算机的快速发展，计算能力有了质的飞跃，于是又有数学家致力于简化四色猜想的证明。1994年，数学家西缪尔(Seymour)所领导的团队全面革新了阿佩尔和哈肯的思想和方法，极大地简化了原来的计算过程，最终只在计算机上运行了24小时就检验了所有情形而完成了证明。更重要的是，此次的计算过程已经简化到人力可以检验的标准，至此，四色猜想证明中受质疑的地方被彻底解决！为此西缪尔受邀在1994年的国际数学家大会上做了一小时的全会报告。

数学总是寻求事物最简洁的关系，而四色定理如此依赖于计算，这显然不符合数学家们的理想，以至于有数学家说过：好的数学证明应优美如诗，但四色定理这样的证明就像一本电话簿一样枯燥。尽管在此之后还出现过更为简单的证明，但都没有脱离借助计算机的范围，迄今为止，数学家还未找到四色定理的纯粹数学证明，但我们相信，随着数学理论的深刻发展，将来很有可能将出现这样的纯粹证明。

结语

四色定理是图论这门学科里最经典的研究对象，实际上对四色定理一百多年的研究深刻影响了图论的发展，在这个过程中所发展出来的思想方法的价值甚至超过了定理本身，图论专家鲍耐特为此曾说道：虽然四色定理已经被证明，但数学家们在许多未成功的尝试中所发展出来的思想方法将具有永恒的价值。一个好的数学问题往往可以影响甚至创造一个学科，而四色定理正是这样一个极具价值的问题，而关于四色定理的价值，我们借用现代图论之父塔特(Tutte,1917~2002)的话来说就是：四色问题是数学中的冰山一角，楔之尖端，孟春一啼。