想必你一定聽說過四色定理，這個最初源于給地圖上國家上色的有趣問題被譽(yù)為世界近代三大數(shù)學(xué)問題之一。數(shù)學(xué)家用了100多年的時間才給出了真正的證明，所用的計算機(jī)證明也登上了數(shù)學(xué)舞臺。如今，在圖論領(lǐng)域，還有許多由四色定理衍生出來的有趣問題。例如，一個起源于收音機(jī)廣播電臺的問題：在一個無限大的網(wǎng)格紙上填入數(shù)字，同一個數(shù)字之間的“距離”必須大于這個數(shù)字本身，那么最少需要多少個數(shù)字能覆蓋整個平面？

撰文?|?含英

年幼的你會對著書房墻面上的世界地圖發(fā)呆嗎？凝視著那五顏六色的圖案，暢想著自己將來有一天能夠環(huán)游世界。而在19世紀(jì)的英國，一個古老且經(jīng)典的數(shù)學(xué)問題——著色問題，就誕生于這樣一份凝視。

圖1：世界地圖丨圖源：自然資源部標(biāo)準(zhǔn)地圖服務(wù)系統(tǒng)

四色問題的起源

故事開始于1852年，英國地圖制圖師弗朗西斯·古特里（Francis Guthrie）在觀察地圖時提出了一個“給地圖著色”的問題。他發(fā)現(xiàn)只需要四種顏色就可以對地圖進(jìn)行著色，使得相鄰的國家顏色不同。但令他不解的是，這個數(shù)字“4”是否是最優(yōu)的呢？于是他向他的弟弟弗雷德里克·古特里（Frederick Guthrie）及其朋友們尋求幫助。在交流中，他們逐漸認(rèn)識到這個問題與數(shù)學(xué)有著深刻的聯(lián)系。于是弗雷德里克向他的老師，倫敦大學(xué)學(xué)院的數(shù)學(xué)家奧古斯塔斯·德摩根（Augustus De Morgan）尋求幫助。德摩根教授嘗試之后也無能為力，于是寫信將這個問題轉(zhuǎn)交給了他的好友，愛爾蘭數(shù)學(xué)家威廉·哈密頓（William Hamilton）教授。遺憾的是，充滿智慧的哈密頓對這個問題并沒有太大的興趣。
摩爾根在信中寫道：“一位學(xué)生今天讓我說明一個事實，我們不知道它是否可作為一個事實。他說將平面上的一個圖形，任意劃分成有限個部分并對其每個部分染色，使得相鄰部分具有不同的顏色，而且只能用四種顏色。你以為如何？如果這個問題成立，它能引起人們關(guān)注嗎？”
起初，這個“聽起來簡單易懂的”問題并沒有引起數(shù)學(xué)家們的廣泛關(guān)注。直到1878年，英國數(shù)學(xué)家阿瑟·凱萊（Arthur Cayley）在倫敦數(shù)學(xué)會上正式宣布并命名這一問題為“四色問題”，這才激發(fā)了大家的求解欲望。在當(dāng)時，數(shù)學(xué)家們普遍認(rèn)為四色問題不會太難，應(yīng)該很快就能解決。然而，事與愿違，從“四色猜想”到“四色定理”，經(jīng)歷了漫長的120多年，甚至一度與“費(fèi)爾馬大定理”、“哥德巴赫猜想”同稱世界上最著名的三大數(shù)學(xué)難題 。

圖2：數(shù)學(xué)家凱萊 圖源：Smithsonian Institution Librarie

四色定理的百年證明

四色問題的通俗敘述中有很多無效信息，例如每個國家的形狀、面積、經(jīng)緯度等等。唯一重要的信息便是——相鄰（即兩個區(qū)域共享同一段邊界）。忽略掉這些無效信息，我們來看看如何用抽象的圖論（Graph Theory）語言來嚴(yán)格定義這個問題。
給定一個圖（graph）G= (V, E)，其中非空集合V是頂點（vertex）集，E是邊（edge）集。這里其實要用到對偶圖的概念，也就是說，用一個頂點ν∈V來表示地圖上的一個國家；用一條邊e12=(ν1,?ν2)∈E來表示兩個頂點（國家）ν1,?ν2是相鄰的。下面我們只考慮簡單無向圖——圖的邊是無向的，即e12=e21；沒有重復(fù)邊，即連接頂點ν1,?ν2的邊最多只有一條；沒有自環(huán)，即不存在只連接一個頂點的邊。
于是四色問題便抽象成了一個猜想：對一個簡單無向圖G=(V, E)的頂點進(jìn)行著色，使相鄰的點顏色不同，那么最少只需要4種顏色。這里最少所需的顏色數(shù)我們稱之為——色數(shù)（chromatic number）。
起初人們只能通過手工計算，得出對于一個包含了96個國家的地圖，四色猜想成立。故事的轉(zhuǎn)折點發(fā)生在1879年，一位英國律師阿福瑞德·肯普（Alfred Kempe）為四色猜想的證明提供了重要的思路?？掀仗岢?，任何一個簡單無向圖G=(V, E)中至少有一個頂點具有2、3、4或5個相鄰頂點（一個國家至少有2、3、4或5個鄰國）。這個命題其實是歐拉公式的應(yīng)用。假設(shè)圖G=(V, E)中有ν個頂點、e個邊和f個面。首先任何一個面至少有三條邊，兩個相鄰的面共用一條邊，每條邊上有2個頂點，因此2e=3f。如果每個頂點都有至少6條邊，那么2e≥6ν。但歐拉公式告訴我們，ν-e+f=2。這就推出了一個矛盾。
肯普將上述最多具有5個相鄰點的頂點及其相應(yīng)的邊命名為“不可避免的構(gòu)型”。接下來他利用歸納法，移除掉這個頂點以及相鄰的邊，得到一個子圖G'。如果這個子圖G'滿足四色猜想，那么稱原圖G'是可約的，同時將移除掉的頂點及其邊稱為“可約構(gòu)型”。肯普認(rèn)為，只要能證明所有不可避免的構(gòu)型都是可約構(gòu)型（也就是說移除掉對應(yīng)的頂點及其邊后可以四色），那么四色猜想必然成立。用數(shù)學(xué)的語言講，假設(shè)包含n個頂點的圖滿足四色猜想，那么對于n+1個頂點的圖，必有一個頂點及其邊是不可避免構(gòu)型。如果相鄰點是三色的，那么給移除掉的點涂上第四種顏色，結(jié)論自然成立；否則，需要對原圖重新涂色，爭取釋放這個頂點，使它的相鄰點可以三色，為此肯普設(shè)計了“肯普鏈”的方法。
然而，在肯普的結(jié)果公布11年后，人們發(fā)現(xiàn)了其中有一個致命的、無法修復(fù)的錯誤。但肯普的思路依然為后世提供了重要的突破口，人們延續(xù)他的方法陸續(xù)證明了22國、39國、52國以下的地圖可以四色。直到1976 年，美國數(shù)學(xué)家肯尼斯·阿佩爾（Kenneth Appel）與沃爾夫格·哈肯（Wolfgang Haken）在美國伊利諾大學(xué)的兩臺計算機(jī)上，耗時1200個小時，終于完成了四色定理的證明。他們延續(xù)并改進(jìn)了肯普的方法，將所有的1936個不可避免構(gòu)型完全羅列出來，并依次對其驗證了可約性。這項工作轟動了世界，不僅僅是因為他們證明一個數(shù)學(xué)難題，更重要的是這告訴人們計算機(jī)也能用于數(shù)學(xué)的邏輯證明。在兩位數(shù)學(xué)家將研究成果公眾于世的當(dāng)天，當(dāng)?shù)剜]局為了慶祝，在所有郵件上都加蓋了“四色足夠”的特制郵戳。

圖3 在四色定理證明發(fā)表后的許多年里，伊利諾伊大學(xué)厄巴納-香檳分校數(shù)學(xué)系在外發(fā)郵件上都蓋上了“四色足夠”的郵戳。丨圖源：las.illinois.edu

圖4：數(shù)學(xué)家哈肯（Wolfgang Haken，1928-2022）和阿佩爾（Kenneth Appel，1938-2013） 丨圖源：legacy.com/mathyear2013.blogspot.com

事實上，阿佩爾與哈肯并不是最早意識到要用計算機(jī)輔助解決四色猜想的人。早在1950年，德國數(shù)學(xué)家亨利·希許（Heinrich Heesch）就曾預(yù)測，只有借助于能處理巨量數(shù)據(jù)的強(qiáng)大計算裝置才能對四色猜想中的有限但是數(shù)量巨大的不同構(gòu)型進(jìn)行檢驗。在計算機(jī)技術(shù)還未蓬勃興起的年代，希許的思想十分超前。他是第一個提倡并試圖利用計算機(jī)來攻克四色問題的數(shù)學(xué)家，同時他也慷慨地將自己的許多想法與哈肯交流，可以說他對四色猜想的證明起到了極大的推動作用。
盡管阿佩爾與哈肯的研究成果轟動一時，但在當(dāng)時并沒有得到廣泛的認(rèn)可。人們的質(zhì)疑主要源于對于計算機(jī)證明數(shù)學(xué)問題的不認(rèn)可。懷疑者們認(rèn)為阿佩爾與哈肯的方法本質(zhì)上是一種窮舉檢驗法，他們只是用機(jī)器檢驗了千萬種情況，他們的證明細(xì)節(jié)隱藏在計算機(jī)內(nèi)，人力是無法進(jìn)行復(fù)核的。數(shù)學(xué)界呼吁給出一份純粹明了的數(shù)學(xué)證明。30年后來自英國劍橋大學(xué)的年輕數(shù)學(xué)家喬治·貢帝埃（Georges Gonthier）給出四色定理的完全計算機(jī)化證明，和阿佩爾、哈肯不同的是，他的每一步邏輯證明都由計算機(jī)獨立完成。經(jīng)過多年的計算機(jī)革命，人們逐漸認(rèn)可了計算機(jī)對于數(shù)學(xué)工作的幫助，也終于愿意承認(rèn)——四色定理成立！

廣播色數(shù)問題：四色問題的推廣

數(shù)學(xué)家們在研究四色猜想的過程中，對其他相關(guān)的染色問題也進(jìn)行了思考。例如最著名的Hadwiger-Nelson問題：在一張無限大的平面上進(jìn)行點染色，使得相鄰的點顏色不同。我們今天介紹的是四色問題的另一種變形：Packing染色（Packing coloring）問題，也叫廣播染色（Broadcast coloring）問題。這個問題最早是由克萊姆森大學(xué)（Clemson University）教授維恩·戈達(dá)德（Wayne Goddard）等人提出的，它其實來源于一個非常實際的問題——廣播電臺的頻率分配。

圖5：收音機(jī)丨圖源：網(wǎng)絡(luò)

每個廣播電臺所發(fā)出信號的覆蓋面積都是有限的，信號越強(qiáng)的電臺它的覆蓋范圍也越廣。收音機(jī)的調(diào)頻（FM）波段很窄，我國的民用收音機(jī)調(diào)頻范圍為FM87.5-108MHz。如果我國每個省市的廣播電臺都發(fā)出不同頻率的信號，顯然是不切實際的。而兩個同頻率的電臺只有在相距足夠遠(yuǎn)的情況下，它們的信號才不會互相干擾。例如，天津相聲廣播、沈陽都市廣播、泰州交通音樂廣播的FM頻率均為92.1MHz；而與天津比鄰的北京，為了避免相同信號的疊加干擾，其廣播電臺頻率表中并沒有分配92.1 MHz的信號波段。

那么如何對不同地區(qū)廣播電臺的頻率進(jìn)行分配，使得我們可以在避免干擾的前提下，用最短的信號波段區(qū)間來覆蓋全國的廣播系統(tǒng)呢？數(shù)學(xué)家們又是如何用數(shù)學(xué)的語言來定義這件事呢？
與四色定理類似，給定一個簡單無向圖G=(V, E)，我們用一個整數(shù)集合K={1,…,k}來表示顏色集，用d(u,?ν)來定義兩個頂點u,?ν之間的距離?？紤]映射f:V→{1,…,k}，它滿足對任意兩個頂點u,?ν∈V，以及任意的整數(shù)c∈K，如果f(u)=f(ν)=c（即頂點u和ν的顏色相同），那么u,?ν之間的距離d(u,?ν)＞c（也就是說具有相同顏色的兩個頂點距離足夠遠(yuǎn)；考慮上文的實際背景，這意味著信號頻率相同的廣播電臺距離足夠遠(yuǎn)）。這樣的映射f就構(gòu)成了一個packing k-染色方案，能滿足packing染色方案的最小整數(shù)就稱為圖的packing染色數(shù)（packing coloring number）χρ(G)。
packing染色問題其實是在地圖著色問題上加了更強(qiáng)的限制。當(dāng)K={1}時，packing 1-染色問題就是最原始的地圖著色問題，即要求相鄰兩個頂點顏色不同。我們先來看一個簡單的例子，考慮下圖中的一維整數(shù)軸，取圖G=Z={0,?±1, ±2,……}為整數(shù)集，每個整數(shù)代表一個頂點，兩個相鄰的整數(shù)記為兩個相鄰的頂點，兩個整數(shù)之間的距離定義為他們差值的絕對值。構(gòu)造映射如下：

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

圖 6：一維Packing 3-染色 圖源：參考文獻(xiàn)[8]
上面的例子僅僅考慮了一維情形，如果我們考慮二維平面整數(shù)集Z2的染色問題呢？可以想象，對于一個無限大的平面，我們可以把平面劃分成一個個網(wǎng)格（就像一個無限大的棋盤一樣），定義兩個網(wǎng)格之間的距離為它們之間的水平距離加上垂直距離，那么如何對它們進(jìn)行packing染色？
2008年，戈達(dá)德和他的四位合作者首先公開了他們對于這個問題的思考，他們完全用人力計算，得出9 ≤χρ(Z2)≤ 23；此后又有幾位數(shù)學(xué)家利用計算機(jī)輔助證明，逐步將結(jié)果優(yōu)化為13 ≤χρ(Z2)≤ 15。
2022年，來自卡耐基梅隆大學(xué)的研究生蘇威卡塞烏斯（Bernardo Subercaseaux）和教授馬金·海勒（Marijn J. H. Heule）兩人將這個結(jié)果進(jìn)一步優(yōu)化為14 ≤χρ(Z2)≤ 15。2023年1月，他們宣布徹底解決了平面整數(shù)集Z2的packing染色問題——他們在文章中證明χρ(Z2)= 15，即只用1-15這15個數(shù)字就能填充整個平面網(wǎng)格，并保證兩個具有相同數(shù)字的網(wǎng)格之間的距離大于這個數(shù)字。下面我們就來簡單介紹一下他們的思路和方法。
顯然，對一個無限網(wǎng)格用窮舉法是不現(xiàn)實也不必要的。所以，數(shù)學(xué)家想到對其中的一小部分進(jìn)行驗證，比如取一個10×10的網(wǎng)格，后將其復(fù)制拼接，如果依然能夠滿足對距離的要求，即可得證。蘇威卡塞烏斯和海勒首先從這個角度對圖進(jìn)行了簡化，但他們并不是考慮簡單的矩形，而是從一個類似于菱形的有限子圖Dr(ν)={u∈Z2/d(u,?ν)≤r}出發(fā)，用Dr, k表示對子圖Dr[(0, 0)]進(jìn)行k-packing染色，Dr,?k, c表示對子圖Dr[(0,?0)]進(jìn)行k-packing染色而且中心點(0,?0)賦予顏色c。如果對于子圖Dr(ν)可以進(jìn)行k-packing染色，那么一定有χρ(Z2)≥k；反之χρ(Z2)≥k+1。不難想象，在Dr(ν)這樣的有限圖中，數(shù)字越小出現(xiàn)的次數(shù)也就越多；所以在染色過程中可以優(yōu)先考慮更大的數(shù)字的存放位置。比如當(dāng)r≤k時，子圖Dr,?k, r中數(shù)字r只會在中心點(0,?0)出現(xiàn)一次，否則就會破壞我們對于距離的要求。這也是Dr(ν)相較于矩形子圖的優(yōu)勢。Dr(ν)其實是一個正四邊形，具有很好的對稱性，因此蘇威卡塞烏斯和海勒把Dr(ν)進(jìn)行八等分（見圖7），在染色時依次把較大的數(shù)字放在1/8角域里進(jìn)行排列，這樣就避免了對染色方案的重復(fù)驗證。圖8的D3,?7, 3就是一個很直觀的例子。

圖7：對Dr(ν)八等分丨圖源：參考文獻(xiàn)[8]

圖8：D3, 7, 3染色丨圖源：參考文獻(xiàn) [8]
蘇威卡塞烏斯和海勒所做的第二個簡化是不再單純地以格點為一個染色單位。他們在Dr(ν)中選取五個相鄰的格點，構(gòu)成一個加號型區(qū)域，以這樣的加號型區(qū)域為一個單位進(jìn)行染色。也就是說，可以只考慮把某個數(shù)字填入這個加號型區(qū)域，但暫時不考慮具體放在這個加號型區(qū)域的哪個格點。在排列好加號型區(qū)域的染色方案后，再對每個格點進(jìn)行染色。

圖9：加號型區(qū)域丨圖源：參考文獻(xiàn)[8]
正如同行所評價的：蘇威卡塞烏斯和海勒不只是在解決問題，他們更是在優(yōu)化組合學(xué)的研究思路。在不懈的努力下，歷時四個月，他們最終攻克了平面packing染色問題。

尾聲

四色定理困擾了數(shù)學(xué)界一個多世紀(jì)，時至今日也沒有找到真正純粹的數(shù)學(xué)證明。但四色問題的意義已遠(yuǎn)超這個問題本身，更重要的是在一代代數(shù)學(xué)家們前赴后繼思考的過程中，所衍生出來的對于其他學(xué)科分支的思考，例如圖論、拓?fù)洹⒂嬎銠C(jī)科學(xué)等。人們愿意研究四色問題，并不是為了真的用四種顏色填補(bǔ)地圖，而是為了探討“4”這個數(shù)字所體現(xiàn)出來的拓?fù)湫再|(zhì)和數(shù)學(xué)內(nèi)涵。
作為第一個由計算機(jī)輔助證明的數(shù)學(xué)定理，四色定理由最初的飽受質(zhì)疑到廣泛認(rèn)可，這注定了它在數(shù)學(xué)史上的非凡地位。在人工智能飛速發(fā)展的今天，AI輔助數(shù)學(xué)證明成為了大多數(shù)學(xué)者關(guān)注的對象。盡管依然有人認(rèn)為AI的形式化證明會破壞數(shù)學(xué)原始的美感，但不可否認(rèn)的是先進(jìn)的技術(shù)手段確實大幅度地簡化了數(shù)學(xué)家的工作?；蛟S我們應(yīng)該質(zhì)疑的并不是計算機(jī)本身，而是學(xué)者們使用計算機(jī)的態(tài)度和方法。
歐幾里得在《幾何原本》中將公元前300年的數(shù)學(xué)以一種近乎完美的語言定義了出來，呈現(xiàn)給后世一套直觀嚴(yán)謹(jǐn)?shù)膸讉€系統(tǒng)。當(dāng)時光來到21世紀(jì)，人們用精確的符號和機(jī)械的規(guī)則將數(shù)學(xué)翻譯為計算機(jī)代碼，這又何嘗不是一次數(shù)學(xué)文化的傳承和迭代呢？

參考文獻(xiàn)

[1]徐俊明. 圖論及其應(yīng)用.第3版[M].合肥 ：中國科學(xué)技術(shù)大學(xué)出版社. 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] 王獻(xiàn)芬,胡作玄.四色定理的三代證明.《自然辯證法通訊》.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

本文受科普中國·星空計劃項目扶持

出品：中國科協(xié)科普部

監(jiān)制：中國科學(xué)技術(shù)出版社有限公司、北京中科星河文化傳媒有限公司