在一張世界地圖上，要給相鄰國家塗上不同的顏色，至少需要多少種顏色呢？
答案是四種顏色。
這就是數學界非常有名的四色定理，這個最初源於給地圖上國家上色的有趣問題被譽為世界近代三大數學問題之一。數學家用了100多年的時間才給出了真正的證明，所用的計算機證明也登上了數學舞臺。
如今，在圖論領域，還有許多由四色定理衍生出來的有趣問題。例如，一個起源於收音機廣播電臺的問題：在一個無限大的網格紙上填入數字，同一個數字之間的「距離」必須大於這個數字本身，那麼最少需要多少個數字能覆蓋整個平面？
年幼的你會對著書房牆面上的世界地圖發呆嗎？凝視著那五顏六色的圖案，暢想著自己將來有一天能夠環遊世界。而在19世紀的英國，一個古老且經典的數學問題——著色問題，就誕生於這樣一份凝視。
世界地圖丨圖源：自然資源部標準地圖服務系統
Part.1
四色問題的起源
故事開始於1852年，英國地圖製圖師弗朗西斯·古特里（Francis Guthrie）在觀察地圖時提出了一個「給地圖著色」的問題。他發現只需要四種顏色就可以對地圖進行著色，使得相鄰的國家顏色不同。但令他不解的是，這個數字「4」是否是最優的呢？於是他向他的弟弟弗雷德裡克·古特里（Frederick Guthrie）及其朋友們尋求幫助。
在交流中，他們逐漸認識到這個問題與數學有著深刻的聯繫。於是弗雷德裡克向他的老師，倫敦大學學院的數學家奧古斯塔斯·德摩根（Augustus De Morgan）尋求幫助。德摩根教授嘗試之後也無能為力，於是寫信將這個問題轉交給了他的好友，愛爾蘭數學家威廉·哈密頓（William Hamilton）教授。遺憾的是，充滿智慧的哈密頓對這個問題並沒有太大的興趣。
摩爾根在信中寫道：「一位學生今天讓我說明一個事實，我們不知道它是否可作為一個事實。他說將平面上的一個圖形，任意劃分成有限個部分並對其每個部分染色，使得相鄰部分具有不同的顏色，而且只能用四種顏色。你以為如何？如果這個問題成立，它能引起人們關注嗎？」
起初，這個「聽起來簡單易懂的」問題並沒有引起數學家們的廣泛關注。直到1878年，英國數學家阿瑟·凱萊（Arthur Cayley）在倫敦數學會上正式宣佈並命名這一問題為「四色問題」，這才激發了大家的求解慾望。在當時，數學家們普遍認為四色問題不會太難，應該很快就能解決。然而，事與願違，從「四色猜想」到「四色定理」，經歷了漫長的120多年，甚至一度與「費爾馬大定理」、「哥德巴赫猜想」同稱世界上最著名的三大數學難題。
數學家凱萊 圖源：Smithsonian Institution Librarie
Part.2
四色定理的百年證明
四色問題的通俗敘述中有很多無效資訊，例如每個國家的形狀、面積、經緯度等等。唯一重要的資訊便是——相鄰（即兩個區域共享同一段邊界）。忽略掉這些無效資訊，我們來看看如何用抽象的圖論（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個不可避免構型完全羅列出來，並依次對其驗證了可約性。
這項工作轟動了世界，不僅僅是因為他們證明一個數學難題，更重要的是這告訴人們計算機也能用於數學的邏輯證明。在兩位數學家將研究成果公眾於世的當天，當地郵局為了慶祝，在所有郵件上都加蓋了「四色足夠」的特製郵戳。
在四色定理證明發表後的許多年裡，伊利諾伊大學厄巴納-香檳分校數學系在外發郵件上都蓋上了「四色足夠」的郵戳。丨圖源：las.illinois.edu
數學家哈肯（Wolfgang Haken，1928-2022）和阿佩爾（Kenneth Appel，1938-2013） 丨圖源：legacy.com/mathyear2013.blogspot.com
事實上，阿佩爾與哈肯並不是最早意識到要用計算機輔助解決四色猜想的人。早在1950年，德國數學家亨利·希許（Heinrich Heesch）就曾預測，只有藉助於能處理巨量資料的強大計算裝置才能對四色猜想中的有限但是數量巨大的不同構型進行檢驗。在計算機技術還未蓬勃興起的年代，希許的思想十分超前。他是第一個提倡並試圖利用計算機來攻克四色問題的數學家，同時他也慷慨地將自己的許多想法與哈肯交流，可以說他對四色猜想的證明起到了極大的推動作用。
儘管阿佩爾與哈肯的研究成果轟動一時，但在當時並沒有得到廣泛的認可。人們的質疑主要源於對於計算機證明數學問題的不認可。懷疑者們認為阿佩爾與哈肯的方法本質上是一種窮舉檢驗法，他們只是用機器檢驗了千萬種情況，他們的證明細節隱藏在計算機內，人力是無法進行復核的。數學界呼籲給出一份純粹明瞭的數學證明。30年後來自英國劍橋大學的年輕數學家喬治·貢帝埃（Georges Gonthier）給出四色定理的完全計算機化證明，和阿佩爾、哈肯不同的是，他的每一步邏輯證明都由計算機獨立完成。經過多年的計算機革命，人們逐漸認可了計算機對於數學工作的幫助，也終於願意承認——四色定理成立！
Part.3
廣播色數問題：四色問題的推廣
數學家們在研究四色猜想的過程中，對其他相關的染色問題也進行了思考。例如最著名的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染色問題。
Part.4
尾聲
四色定理困擾了數學界一個多世紀，時至今日也沒有找到真正純粹的數學證明。但四色問題的意義已遠超這個問題本身，更重要的是在一代代數學家們前赴後繼思考的過程中，所衍生出來的對於其他學科分支的思考，例如圖論、拓撲、電腦科學等。人們願意研究四色問題，並不是為了真的用四種顏色填補地圖，而是為了探討「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
來源：返樸