古典着色问题的新时代算法

想必你一定听说过四色定理。 这个起源于在地图上给国家着色的有趣问题被称为世界三大现代数学问题之一。 数学家花了一百多年的时间才给出真正的证明，所使用的计算机证明也进入了数学阶段。 如今，在图论领域，有很多有趣的问题都是由四色定理衍生出来的。 例如，一个源于无线电广播电台的问题：在无限大的格子纸上填写数字，相同数字之间的“距离”必须大于数字本身，那么至少需要多少个数字才能覆盖整个平面？

作者|含英文

小时候，你会盯着书房墙上的世界地图发呆吗？ 看着那些色彩斑斓的图案，我想象着有一天我也能环游世界。 19世纪的英国，一个古老而经典的数学问题——着色问题，就是在这样的目光中诞生的。

图1：世界地图丨来源：自然资源部标准地图服务系统四色问题的由来

故事开始于1852年，当时英国地图制图师弗朗西斯古特里（ Gutry）在观察地图时提出了一个“给地图着色”的问题。 他发现只需要四种颜色就可以给地图上色，这样相邻国家的颜色就不同了。 但令他困惑的是，这个数字“4”是否是最优的？ 于是他向他的兄弟弗雷德里克格思里（ ）和他的朋友们寻求帮助。 在交流中，他们逐渐意识到这个问题与数学有着深刻的联系。 于是腓特烈向他的老师、伦敦大学学院的数学家奥古斯塔斯德摩根（ De ）寻求帮助。 德摩根教授尝试后无能为力，于是他写了一封信，将这个问题转发给他的朋友、爱尔兰数学家威廉汉密尔顿教授( )。 不幸的是，聪明的汉密尔顿对这个问题并没有多大兴趣。

摩根在信中写道：“今天有一个学生让我解释一个事实，我们不知道它是否可以被视为事实。他说平面上的一个图形被任意分成有限数量的部分，每个部分部分染色，让相邻部分颜色不同，只能用四种颜色，你觉得怎么样？如果这个问题属实，能引起人们的注意吗？

起初，这个“听起来简单”的问题并没有引起数学家的太多关注。 直到1878年，英国数学家阿瑟网凯莱（ ）在伦敦数学会正式宣布并命名这个问题为“四色问题”，才激起了大家解决它的欲望。 当时数学家普遍认为四色问题不会太难，应该很快就能解决。 然而，事情却适得其反。 从“四色猜想”到“四色定理”，历时120多年，甚至与“费马大定理”、“哥德巴赫猜想”并称为世界三大著名定理。 数学难题。

图2：数学家凯莱的来源：四色定理的百年证明

四色问题的通俗叙述中存在大量无效信息，例如各个国家的形状、面积、经纬度等等。 唯一重要的信息是 - 邻接（即两个区域共享相同的边界）。 忽略这些无效信息，我们来看看如何用抽象图论（Graph）语言来严格定义这个问题。

给定一个图（graph）G=（V，E），其中非空集合V是顶点（）的集合，E是边（edge）的集合。 其实这里用到了对偶图的概念，即地图上的一个国家用一个顶点∈V来表示； 两个顶点（国家）1 用一条边 e12=(1,2)E 表示，2 是相邻的。 下面我们只考虑简单的无向图——图的边是无向的，即e12=e21； 没有重复的边，即最多有一条边连接顶点1和2； 不存在自循环，即不存在仅与一个顶点侧的连接。

于是四色问题被抽象为一个猜想：给一个简单无向图G=(V,E)的顶点着色，使得相邻点有不同的颜色，那么至少需要4种颜色。 这里所需的最小颜色数称为 - 色数 ( )。

起初，人们只能手工计算，得出的结论是，对于一张包含96个国家的地图，四色猜想成立。 故事的转折点发生在1879年，当时英国律师阿尔弗雷德肯佩为四色猜想的证明提供了重要思路。 Kemp 提出，在任何简单无向图中 G=(V, E) 至少一个顶点有 2、3、4 或 5 个相邻顶点（一个国家至少有 2、3、4 或 5 个邻居）。 这个命题实际上是欧拉公式的应用。 假设图 G=(V, E) 中有 个顶点、e 个边和 f 个面。 首先，任意面至少有3条边，两个相邻的面共用一条边，每条边有2个顶点，所以2e=3f。 如果每个顶点至少有6条边，则2e≥6。 但欧拉公式告诉我们-e+f=2。 这就引入了一个矛盾。

Kemp 将上述最多有 5 个邻居的顶点及其对应的边命名为“不可避免的配置”。 接下来，他利用归纳法去除顶点和相邻边，得到子图G'。 如果这个子图G'满足四色猜想，则称原图G'是可约的，去除的顶点和边称为“可约配置”。 坎普认为，只要能证明所有不可避免的构型都是可约构型（即去掉相应的顶点和边后可以得到四种颜色），那么四色猜想就一定成立。 用数学语言来说，假设一个包含n个顶点的图满足四色猜想，那么对于一个包含n+1个顶点的图，必然存在一个顶点及其边是不可避免的配置。 如果相邻的点都是三种颜色，则将去掉的点涂上第四种颜色，结论自然成立； 为此，坎普设计了“坎普链”的方法。

然而，在坎普的研究结果发表11年后，人们发现其中存在致命的、不可挽回的错误。 不过，坎普的思想仍然为后人提供了重要的突破。 人们继续他的方法，证明了22个国家、39个国家和52个以下国家的地图可以有四种颜色。 直到1976年，美国数学家肯尼思阿佩尔和沃尔夫格哈肯在伊利诺伊大学的两台计算机上花费了1200个小时，终于完成了四色定理证明。 他们继续并改进了肯普的方法，列出了所有1936种不可避免的构型，并依次验证了它们的可约性。 这项工作引起了世界的轰动，不仅因为它们证明了一个数学问题，更重要的是它告诉人们计算机也可以用于数理逻辑证明。 在两位数学家公开研究成果的那天，当地邮局为所有邮件贴上了“四种颜色就够了”的特殊邮戳以示庆祝。

图3 四色定理证明发表多年后，伊利诺伊大学厄巴纳-香槟分校数学系在发出的邮件上盖上“四种颜色就足够了”的印章。丨来源：

图4：数学家哈肯（Haken，1928-2022）和阿佩尔（Appel，1938-2013）丨来源：/

事实上，阿佩尔和哈肯并不是第一个实现利用计算机辅助解决四色猜想的人。 早在1950年，德国数学家亨利希希（Henri Hisch）就预言，四色猜想的有限但数量巨大的不同配置只有借助能够处理大量数据的强大计算设备才能进行测试。 在计算机技术还不发达的时代，席旭的思想是非常超前的。 他是第一位提倡并尝试用计算机解决四色问题的数学家。 同时，他也慷慨地与哈肯交流了自己的许多想法。 可以说，他对四色猜想的证明起到了很大的推动作用。

尽管阿佩尔和哈肯的研究成果轰动一时，但当时并没有得到广泛认可。 人们的质疑主要源于不认可计算机证明数学问题。 怀疑论者认为Appel和Haken的方法本质上是一种穷举测试方法。 他们只是用机器测试了数千种情况，而他们的证明细节都隐藏在计算机中，人类无法检查。 数学界呼吁纯粹明确的数学证明。 三十年后，英国剑桥大学的年轻数学家乔治冈迪尔给出了四色定理的完整计算机证明。 与阿佩尔和哈肯不同，他的逻辑证明的每一步都是由计算机独立执行的。 结束。 经过多年的计算机革命，人们逐渐认识到计算机对于数学工作的帮助，并终于愿意承认四色定理成立！

广播色数问题：四色问题的推广

在研究四色猜想的过程中，数学家们还思考了其他相关的着色问题。 例如，最著名的问题：在无限平面上进行点着色，使相邻点具有不同的颜色。 今天我们介绍的是四色问题的另一种变体：着色（ ）问题，也称为广播着色（ ）问题。 这个问题首先是由克莱姆森大学（ ）教授韦恩戈达德（Wayne）等人提出的。 其实来源于一个很现实的问题——电台的频率分配。

图5：广播丨来源：网络

每个电台发出的信号的覆盖范围是有限的，信号越强的电台，覆盖范围就越广。 收音机的调频（FM）频段很窄，我国民用收音机的调频范围为FM87.5-。 如果我国各个省市的广播电台都发出不同频率的信号，显然是不切实际的。 而且两个频率相同的无线电台不会互相干扰，除非它们相距足够远。 例如，天津相网声广播、沉阳城市广播、台州交通音乐广播的调频频率为92.1MHz； 而与天津相邻的北京，为了避免同一信号频段的叠加干扰，其无线电台频率表中没有分配92.1 MHz信号。

那么如何分配不同地区的广播电台频率，以便在避免干扰的前提下，用最短的信号频段间隔覆盖全国广播系统呢？ 数学家如何用数学语言来定义这个问题？

与四色定理类似，给定一个简单的无向图G=(V,E)，我们用整数集合K={1,…,k}来表示颜色集合，用d(u,)来表示定义两个顶点之间的距离u,。 考虑映射 f:V →{1,…,k}，它满足任意两个顶点 u, V 和任意整数 cK，如果 f (u)=f ()=c （即顶点u 和 颜色相同），则 u, 之间的距离 d (u,)>c （即两个颜色相同的顶点距离足够远；考虑到上面的实际背景，这意味着信号相同频率的广播电台距离足够远）。 这样的映射f就构成了k-着色方案，能够满足该着色方案的最小整数称为图的着色数( ) (G)。

着色问题实际上是对地图着色问题的更强限制。 当K={1}时，1-着色问题是最原始的地图着色问题，要求两个相邻顶点具有不同的颜色。 我们先看一个简单的例子，考虑下图中的一维整数轴，将图G=Z={0, 1, 2,...}视为一组整数，每个整数代表一个顶点，两个相邻的整数记录为两个相邻的顶点，两个整数之间的距离定义为其差的绝对值。 构建映射如下：

因此 d(-2, 2) = 4 > 3 = f(-2) = f(2)。 则此时(Z)=3。

图6：1D 3-染色图 来源：参考文献[8]

上面的例子只考虑了一维的情况，如果考虑二维平面整数集合Z2的着色问题呢？ 可以想象，对于一个无限的平面，我们可以将平面划分为多个网格（就像一个无限的棋盘），并将两个网格之间的距离定义为它们之间的水平距离加上垂直距离，那么如何给它们着色呢？

2008年，戈达德和他的四位合作者首次发表了他们对这个问题的思考。 他们完全通过人工计算得出9≤(Z2)≤23； 证明，逐步优化结果至13≤(Z2)≤15。

2022年，卡内基梅隆大学研究生Suwei （）和JH Heule教授将这一结果进一步优化为14≤(Z2)≤15。2023年1月，他们宣布彻底解决了平面整数集的着色问题Z2——他们在文章中证明了(Z2)=15，即只需从1到15的15个数字就可以填满整个平面网格，并保证两个相同数字的网格之间的距离大于这个数字。 下面我们简单介绍一下他们的想法和方法。

显然，针对无限网格的穷举方法是不现实且不必要的。 因此，数学家想到验证其中的一小部分，比如取一个1010的网格，然后复制拼接。 如果仍能满足距离要求，即可获得证明。 Suwei 和首先从这个角度简化了图，但他们没有考虑简单的矩形，而是从有限子图Dr()={u∈Z2/d(u,)≤r}，使用Dr, k表示子图 Dr[(0, 0)] 的 k 着色，Dr,k, c 表示子图 Dr[(0,0)] 的 k 着色 - 着色和中心点 (0,0 ) 被分配颜色 c。 如果可以对子图Dr()进行k着色，则必定有(Z2)≥k； 否则 (Z2)≥k+1。 不难想象，在Dr()这样的有限图中，数字越小，出现的次数就越多； 因此在着色过程中可以优先考虑较大数字的存储位置。 例如，当r≤k时，子图Dr,k,r中的数字r只会在中心点(0,0)处出现一次，否则就会破坏我们的距离要求。 这也是Dr()相对于矩形子图的优势。 Dr()实际上是一个对称性良好的正四边形，因此Suwei 和将Dr()分成八等份（见图7），较大的依次分成数字排网列在1/8的方格内，从而避免了着色方案的双重验证。 图8中的D3,7,3是一个非常直观的例子。

图7：Dr()的八等分丨来源：参考文献[8]

图 8：D3、7、3 染色 | 来源：参考文献[8]

Suwei 和所做的第二个简化是网格点不再简单地用作着色单元。 他们在Dr()中选择5个相邻的网格点组成一个加号区域，并以这样的加号区域作为一个单位进行着色。 也就是说，你可以只考虑在加号区域中填充一定的数字，但暂时不要考虑将哪个网格点放入加号区域中。 安排好加号区域的着色方案后，为每个网格点着色。

图9：加号区域丨来源：参考文献[8]

正如同行评价：Suwei 和不仅是在解决问题，更是在优化组合学的研究思路。 经过四个月的不懈努力，他们终于解决了平面染色的难题。

结尾

四色定理困扰了数学界一个多世纪，直到现在还没有找到真正纯粹的数学证明。 但四色问题的意义远远超出了问题本身。 更重要的是对其他科学分支的思考，比如图论、拓扑学、计算机科学等，源自一代又一代数学家的思维过程。 人们愿意研究四色问题，并不是为了真正用四种颜色填充地图，而是为了探索数字“4”所体现的拓扑性质和数学内涵。

作为第一个计算机辅助数学定理，四色定理从最初的质疑得到了广泛的认可，这注定了它在数学史上的非凡地位。 如今，随着人工智能的快速发展，AI辅助数学证明成为大多数学者关注的焦点。 尽管仍然有人认为人工智能的形式化证明会破坏数学原本的美感，但不可否认的是，先进的技术手段极大地简化了数学家的工作。 也许我们应该质疑的不是计算机本身，而是学者使用计算机的态度和方法。

欧几里得在《几何原本》中用近乎完美的语言定义了公元前300年的数学，为后世呈现了一套直观而严密的体系。 当时间来到21世纪，人们利用精确的符号和机械规则将数学转化为计算机代码。 这难道不是数学文化的传承和迭代吗？

参考

广告声明：文章中包含的外部跳转链接（包括但不限于超链接、二维码、密码等）用于传达更多信息，节省选择时间。 结果仅供参考。 IT之家的所有文章均包含此声明。