愛游戲(ayx)中國官方網站-古典著色問題的新時代算法

本文來自微信公眾號：返樸 （ID：fanpu2019），古典作者：含英

撰文 | 含英

年幼的時代算法你會對著書房墻面上的世界地圖發呆嗎？凝視著那五顏六色的圖案，暢想著自己將來有一天能夠環游世界。古典而在 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 來表示地圖上的一個國家；用一條邊 e₁₂=(ν₁, ν₂)∈E 來表示兩個頂點（國家）ν₁, ν₂是相鄰的。下面我們只考慮簡單無向圖 —— 圖的邊是無向的，即 e₁₂=e₂₁；沒有重復邊，即連接頂點 ν₁, ν₂的邊最多只有一條；沒有自環，即不存在只連接一個頂點的邊。

于是四色問題便抽象成了一個猜想：對一個簡單無向圖 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。

上面的例子僅僅考慮了一維情形，如果我們考慮二維平面整數集 Z²的染色問題呢？可以想象，對于一個無限大的平面，我們可以把平面劃分成一個個網格（就像一個無限大的棋盤一樣），定義兩個網格之間的距離為它們之間的水平距離加上垂直距離，那么如何對它們進行 packing 染色？

2008 年，戈達德和他的四位合作者首先公開了他們對于這個問題的思考，他們完全用人力計算，得出 9 ≤χ_ρ(Z²)≤ 23；此后又有幾位數學家利用計算機輔助證明，逐步將結果優化為 13 ≤χ_ρ(Z²)≤ 15。

2022 年，來自卡耐基梅隆大學的研究生蘇威卡塞烏斯（Bernardo Subercaseaux）和教授馬金?海勒（Marijn J. H. Heule）兩人將這個結果進一步優化為 14 ≤χ_ρ(Z²)≤ 15。2023 年 1 月，他們宣布徹底解決了平面整數集 Z²的 packing 染色問題 —— 他們在文章中證明 χ_ρ(Z²)= 15，即只用 1-15 這 15 個數字就能填充整個平面網格，并保證兩個具有相同數字的網格之間的距離大于這個數字。下面我們就來簡單介紹一下他們的思路和方法。

顯然，對一個無限網格用窮舉法是不現實也不必要的。所以，數學家想到對其中的一小部分進行驗證，比如取一個 10×10 的網格，后將其復制拼接，如果依然能夠滿足對距離的要求，即可得證。蘇威卡塞烏斯和海勒首先從這個角度對圖進行了簡化，但他們并不是考慮簡單的矩形，而是從一個類似于菱形的有限子圖 D_r(ν)={u∈Z²/d (u, ν)≤r} 出發，用 D_{r, k}表示對子圖 D_r[(0, 0)] 進行 k-packing 染色，D_{r, k, c}表示對子圖 D_r[(0, 0)] 進行 k-packing 染色而且中心點 (0, 0) 賦予顏色 c。如果對于子圖 D_r(ν) 可以進行 k-packing 染色，那么一定有 χ_ρ(Z²)≥k；反之 χ_ρ(Z²)≥k+1。不難想象，在 D_r(ν) 這樣的有限圖中，數字越小出現的次數也就越多；所以在染色過程中可以優先考慮更大的數字的存放位置。比如當 r≤k 時，子圖 D_{r, k, r}中數字 r 只會在中心點 (0, 0) 出現一次，否則就會破壞我們對于距離的要求。這也是 D_r(ν) 相較于矩形子圖的優勢。D_r(ν) 其實是一個正四邊形，具有很好的對稱性，因此蘇威卡塞烏斯和海勒把 D_r(ν) 進行八等分（見圖 7），在染色時依次把較大的數字放在 1/8 角域里進行排列，這樣就避免了對染色方案的重復驗證。圖 8 的 D_{3, 7, 3}就是一個很直觀的例子。

蘇威卡塞烏斯和海勒所做的第二個簡化是不再單純地以格點為一個染色單位。他們在 D_r(ν) 中選取五個相鄰的格點，構成一個加號型區域，以這樣的加號型區域為一個單位進行染色。也就是說，可以只考慮把某個數字填入這個加號型區域，但暫時不考慮具體放在這個加號型區域的哪個格點。在排列好加號型區域的染色方案后，再對每個格點進行染色。

正如同行所評價的：蘇威卡塞烏斯和海勒不只是在解決問題，他們更是在優化組合學的研究思路。在不懈的努力下，歷時四個月，他們最終攻克了平面 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之家所有文章均包含本聲明。