生活与数学（1）——四色问题

  你想一战成名吗？ 

  圣诞节前夜，一个住在英国卡姆登镇贝汗街的小男孩汤姆收到了一份圣诞礼物，一套四色蜡笔和一张空白的英国郡县的地图，要求小男孩将地图着色，必须保证两个有公共边界的郡县被涂上不同的颜色。 

  谁会送给汤姆这样的礼物呢？可能是作为制图员的邻居碰巧送来的，也可能那位脾气古怪的数学家，奥古斯都.德摩根，他住在附近，与汤姆的父亲相交甚密。总之，这些礼物绝对不是吝啬鬼斯克搙奇送来的。 

    当教授打电话询问汤姆是否已经将地图涂上颜色的时候该礼物的来源终于真相大白。德摩根是伦敦大学的一名教授，住在克莱切特一家附近。前不久，德摩根的一名学生，弗雷德克.格思里，便向他问起过这个问题，而且提到了一种使用四种颜色就可以按要求将英国地图着色的方法。这个问题激发了德摩根的数学想象力。对于任何一种地图，是否使用四种颜色就可以保证相邻区域的颜色不同？几个世纪以来，制图员对此深信不疑，但可以给出一个严格的证明吗？让我们看一下美国西部的州地图。如果仅仅使用蓝、绿、红三种颜色，我们可以先从内华达州和爱达华州开始。开始时选用哪个颜色是无所谓的，我们不妨为内华达州选择蓝色，为爱达苛州选择绿色。到现在为止还没有任何问题。同时，这个选择意味着必须将犹他州着为红色，然后，将亚利桑那州着为绿色，将加利福尼亚州着为红色，并将俄勒冈州着为绿色。这意味着俄勒冈州和爱达荷州都着为了绿色，因此，它们无法被区分开来。然而，如果我们有四种颜色，即增添一种黄色，我们便可以使用该颜色为俄勒冈州着色，这样就满足了所有的要求。

生活与数学（1）——四色问题

  那么这四种颜色——蓝色、绿色、红色以及黄色，对任意一张地图都足够了吗？这个问题即是著名的四色问题。

生活与数学（1）——四色问题

  19世纪60年代，美国数学家和哲学家查尔斯.桑德斯.皮尔士认为自己已经证明了该问题，但我们对其证明过程却无从寻觅。由于维多利亚时代的地理学家弗朗西斯.高尔顿的介入，该问题变得广为人知。他看到了将其公之于众的价值，因而促使杰出的剑桥数学家阿瑟.凯莱在1878年写了一篇介绍该问题的论文。他承认自己无法给出证明，但他注意到的我们只需要集中注意力在每个交点上相邻只有三个国家的地图。这个贡献激发了他的学生阿尔法、弗雷德.布雷.肯普，他开始尝试各种方法，仅仅一年之后，肯普宣布他找到了证明的方法。他得到了凯莱的哀心祝愿，并因此被选入了英国皇家学会。

  接下来发生了什么呢？尽管肯普的证明过程非常冗长，而且技术要求比较高，有一两个人一直对其持怀疑态度，但这个证明过程还是被广泛接受了。10年后，柏西.希伍德找到了一个反例，指出了肯普证明过程的不足，这给当时的人们一个不小的震惊。尽管他没有能够给出自己的证明，但希伍德告诉世人，四色问题的挑战之门仍然敞开着。这也给新人提供了一个战成名的机会。通过使用肯普的一些技术，希伍德证明了五色定理——使用五种颜色就可以将任意一张地图着色。如果有人能够构造出一个无法用四种颜色着色的地图，那么五色定理便将是一个 伟大的成就。数学家又处在了一个进退两难的境地：到底是四色还是五色？

    基本的四色定理是关于画在平面或球面上的地图的。如果地图是画在像甜甜圈这样的曲面上会怎样——对于数学家来说，这种曲面的形状要比它的味道更具吸引力。对于这种曲面，希伍德证明了七种颜色是将画在其上面的地图着色的充要条件。他甚至证明除了对于多孔（h个孔）甜甜圈曲面上的地图着色时，所需要的颜色数目——尽管他没有证明这些数目是所需要的最小值。

生活与数学（1）——四色问题 生活与数学（1）——四色问题

该问题解决了吗？50年后，这个在1852年提出的问题仍然是数学中的一个未解之谜。进入20世纪，那些最杰出的数学家对此仍然无能为力。尽管如此，人们还是取得了一些进展。一位数学家证明了四种颜色对于包括27个国家的地图是足够的,另一位数学家将这个数字增加到了31个，后来又有人将其增加到了35。如果以这种方式证明下去，永远都不会有尽头。幸运的是，一位对此问题研究了多年的德国数学家沃尔夫冈.哈肯，得到了美国数学家和计算机专家肯尼斯.阿佩尔的帮助。到了1976年的6月末，经过长时间不眠不休的研究，此工作终于完成了。在他们所信赖的那台IBM370计算机的帮助下，他们终于成功地解决了这个伟大的问题。一些人勉强接受了该工作的成果，但很多人还是持怀疑态度。麻烦之处在于，这是一个电脑完成的证明，而非采用传统的数学证明方式。人们已经预料证明方法可能会很难理解，证明过程可能会很长，但计算机证明这一步的跨越还是有点太大了。它引出了“可验证性”的问题。人们如何去检验证明过程所依赖的那个上千行代码呢？计算机编程的错误时有发生，而一个错误则会带来毁灭性的后果。自1976年之后，需要检验的构形数量又减少了一半，而计算机的运算速度越来越快，性能越来越强大。但即便如此，数学界还是在等待一个以传统方式作出了的更加简洁的证明。同时，四色定理在图论中又衍生了许多新的重要问题，而且它还有一个附带影响。那就是，它挑战了数学家对于数学证明应该是什么样子的原有概念。这个古老的、连汤姆这样的10岁孩童都可以理解的问题，将一些最伟大的数学家戏弄和折磨了一个多世纪，研究这样的一个问题有什么意义呢？

  着色在我们得生活中有重要的用途，在二维平面内着色可以解决三维的时间安排问题。

生活与数学（1）——四色问题

这是一个工作查询界面，明显不适合继续筛选的单元格，用红色标注；明显适合继续筛选的单元格，用绿色标注；还有一些不太确定的，则不表明颜色。大大增加了识别率。假设7个欧米珈级超级大反派，毁灭博士，黑暗领主，康，奥创，万磁王，天启和灭雷要在同一天攻击地球。我们有7组超级英雄，新复仇者联盟，X战警，X特攻队，神奇四侠，捍卫者联盟，复仇者联盟，今天这些英雄要狙击这些超反派，拯救世界，下面是他们的名册。

生活与数学（1）——四色问题

每个团队要求全部队员都到齐才能作战，问题是有些英雄在几个团队里，比如金刚狼就参加四个团队。怎么安排作战时间，才能使他们的等待时间更短，从而更快的拯救地球呢？可以用着色来解决，每个团队看作一个节点，有共用队员的团队用线段连接起来，这样有线段连接的节点不同图相同颜色，没有连线的节点没有要求。

生活与数学（1）——四色问题

如图，金刚狼所在的四个团队就图上不同的颜色，第一战队紫色，第二战队红色，第三战队蓝色，第四战队绿色，只需要安排四场战役，这样只需要4种颜色，就解决了这样一个复杂问题。