四色定理：古典著色問題的新時(shí)代算法

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

撰文 | 含英

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

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

四色問題的起源

故事開始于1852年，英國地圖制圖師弗朗西斯·古特里（Francis Guthrie）在觀察地圖時(shí)提出了一個(gè)“給地圖著色”的問題。他發(fā)現(xiàn)只需要四種顏色就可以對(duì)地圖進(jìn)行著色，使得相鄰的國家顏色不同。但令他不解的是，這個(gè)數(shù)字“4”是否是最優(yōu)的呢？于是他向他的弟弟弗雷德里克·古特里（Frederick Guthrie）及其朋友們尋求幫助。在交流中，他們逐漸認(rèn)識(shí)到這個(gè)問題與數(shù)學(xué)有著深刻的聯(lián)系。于是弗雷德里克向他的老師，倫敦大學(xué)學(xué)院的數(shù)學(xué)家奧古斯塔斯·德摩根（Augustus De Morgan）尋求幫助。德摩根教授嘗試之后也無能為力，于是寫信將這個(gè)問題轉(zhuǎn)交給了他的好友，愛爾蘭數(shù)學(xué)家威廉·哈密頓（William Hamilton）教授。遺憾的是，充滿智慧的哈密頓對(duì)這個(gè)問題并沒有太大的興趣。

摩爾根在信中寫道：“一位學(xué)生今天讓我說明一個(gè)事實(shí)，我們不知道它是否可作為一個(gè)事實(shí)。他說將平面上的一個(gè)圖形，任意劃分成有限個(gè)部分并對(duì)其每個(gè)部分染色，使得相鄰部分具有不同的顏色，而且只能用四種顏色。你以為如何？如果這個(gè)問題成立，它能引起人們關(guān)注嗎？”

起初，這個(gè)“聽起來簡單易懂的”問題并沒有引起數(shù)學(xué)家們的廣泛關(guān)注。直到1878年，英國數(shù)學(xué)家阿瑟·凱萊（Arthur Cayley）在倫敦?cái)?shù)學(xué)會(huì)上正式宣布并命名這一問題為“四色問題”，這才激發(fā)了大家的求解欲望。在當(dāng)時(shí)，數(shù)學(xué)家們普遍認(rèn)為四色問題不會(huì)太難，應(yīng)該很快就能解決。然而，事與愿違，從“四色猜想”到“四色定理”，經(jīng)歷了漫長的120多年，甚至一度與“費(fèi)爾馬大定理”、“哥德巴赫猜想”同稱世界上最著名的三大數(shù)學(xué)難題 。

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

四色定理的百年證明

四色問題的通俗敘述中有很多無效信息，例如每個(gè)國家的形狀、面積、經(jīng)緯度等等。唯一重要的信息便是——相鄰（即兩個(gè)區(qū)域共享同一段邊界）。忽略掉這些無效信息，我們來看看如何用抽象的圖論（Graph Theory）語言來嚴(yán)格定義這個(gè)問題。

給定一個(gè)圖（graph）G= (V, E)，其中非空集合V是頂點(diǎn)（vertex）集，E是邊（edge）集。這里其實(shí)要用到對(duì)偶圖的概念，也就是說，用一個(gè)頂點(diǎn)ν∈V來表示地圖上的一個(gè)國家；用一條邊e12=(ν1, ν2)∈E來表示兩個(gè)頂點(diǎn)（國家）ν1, ν2是相鄰的。下面我們只考慮簡單無向圖——圖的邊是無向的，即e12=e21；沒有重復(fù)邊，即連接頂點(diǎn)ν1, ν2的邊最多只有一條；沒有自環(huán)，即不存在只連接一個(gè)頂點(diǎn)的邊。

于是四色問題便抽象成了一個(gè)猜想：對(duì)一個(gè)簡單無向圖G=(V, E)的頂點(diǎn)進(jìn)行著色，使相鄰的點(diǎn)顏色不同，那么最少只需要4種顏色。這里最少所需的顏色數(shù)我們稱之為——色數(shù)（chromatic number）。

起初人們只能通過手工計(jì)算，得出對(duì)于一個(gè)包含了96個(gè)國家的地圖，四色猜想成立。故事的轉(zhuǎn)折點(diǎn)發(fā)生在1879年，一位英國律師阿福瑞德·肯普（Alfred Kempe）為四色猜想的證明提供了重要的思路?？掀仗岢?，任何一個(gè)簡單無向圖G=(V, E)中至少有一個(gè)頂點(diǎn)具有2、3、4或5個(gè)相鄰頂點(diǎn)（一個(gè)國家至少有2、3、4或5個(gè)鄰國）。這個(gè)命題其實(shí)是歐拉公式的應(yīng)用。假設(shè)圖G=(V, E)中有ν個(gè)頂點(diǎn)、e個(gè)邊和f個(gè)面。首先任何一個(gè)面至少有三條邊，兩個(gè)相鄰的面共用一條邊，每條邊上有2個(gè)頂點(diǎn)，因此2e=3f。如果每個(gè)頂點(diǎn)都有至少6條邊，那么2e≥6ν。但歐拉公式告訴我們，ν-e+f=2。這就推出了一個(gè)矛盾。

肯普將上述最多具有5個(gè)相鄰點(diǎn)的頂點(diǎn)及其相應(yīng)的邊命名為“不可避免的構(gòu)型”。接下來他利用歸納法，移除掉這個(gè)頂點(diǎn)以及相鄰的邊，得到一個(gè)子圖G'。如果這個(gè)子圖G'滿足四色猜想，那么稱原圖G'是可約的，同時(shí)將移除掉的頂點(diǎn)及其邊稱為“可約構(gòu)型”。肯普認(rèn)為，只要能證明所有不可避免的構(gòu)型都是可約構(gòu)型（也就是說移除掉對(duì)應(yīng)的頂點(diǎn)及其邊后可以四色），那么四色猜想必然成立。用數(shù)學(xué)的語言講，假設(shè)包含n個(gè)頂點(diǎn)的圖滿足四色猜想，那么對(duì)于n+1個(gè)頂點(diǎn)的圖，必有一個(gè)頂點(diǎn)及其邊是不可避免構(gòu)型。如果相鄰點(diǎn)是三色的，那么給移除掉的點(diǎn)涂上第四種顏色，結(jié)論自然成立；否則，需要對(duì)原圖重新涂色，爭取釋放這個(gè)頂點(diǎn)，使它的相鄰點(diǎn)可以三色，為此肯普設(shè)計(jì)了“肯普鏈”的方法。

然而，在肯普的結(jié)果公布11年后，人們發(fā)現(xiàn)了其中有一個(gè)致命的、無法修復(fù)的錯(cuò)誤。但肯普的思路依然為后世提供了重要的突破口，人們延續(xù)他的方法陸續(xù)證明了22國、39國、52國以下的地圖可以四色。直到1976 年，美國數(shù)學(xué)家肯尼斯·阿佩爾（Kenneth Appel）與沃爾夫格·哈肯（Wolfgang Haken）在美國伊利諾大學(xué)的兩臺(tái)計(jì)算機(jī)上，耗時(shí)1200個(gè)小時(shí)，終于完成了四色定理的證明。他們延續(xù)并改進(jìn)了肯普的方法，將所有的1936個(gè)不可避免構(gòu)型完全羅列出來，并依次對(duì)其驗(yàn)證了可約性。這項(xiàng)工作轟動(dòng)了世界，不僅僅是因?yàn)樗麄冏C明一個(gè)數(shù)學(xué)難題，更重要的是這告訴人們計(jì)算機(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

事實(shí)上，阿佩爾與哈肯并不是最早意識(shí)到要用計(jì)算機(jī)輔助解決四色猜想的人。早在1950年，德國數(shù)學(xué)家亨利·希許（Heinrich Heesch）就曾預(yù)測(cè)，只有借助于能處理巨量數(shù)據(jù)的強(qiáng)大計(jì)算裝置才能對(duì)四色猜想中的有限但是數(shù)量巨大的不同構(gòu)型進(jìn)行檢驗(yàn)。在計(jì)算機(jī)技術(shù)還未蓬勃興起的年代，希許的思想十分超前。他是第一個(gè)提倡并試圖利用計(jì)算機(jī)來攻克四色問題的數(shù)學(xué)家，同時(shí)他也慷慨地將自己的許多想法與哈肯交流，可以說他對(duì)四色猜想的證明起到了極大的推動(dòng)作用。

盡管阿佩爾與哈肯的研究成果轟動(dòng)一時(shí)，但在當(dāng)時(shí)并沒有得到廣泛的認(rèn)可。人們的質(zhì)疑主要源于對(duì)于計(jì)算機(jī)證明數(shù)學(xué)問題的不認(rèn)可。懷疑者們認(rèn)為阿佩爾與哈肯的方法本質(zhì)上是一種窮舉檢驗(yàn)法，他們只是用機(jī)器檢驗(yàn)了千萬種情況，他們的證明細(xì)節(jié)隱藏在計(jì)算機(jī)內(nèi)，人力是無法進(jìn)行復(fù)核的。數(shù)學(xué)界呼吁給出一份純粹明了的數(shù)學(xué)證明。30年后來自英國劍橋大學(xué)的年輕數(shù)學(xué)家喬治·貢帝埃（Georges Gonthier）給出四色定理的完全計(jì)算機(jī)化證明，和阿佩爾、哈肯不同的是，他的每一步邏輯證明都由計(jì)算機(jī)獨(dú)立完成。經(jīng)過多年的計(jì)算機(jī)革命，人們逐漸認(rèn)可了計(jì)算機(jī)對(duì)于數(shù)學(xué)工作的幫助，也終于愿意承認(rèn)——四色定理成立！

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

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

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

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

那么如何對(duì)不同地區(qū)廣播電臺(tái)的頻率進(jìn)行分配，使得我們可以在避免干擾的前提下，用最短的信號(hào)波段區(qū)間來覆蓋全國的廣播系統(tǒng)呢？數(shù)學(xué)家們又是如何用數(shù)學(xué)的語言來定義這件事呢？

與四色定理類似，給定一個(gè)簡單無向圖G=(V, E)，我們用一個(gè)整數(shù)集合K={1,…,k}來表示顏色集，用d(u, ν)來定義兩個(gè)頂點(diǎn)u, ν之間的距離?？紤]映射f:V→{1,…,k}，它滿足對(duì)任意兩個(gè)頂點(diǎn)u, ν∈V，以及任意的整數(shù)c∈K，如果f(u)=f(ν)=c（即頂點(diǎn)u和ν的顏色相同），那么u, ν之間的距離d(u, ν)＞c（也就是說具有相同顏色的兩個(gè)頂點(diǎn)距離足夠遠(yuǎn)；考慮上文的實(shí)際背景，這意味著信號(hào)頻率相同的廣播電臺(tái)距離足夠遠(yuǎn)）。這樣的映射f就構(gòu)成了一個(gè)packing k-染色方案，能滿足packing染色方案的最小整數(shù)就稱為圖的packing染色數(shù)（packing coloring number）χρ(G)。

packing染色問題其實(shí)是在地圖著色問題上加了更強(qiáng)的限制。當(dāng)K={1}時(shí)，packing 1-染色問題就是最原始的地圖著色問題，即要求相鄰兩個(gè)頂點(diǎn)顏色不同。我們先來看一個(gè)簡單的例子，考慮下圖中的一維整數(shù)軸，取圖G=Z={0, ±1, ±2,……}為整數(shù)集，每個(gè)整數(shù)代表一個(gè)頂點(diǎn)，兩個(gè)相鄰的整數(shù)記為兩個(gè)相鄰的頂點(diǎn)，兩個(gè)整數(shù)之間的距離定義為他們差值的絕對(duì)值。構(gòu)造映射如下：

圖9：加號(hào)型區(qū)域丨圖源：參考文獻(xiàn)[8]

正如同行所評(píng)價(jià)的：蘇威卡塞烏斯和海勒不只是在解決問題，他們更是在優(yōu)化組合學(xué)的研究思路。在不懈的努力下，歷時(shí)四個(gè)月，他們最終攻克了平面packing染色問題。

尾聲

四色定理困擾了數(shù)學(xué)界一個(gè)多世紀(jì)，時(shí)至今日也沒有找到真正純粹的數(shù)學(xué)證明。但四色問題的意義已遠(yuǎn)超這個(gè)問題本身，更重要的是在一代代數(shù)學(xué)家們前赴后繼思考的過程中，所衍生出來的對(duì)于其他學(xué)科分支的思考，例如圖論、拓?fù)?、?jì)算機(jī)科學(xué)等。人們?cè)敢庋芯克纳珕栴}，并不是為了真的用四種顏色填補(bǔ)地圖，而是為了探討“4”這個(gè)數(shù)字所體現(xiàn)出來的拓?fù)湫再|(zhì)和數(shù)學(xué)內(nèi)涵。

作為第一個(gè)由計(jì)算機(jī)輔助證明的數(shù)學(xué)定理，四色定理由最初的飽受質(zhì)疑到廣泛認(rèn)可，這注定了它在數(shù)學(xué)史上的非凡地位。在人工智能飛速發(fā)展的今天，AI輔助數(shù)學(xué)證明成為了大多數(shù)學(xué)者關(guān)注的對(duì)象。盡管依然有人認(rèn)為AI的形式化證明會(huì)破壞數(shù)學(xué)原始的美感，但不可否認(rèn)的是先進(jìn)的技術(shù)手段確實(shí)大幅度地簡化了數(shù)學(xué)家的工作?；蛟S我們應(yīng)該質(zhì)疑的并不是計(jì)算機(jī)本身，而是學(xué)者們使用計(jì)算機(jī)的態(tài)度和方法。

歐幾里得在《幾何原本》中將公元前300年的數(shù)學(xué)以一種近乎完美的語言定義了出來，呈現(xiàn)給后世一套直觀嚴(yán)謹(jǐn)?shù)膸讉€(gè)系統(tǒng)。當(dāng)時(shí)光來到21世紀(jì)，人們用精確的符號(hào)和機(jī)械的規(guī)則將數(shù)學(xué)翻譯為計(jì)算機(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

本文受科普中國·星空計(jì)劃項(xiàng)目扶持

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

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

特 別 提 示

1. 進(jìn)入『返樸』微信公眾號(hào)底部菜單“精品專欄“，可查閱不同主題系列科普文章。

2. 『返樸』提供按月檢索文章功能。關(guān)注公眾號(hào)，回復(fù)四位數(shù)組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。

版權(quán)說明：歡迎個(gè)人轉(zhuǎn)發(fā)，任何形式的媒體或機(jī)構(gòu)未經(jīng)授權(quán)，不得轉(zhuǎn)載和摘編。轉(zhuǎn)載授權(quán)請(qǐng)?jiān)凇阜禈恪刮⑿殴娞?hào)內(nèi)聯(lián)系后臺(tái)。