应用四色定理填色的世界地图，图片来源：自然资源部标准地图服务系统

四色问题的起源

尽管阿佩尔与哈肯的研究成果轰动一时，但在当时并没有得到广泛的认可。人们的质疑主要源于对于计算机证明数学问题的不认可。怀疑者们认为阿佩尔与哈肯的方法本质上是一种穷举检验法，他们只是用机器检验了千万种情况，他们的证明细节隐藏在计算机内，人力是无法进行复核的。数学界呼吁给出一份纯粹明了的数学证明。30 年后来自英国剑桥大学的年轻数学家乔治·贡帝埃（Georges Gonthier）给出四色定理的完全计算机化证明，和阿佩尔、哈肯不同的是，他的每一步逻辑证明都由计算机独立完成。经过多年的计算机革命，人们逐渐认可了计算机对于数学工作的帮助，也终于愿意承认——四色定理成立！

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

数学家们在研究四色猜想的过程中，对其他相关的染色问题也进行了思考。例如最著名的 Hadwiger-Nelson 问题：在一张无限大的平面上进行点染色，使得相邻的点颜色不同。我们今天介绍的是四色问题的另一种变形：Packing染色（Packing coloring）问题，也叫广播染色（Broadcast coloring）问题。这个问题最早是由克莱姆森大学（Clemson University）教授维恩·戈达德（Wayne Goddard）等人提出的，它其实来源于一个非常实际的问题——广播电台的频率分配。

收音机

每个广播电台所发出信号的覆盖面积都是有限的，信号越强的电台它的覆盖范围也越广。收音机的调频（FM）波段很窄，我国的民用收音机调频范围为 FM87.5-108MHz。如果我国每个省市的广播电台都发出不同频率的信号，显然是不切实际的。而两个同频率的电台只有在相距足够远的情况下，它们的信号才不会互相干扰。例如，天津相声广播、沈阳都市广播、泰州交通音乐广播的FM频率均为 92.1MHz；而与天津比邻的北京，为了避免相同信号的叠加干扰，其广播电台频率表中并没有分配 92.1 MHz 的信号波段。

那么如何对不同地区广播电台的频率进行分配，使得我们可以在避免干扰的前提下，用最短的信号波段区间来覆盖全国的广播系统呢？数学家们又是如何用数学的语言来定义这件事呢？

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

packing 染色问题其实是在地图着色问题上加了更强的限制。当 K={1} 时，packing 1- 染色问题就是最原始的地图着色问题，即要求相邻两个顶点颜色不同。我们先来看一个简单的例子，考虑下图中的一维整数轴，取图 G=Z={0, ±1, ±2,……} 为整数集，每个整数代表一个顶点，两个相邻的整数记为两个相邻的顶点，两个整数之间的距离定义为他们差值的绝对值。构造映射如下：

因此 d(-2, 2)=4＞3=f(-2)=f(2)。那么此时 χρ(Z)=3。

一维 Packing 3- 染色,图片来源：参考文献[8]

上面的例子仅仅考虑了一维情形，如果我们考虑二维平面整数集 Z2 的染色问题呢？可以想象，对于一个无限大的平面，我们可以把平面划分成一个个网格（就像一个无限大的棋盘一样），定义两个网格之间的距离为它们之间的水平距离加上垂直距离，那么如何对它们进行 packing 染色？

2008 年，戈达德和他的四位合作者首先公开了他们对于这个问题的思考，他们完全用人力计算，得出 9 ≤χρ(Z2)≤ 23；此后又有几位数学家利用计算机辅助证明，逐步将结果优化为 13 ≤χρ(Z2)≤ 15。

2022 年，来自卡耐基梅隆大学的研究生苏威卡塞乌斯（Bernardo Subercaseaux）和教授马金·海勒（Marijn J. H. Heule）两人将这个结果进一步优化为 14 ≤χρ(Z2)≤ 15。2023 年 1 月，他们宣布彻底解决了平面整数集 Z2 的 packing 染色问题——他们在文章中证明 χρ(Z2)= 15，即只用 1-15 这 15 个数字就能填充整个平面网格，并保证两个具有相同数字的网格之间的距离大于这个数字。下面我们就来简单介绍一下他们的思路和方法。

显然，对一个无限网格用穷举法是不现实也不必要的。所以，数学家想到对其中的一小部分进行验证，比如取一个 10×10 的网格，后将其复制拼接，如果依然能够满足对距离的要求，即可得证。

苏威卡塞乌斯和海勒首先从这个角度对图进行了简化，但他们并不是考虑简单的矩形，而是从一个类似于菱形的有限子图 Dr(ν)={u∈Z2/d(u, ν)≤r} 出发，用 Dr, k 表示对子图 Dr[(0, 0)] 进行 k-packing 染色，Dr, k, c 表示对子图 Dr[(0, 0)] 进行 k-packing 染色而且中心点 (0, 0) 赋予颜色 c。如果对于子图 Dr(ν) 可以进行 k-packing 染色，那么一定有 χρ(Z2)≥k；反之 χρ(Z2)≥k+1。不难想象，在 Dr(ν) 这样的有限图中，数字越小出现的次数也就越多；所以在染色过程中可以优先考虑更大的数字的存放位置。比如当 r≤k 时，子图 Dr, k, r 中数字 r 只会在中心点 (0, 0) 出现一次，否则就会破坏我们对于距离的要求。这也是 Dr(ν) 相较于矩形子图的优势。Dr(ν) 其实是一个正四边形，具有很好的对称性，因此苏威卡塞乌斯和海勒把 Dr(ν) 进行八等分（见图 7），在染色时依次把较大的数字放在 1/8 角域里进行排列，这样就避免了对染色方案的重复验证。图 8 的 D3, 7, 3 就是一个很直观的例子。

对Dr(ν) 八等分，图片来源：参考文献[8]

D3, 7, 3 染色，图片来源：参考文献[8]

苏威卡塞乌斯和海勒所做的第二个简化是不再单纯地以格点为一个染色单位。他们在 Dr(ν) 中选取五个相邻的格点，构成一个加号型区域，以这样的加号型区域为一个单位进行染色。也就是说，可以只考虑把某个数字填入这个加号型区域，但暂时不考虑具体放在这个加号型区域的哪个格点。在排列好加号型区域的染色方案后，再对每个格点进行染色。

加号型区域，图片来源：参考文献[8]

正如同行所评价的：苏威卡塞乌斯和海勒不只是在解决问题，他们更是在优化组合学的研究思路。在不懈地努力下，历时四个月，他们最终攻克了平面 packing 染色问题。

尾声‍

四色定理困扰了数学界一个多世纪，时至今日也没有找到真正纯粹的数学证明。但四色问题的意义已远超这个问题本身，更重要的是在一代代数学家们前赴后继思考的过程中，所衍生出来的对于其他学科分支的思考，例如图论、拓扑、计算机科学等。人们愿意研究四色问题，并不是为了真的用四种颜色填补地图，而是为了探讨“4”这个数字所体现出来的拓扑性质和数学内涵。

作为第一个由计算机辅助证明的数学定理，四色定理由最初的饱受质疑到广泛认可，这注定了它在数学史上的非凡地位。在人工智能飞速发展的今天，AI辅助数学证明成为了大多数学者关注的对象。尽管依然有人认为AI的形式化证明会破坏数学原始的美感，但不可否认的是先进的技术手段确实大幅度地简化了数学家的工作。或许我们应该质疑的并不是计算机本身，而是学者们使用计算机的态度和方法。

欧几里得在《几何原本》中将公元前 300 年的数学以一种近乎完美的语言定义了出来，呈现给后世一套直观严谨的几个系统。当时光来到 21 世纪，人们用精确的符号和机械的规则将数学翻译为计算机代码，这又何尝不是一次数学文化的传承和迭代呢？

参考文献

[1] 徐俊明. 图论及其应用.第3版[M].合肥 ：中国科学技术大学出版社. 2010.

[2] Fritsch R. The Four-Color Theorem[J]. American Mathematical Monthly, 1997, 106(8):785.

[3] Gonthier G. Formal Proof—The Four- Color Theorem[J]. American Mathematical Society Notices, 2009(1).

[4] 王献芬,胡作玄.四色定理的三代证明.《自然辩证法通讯》.2010年第4期42-48,127,共7页

[5] Goddard, W., Hedetniemi, S., Hedetniemi, S., Harris, J., Rall, D.: Broadcast chromatic numbers of graphs. Ars Comb. 86 (01 2008)

[6] Bre sar, B., Ferme, J., Klav zar, S., Rall, D.F.: A survey on packing colorings. Discussiones Mathematicae Graph Theory 40(4), 923 (2020)

[7] Subercaseaux, B., Heule, M.J.H.: The Packing Chromatic Number of the Infinite Square Grid Is at Least 14. In: Meel, K.S., Strichman, O. (eds.) 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 236, pp. 21:1–21:16. Schloss Dagstuhl – Leibniz-Zentrum fur Infor- ¨ matik, Dagstuhl, Germany (2022)

[8] Subercaseaux, B., Heule, M.J.H The Packing Chromatic Number of the Infinite Square Grid is 15. arXiv:2301.09757

-END- 版权声明：文章来源于网络返回搜狐，查看更多