古典着色問題的新時代算法_風聞
返朴-返朴官方账号-关注返朴（ID：fanpu2019）,阅读更多！07-25 09:59
撰文 | 含英
年幼的你會對着書房牆面上的世界地圖發呆嗎？凝視着那五顏六色的圖案，暢想着自己將來有一天能夠環遊世界。而在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,……}為整數集，每個整數代表一個頂點，兩個相鄰的整數記為兩個相鄰的頂點，兩個整數之間的距離定義為他們差值的絕對值。構造映射如下：
正如同行所評價的：蘇威卡塞烏斯和海勒不只是在解決問題，他們更是在優化組合學的研究思路。在不懈的努力下，歷時四個月，他們最終攻克了平面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
本文受科普中國·星空計劃項目扶持
出品：中國科協科普部
監製：中國科學技術出版社有限公司、北京中科星河文化傳媒有限公司
1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。
2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。
版權説明：歡迎個人轉發，任何形式的媒體或機構未經授權，不得轉載和摘編。轉載授權請在「返樸」微信公眾號內聯繫後台。