四色猜想的启示

在我们的生活中地图的重要性自然不用多说。可是，在绘制地图时，相邻的不同区域最好涂上不同的颜色以示区别。这样的地图看起来花花绿绿，只是不知你有没有注意过，不论一张地图上的行政区划有多么复杂，只要使用四种颜色着色，就可以保证将它们清清楚楚地区分开来(即任何相邻的两个地区颜色不会重复)。

　　这个问题到了数学家手里，就变成著名的四色猜想(也称四色问题)。数学家从节约的角度考虑，任何地图，使得相邻的地区涂上不同的颜色，至少得用多少种颜色呢?四色问题或者四色猜想的结论是：四色足够!

　　

　　百年拼搏史

　　

　　说起来，这个问题可能有许多人发现过，但是第一个明确记录在案的是刚从伦敦大学毕业不久的英国青年弗兰西斯·葛斯瑞。1852年，他给一张英国地图着色时发现，四种颜色足够。他于是猜想对任何地图也是如此。他把这个想法告诉正在伦敦大学学习的弟弟弗雷德里克，他弟弟当然解决不了这个问题，于是向他的老师、著名数学家德·摩尔根请教，他也不能解决这个问题，便于1852年lO月23日写信给当时最伟大的科学家哈密顿，这成为四色问题第一个人历史文献。不过，哈密顿对这类好像数学游戏的问题不太感兴趣，德·摩尔根于是继续宣传，直到另一位英国数学家凯莱于1878年在皇家学会上正式提出并在《皇家地理学会会报》上发表，这才引起人们对四色问题的广泛重视。各国数学中心和数学杂志都收到大量的错误证明，就如同以后的费马大定理和哥德巴赫猜想一样。

　　正如许多这类提法简单而证明极为困难的大猜想一样，大量的“证明”完全离谱，但也有的包含可贵的思想，当然这些思想只能来自有数学训练的人。1879年，剑桥大学三一学院数学毕业生肯普先在《自然》杂志，后在《美国数学杂志》上发表四色猜想的证明。然而到1890年，一位大学数学讲师希伍德指出肯普的“证明”中有一个漏洞，然后，他应用肯普的方法给出一个定理——五色定理，也就是五色足够。尽管四色定理没有得到证明，肯普和希伍德对于后来图论的发展都作出决定性的贡献。一位图论大师说道，1890年四色问题的研究主要沿着两条道路发展：一条是定性的，主要是肯普发明的“链”方法，一条是定量的，主要是希伍德的方法，其思想基础是寻找一个极小的反例。开始的作法是对于区域数目很少的地图证明四色定理，由于区域数越多，可能的构形数目也越多，因此到1976年，虽然区域数接近100个，但这个问题还差得很远。

　　

　　计算机的参与

　　

　　要想完整地证明四色定理，还是需要在概念上下工夫，特别是要寻找可约化的构形，也就是把区域数多的问题简化为区域数少的情形。20世纪60年代、70年代当时估计这种构形有8000到10000个，这用计算机也办不到。后来阿沛尔及哈肯用计算机搜索，发现只有不到2000个，从而完成了全部的证明。它用了1200小时的机时，相当于计算机连续算50个昼夜。这成为第一个用计算机证明的大定理。芝加哥的邮局信封上也印有“四色足够”的字样。它轰动了整个世界。但是数学界对此并不放心，于是阿沛尔和哈肯又进行了系统的检查，的确发现并纠正了一些小的错误，并在1989年发表修正后的论文。

　　但是，这仍然不能平息人们的疑虑，另一组数学家企图通过手写来证明，但是，没有成功。他们的贡献在于使用的可约化构形数目大大减少了，减少到633种构形。整个证明简单，而且容易复核，虽然仍需计算机帮助，但再次肯定四色猜想的确成为定理。

　　

　　几点启示

　　

　　首先，虽然迄今为止，四色猜想仍是电脑证明数学难题绝无仅有的一例，但它昭示了“机器证明”时代的到来。它可能开辟了人与机器合作去解决问题的新途径，成为数学上一系列新思维的起点。

　　其次，四色猜想的证明，是人工智能机器与人类本身关系的一次验证。通过人工智能的运用，找到一些数学难题解决的途径，不应该给人们带来某些顾虑(似乎在人工智能机器面前，人类显得如此渺小和无能，由此甚至产生“机器取代人脑”的恐惧)。四色猜想是第一个用计算机辅助证明的大定理，但是主导整个证明的是数学家，计算机只是进行机械化的运算。

　　第三，四色猜想看来是一个带有数学游戏性质的孤立的问题，可是它却创造出图论许多新的分支。数学家的本事在于他们能够把复杂的事物变成简单的对象。从四色问题就可以做这样的化简：一个区域不妨看成一个点，任何两个区域或者相邻(也就是公用一条边界)，或是不相邻。如果代表两个区域的点相邻，那么我们就在两点之间连上一条线，否则就不连线。这样的结构就称为图。四色问题也就变成图的顶点着色的问题，也就是两顶点如果有线相连，则必须涂上不同颜色。