数学史上最伟大的事件之一开始于1852年10月23日。当时，英国地图制图师弗朗西斯·古特里（Francis Guthrie）在观察一张地图时提出关于“给地图着色”的问题，他想知道是否有可能用最少的颜色对地图进行着色，使得相邻的区域颜色不同。他向他的哥哥弗雷德里克·格思里（Frederick Guthrie）提出了这个问题，并向其他人寻求帮助。弗雷德里克在与他的朋友们交流中，认识到这个问题涉及到图论和离散数学中的概念，于是他向伦敦大学学院的数学家奥古斯塔斯·德摩根（Augustus De Morgan）寻求帮助。德摩根最终将这个问题转交给了他的学生阿瑟·凯莱（Arthur Cayley），但凯莱也未能解决这个问题。1882年，肯普（Kempe）在提出了一个被称为“肯普链”的思想，这个思想成为了解决四色定理的一个重要工具。肯普链是指一些连接不同颜色区域的边，它们可以相互连接形成一个环，通过这个环的变化可以将地图上的颜色重新涂上。肯普利用这个思想提出了一种证明四色定理的方法，但后来发现这个方法是有错误的。虽然Kempe的方法最终被证明是错误的，但他的工作仍然是四色定理研究中的重要里程碑之一，它激励了后来数学家们寻找新的证明方法，最终在20世纪中期证明了四色定理。为了更好地理解Kempe和大多数数学家对这个问题的看法，我们需要认识到地图中包含很多与着色问题无关的信息，例如每个区域的形状、大小和精确位置。在着色问题中，相邻的区域是最重要的。如果两个区域共享一个边界，则它们是相邻的。对于着色问题，只有相邻的区域之间可能需要被涂上不同的颜色。为了聚焦于重要的信息，我们可以使用一个称为图格（graph）的图来编码这些关系，其中点（顶点）通过线（边）相互连接。用一个顶点来代表地图上的每个区域，并用一条边将相邻区域的顶点连接起来。这样，地图着色问题就被转化为了图着色问题：对图的顶点进行着色，使相邻的点颜色不同。所需的最少颜色数称为图的色数。我们可以考虑任何图的色数，但所考虑的图必须简单图。在图论中，一个简单图是一个没有重复边和自环的图。重复边是指连接同一对顶点的两条或更多边，而自环是指连接同一顶点的边。简单图也可以被定义为没有多重边的图。简单图是图论中最基本的图形之一，由许多实际问题所描述。 肯普证明的基本思想是，从一个只包含一个顶点的图开始，然后一步步地添加顶点和边，每次添加一个顶点时，将其涂上不同于与之相邻的顶点的颜色。通过这种方法，可以证明对于任何地图都可以使用最多四种颜色进行着色。假设我们只需用四种颜色对所有顶点数为n的简单图进行着色，如果我们拿到一个有n + 1个顶点的图，我们该如何证明它也只需最多四种颜色来着色呢？首先，肯普证明了，每个简单图都有一个共同点：它必须至少包含一个至多有五个邻居的顶点。- 肯普证明，每个简单图形都必须有这些类型之一的顶点。
如果我们移除这个顶点以及与之相连的所有边，我们就得到了一个有n个顶点的图，我们已经知道可以用四种颜色来着色。现在看一下与移除的顶点相邻的顶点。如果它们中的三个或更少是不同的颜色，我们可以把移除的顶点涂上剩下的一种颜色，这样就完成了：我们刚刚证明了具有n+1个顶点的图可以用四种颜色着色。如果相邻的顶点包含了所有四种颜色，肯普设计了“一种聪明的方法”来重新涂色特定的顶点，以释放一种颜色给移除的顶点，从而再次证明具有n+1个顶点的图只需要用四种颜色。1890年，数学家希伍德（Percy Heawood）发现了肯普的错误。在一种特殊情况下，肯普的聪明方法会失败。希伍德指出，肯普的技巧可以证明每个地图都可以用五种或更少的颜色来着色。希伍德还研究了在更复杂表面上绘制的图（刚刚我们讨论的都是平面图）。他证明了一个带有 g 个孔的甜甜圈图可能需这么多种颜色：因此，着色一个普通甜甜圈可能需要多达七种颜色的涂料。然而，他对一般曲面的证明是不完整的，直到1968年才有了一个完整的证明。1976年，在一次会议上，福尔克·哈肯（Wolfgang Haken）与肯尼斯·阿普尔（Kenneth Appel）合作，宣布解决了四色定理。然而，人们对此反应褒贬不一。因为他们的证明依赖于计算机，而不是一个书面证明。由于平面图的数量是无限的，因此他们没有让机器直接回答这个问题，因为计算机无法检查所有可能性。不过，肯普曾经证明每个图形都包含六个特殊的顶点配置，而阿普尔和哈肯则证明每个图形必须具有1936个特殊的配置。证明这个定理的过程就是要表明我们只需要四种颜色就可以给包含这些子图的任何图形着色。为了更细致地控制每种情况并使每种情况更容易检查，他们将肯普的六种特殊情况分解成了1936个子情况，尽管现在总数已经远远超出了人类在没有辅助工具的情况下验证的范围。事实上，完成这些计算需要超过1000小时的计算机时间。数学界对这些结果只是勉强接受，他们认为证明应该是可以被人类完全理解和验证的。尽管让计算机执行日常算术是可以接受的，但数学家并不准备将逻辑推理让给计算机。这种保守和不愿意接受新事物的现象并不是首次，类似的情况在17世纪也曾发生，当时一些数学家使用新颖的代数技巧来解决几何问题，引起了类似的争议。随着机器学习的兴起，同样的戏剧性场景可能会再次出现：数学家是否会接受由不透明算法发现和证明的定理？四色问题的证明只是计算机革命在数学中的开始。1998年，黑尔斯（Thomas Hales）通过使用计算机生成和验证大量的数学公式，最终证明了开普勒猜想（conjecture of Johannes Kepler’s）。他使用了复杂的计算机程序和算法，包括离散傅里叶变换、线性规划和自动定理证明。这项工作产生了几千页的证明文件，历时近10年才完成。开普勒猜想是由17世纪德国天文学家约翰·开普勒提出的一个问题，即如何在三维空间中最有效地将球堆叠在一起，以填满空间。具体来说，这个问题是要求在给定的空间中，如何排列一定数量的同大小球体，使得这些球体之间的空隙最小，并且不留下任何剩余空间。尽管开普勒猜想被认为是正确的，并且数百年来一直被广泛使用，但长期以来一直缺乏严格的数学证明。 最近，计算机帮助找到了“上帝之数（God’s number）”。"上帝之数"是一个数学术语，指的是解决特定难题或问题所需的最大步数。这个术语是由一个计算机算法所发明的，该算法被用来解决魔方（Rubik's Cube）难题，魔方是一种三维组合难题，于1974年发明。魔方有着43万亿个可能的组合方式，找到最优解需要搜索所有的组合方式，这是一个非常庞大的计算任务。在魔方问题中，"上帝之数"指的是解决任何可能的初始状态所需的最大步数。在2010年，人们证明了解决魔方问题的最大步数为20步，如果把半步旋转算作两步，则为26步。这意味着，无论初始状态如何，任何可解的魔方都可以在20步或更少的步数内解决。"上帝之数"一词强调了这个难题的困难程度，以及找到最优解所需的深刻理解和大量计算能力。 虽然地图四色问题已经得到解决，但关于图形着色的许多基本问题仍未解答或刚刚得到解决。希伍德关于曲面的研究表明，我们可以对非平面图提出可着色性的问题。实际上，特定图形的色数并不取决于等价图所绘制的曲面。例如，每个顶点都连接到其他每个顶点的图形称为完全图，完全图的色数为n。因此，如果一个大图包含一个具有n个顶点的完全图，那么我们就知道该大图的色数至少为n。这个观察结果并不意味着如果一个图的色数是n，那么它就包含一个有n个顶点的完全图。但是在1943年，Hugo Hadwiger提出了一个非常类似的猜想。他认为，如果一个没有环的图的色数为n，则它有一种称为K_n小图的顶点排列方式，其中删除一些顶点和边并将其他顶点分组形成一个有n个顶点的完全图。换句话说，这个猜想表明，如果一个图没有K_n小图，则它可以用少于n个颜色进行着色。Hadwiger的猜想是图论中最重要的未解决问题之一，它是四色定理的推广，因为平面图不能包含K_5小图。虽然图着色始于地图问题，但与地图或颜色无关的问题也可以适用于图着色框架。例如，数独是一个伪装成图着色问题的问题。将每个单元格视为一个顶点，将九个数字视为颜色。每个顶点有20条边出来，分别与其行、列和3×3子方格中的每个单元格相连。这个由81个顶点和810条边组成的图从部分着色（已知的线索）开始。目的是对其余顶点进行着色。虽然这些着色问题受到了很多关注，但我们仍然没有一种人类可以阅读的原始四色定理的证明。
|
