本文来自微信公众号：返朴 （ID：fanpu2019）庭院里的女人，作家：含英
想必你一定外传过四色定理，这个最先源于给舆图上国度上色的风趣问题被誉为世界近代三大数知识题之一。数学家用了 100 多年的时刻才给出了真确的讲解，所用的缠绵机讲解也登上了数学舞台。如今，在图论范围，还有许多由四色定理繁衍出来的风趣问题。举例，一个发祥于收音机播送电台的问题：在一个无尽大的网格纸上填入数字，兼并个数字之间的“距离”必须大于这个数字自己，那么最少需要若干个数字能笼罩统统这个词平面？
撰文 | 含英
年幼的你会对着书斋墙面上的世界舆图怔住吗？注目着那五颜六色的图案，畅想着我方改日有一天能够环游世界。而在 19 世纪的英国，一个迂腐且经典的数知识题 —— 着色问题，就降生于这么一份注目。
故事运转于 1852 年，英国舆图制图师弗朗西斯・古特里（Francis Guthrie）在不雅察舆图时提议了一个“给舆图着色”的问题。他发现只需要四种心扉就不错对舆图进行着色，使得相邻的国度心扉不同。但令他不明的是，这个数字“4”是否是最优的呢？于是他向他的弟弟弗雷德里克・古特里（Frederick Guthrie）过甚一又友们寻求匡助。在交流中，他们渐渐剖判到这个问题与数学有着长远的推敲。于是弗雷德里克向他的竭诚，伦敦大学学院的数学家奥古斯塔斯・德摩根（Augustus De Morgan）寻求匡助。德摩根教练尝试之后也窝囊为力，于是写信将这个问题转交给了他的好友，爱尔兰数学家威廉・哈密顿（William Hamilton）教练。缺憾的是，充满机灵的哈密顿对这个问题并莫得太大的兴趣。
摩尔根在信中写说念：“一位学生今天让我证据一个事实，咱们不知说念它是否可当作一个事实。他说将平面上的一个图形，率性分离红有限个部分并对其每个部分染色，使得相邻部分具有不同的心扉，况兼只可用四种心扉。你以为怎样？淌若这个问题成立，它能引起东说念主们缓和吗？”
最先，这个“听起来浅薄易懂的”问题并莫得引起数学家们的平时缓和。直到 1878 年，英国数学家阿瑟・凯莱（Arthur Cayley）在伦敦数学会上老成晓示并定名这一问题为“四色问题”，这才激励了各人的求解空想。在其时，数学家们广阔觉得四色问题不会太难，应该很快就能惩办。但是，事与愿违，从“四色揣摸”到“四色定理”，履历了漫长的 120 多年，致使一度与“费尔马大定理”、“哥德巴赫揣摸”同称世界上最著名的三大数学勤快 。
四色问题的粗鲁讲述中有好多无效信息，举例每个国度的阵势、面积、经纬度等等。独一伏击的信息就是 —— 相邻（即两个区域分享兼并段鸿沟）。忽略掉这些无效信息，咱们来望望怎样用空洞的图论（Graph Theory）谈话来严格界说这个问题。
给定一个图（graph）G= (V， E)，其中非空聚积 V 是高出（vertex）集，E 是边（edge）集。这里其实要用到对偶图的认识，也就是说，用一个高出 ν∈V 来默示舆图上的一个国度；用一条边 e12=(ν1， ν2)∈E 来默示两个高出（国度）ν1， ν2 是相邻的。底下咱们只辩论浅薄无向图 —— 图的边是无向的，即 e12=e21；莫得重迭边，即团结高出 ν1， ν2 的边最多只好一条；莫得自环，即不存在只团结一个高出的边。
于是四色问题便空洞成了一个揣摸：对一个浅薄无向图 G=(V， E) 的高出进行着色，使相邻的点心扉不同，那么最少只需要 4 种心扉。这里最少所需的心扉数咱们称之为 —— 色数（chromatic number）。
最先东说念主们只可通过手工缠绵，得出关于一个包含了 96 个国度的舆图，四色揣摸成立。故事的升沉点发生在 1879 年，一位英国讼师阿福瑞德・肯普（Alfred Kempe）为四色揣摸的讲解提供了伏击的念念路。肯普提议，任何一个浅薄无向图 G=(V， E) 中至少有一个高出具有 2、3、4 或 5 个相邻高出（一个国度至少有 2、3、4 或 5 个邻国）。这个命题其实是欧拉公式的应用。假定图 G=(V， E) 中有 ν 个高出、e 个边和 f 个面。最先任何一个面至少有三条边，两个相邻的面共用一条边，每条边上有 2 个高出，因此 2e=3f。淌若每个高出皆有至少 6 条边，那么 2e≥6ν。但欧拉公式告诉咱们，ν-e+f=2。这就推出了一个矛盾。
肯普将上述最多具有 5 个相邻点的高出过甚相应的边定名为“不成幸免的构型”。接下来他愚弄归纳法，移撤退这个高出以及相邻的边，获取一个子图 G'。淌若这个子图 G' 得志四色揣摸，那么称原图 G' 是可约的，同期将移撤退的高出过甚边称为“可约构型”。肯普觉得，只须能讲解统统不成幸免的构型皆是可约构型（也就是说移撤退对应的高出过甚边后不错四色），那么四色揣摸势必成立。用数学的谈话讲，假定包含 n 个高出的图得志四色揣摸，那么关于 n+1 个高出的图，必有一个高出过甚边是不成幸免构型。淌若相邻点是三色的，那么给移撤退的点涂上第四种心扉，论断当然成立；不然，需要对原图从头涂色，争取开释这个高出，使它的相邻点不错三色，为此肯普联想了“肯普链”的步调。
但是，在肯普的闭幕公布 11 年后，东说念主们发现了其中有一个致命的、无法开导的诞妄。但肯普的念念路仍是为后世提供了伏击的龙套口，东说念主们延续他的步调不时讲解了 22 国、39 国、52 国以下的舆图不错四色。直到 1976 年，好意思国数学家肯尼斯・阿佩尔（Kenneth Appel）与沃尔夫格・哈肯（Wolfgang Haken）在好意思国伊利诺大学的两台缠绵机上，耗时 1200 个小时，终于完成了四色定理的讲解。他们延续并改良了肯普的步调，将统统的 1936 个不成幸免构型完全摆设出来，并轮换对其考证了可约性。这项责任颠簸了世界，不单是是因为他们讲解一个数学勤快，更伏击的是这告诉东说念主们缠绵机也能用于数学的逻辑讲解。在两位数学家将征询闭幕公众于世确当天，当地邮局为了庆祝，在统统邮件上皆加盖了“四色饱和”的特制邮戳。
事实上，阿佩尔与哈肯并不是最早意志到要用缠绵机提拔惩办四色揣摸的东说念主。早在 1950 年，德国数学家亨利・希许（Heinrich Heesch）就曾斟酌，只好借助于能处理巨量数据的强劲缠绵安设智力对四色揣摸中的有限但是数目广大的不同构型进行磨砺。在缠绵机本事还未荣华兴起的年代，希许的念念想十分超前。他是第一个提倡并试图愚弄缠绵机来攻克四色问题的数学家，同期他也粗糙地将我方的许多主义与哈肯交流，不错说他对四色揣摸的讲解起到了极大的激动作用。
尽管阿佩尔与哈肯的征询闭幕哄动一时，但在其时并莫得获取平时的招供。东说念主们的质疑主要源于关于缠绵机讲解数知识题的不招供。怀疑者们觉得阿佩尔与哈肯的步调骨子上是一种穷举磨砺法，他们只是用机器磨砺了千万种情况，他们的讲解细节荫藏在缠绵机内，东说念主力是无法进行复核的。数学界号令给出一份贞洁明了的数学讲解。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。
上头的例子只是辩论了一维情形，淌若咱们辩论二维平面整数集 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(ν) 中登第五个相邻的格点，组成一个加号型区域，以这么的加号型区域为一个单元进行染色。也就是说，不错只辩论把某个数字填入这个加号型区域，但暂时不辩论具体放在这个加号型区域的哪个格点。在排列好加号型区域的染色决策后，再对每个格点进行染色。
正如同业所评价的：苏威卡塞乌斯和海勒不单是在惩办问题，他们更是在优化组合学的征询念念路。在不懈的奋力下，历时四个月，他们最终攻克了平面 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
告白声明：文内含有的对外跳转联络（包括不限于超联络、二维码、口令等时势）庭院里的女人，用于传递更多信息，从简甄选时刻，闭幕仅供参考，IT之家统统著述均包含本声明。