分享本文至 E-mail 信箱
學術引用格式
MLA
APA
EndNote(.enw)

停擺 60 年的《哈德維格-納爾遜問題》在一位生物學家的手上有了新突破!

  • 文/陳宏賓 │ UniMath 主編、中興大學應用數學系助理教授。

圖論 (Graph Theory) 在數學領域是專門研究一群物件與物件彼此關聯的學問。將要研究的對象物件以頂點視之,兩個物件若有關聯則連接一條邊,圖論主要是研究這個抽象化後由頂點集邊集所構成的圖的性質。

圖論 (Graph Theory) 是專門研究一群物件與物件彼此關聯的學問,其中著色問題可以說是圖論中最經典的研究主題之一。圖 / wikipedia

著色問題可以說是圖論最經典的研究主題之一,透過著色,我們可以將圖分類,這個是可以 2 著色的圖,那個是可以 5 著色的圖……。如果有人問你數學家都在做什麼工作?有一個我認為還不錯又簡單的答案,那就是「分類」。各種領域的數學家都在忙著分類,而「著色數」是圖的一項重要分類指標。

讓人困擾60年的《哈德維格-納爾遜問題》

1950 年,就讀芝加哥大學的大學生愛德華 · 尼爾森 (Edward Nelson) 提出了一個困擾數學家多年的著色問題。在二維平面上,任意選一些頂點,如果頂點間的距離是 1 個單位,就把這兩頂點連接一條邊,這種圖稱為單位距離圖 (unit-distance graph)。尼爾森好奇平面上隨便一個這樣子的圖,「點著色數」是多少呢?

「點著色」要求將圖的所有頂點著色,且彼此有邊的頂點必須要塗不同色。而一個圖的「點著色數」就是滿足上述要求的方法中使用最少的顏色數。如果把平面上無限多個點都當成頂點,這個擁有無窮多個頂點和無窮多條邊的圖的點著色數是多少呢?這就是困擾圖論專家一甲子的《哈德維格-納爾遜問題》(Hadwiger-Nelson problem)。

這個問題之所以有名其實是拜已故數學科普大師葛老爹 (Martin Gardner) 之賜,他後來將這個難題寫下來刊載在《科學美國人》,除了吸引不少業餘數學愛好者的目光,也引起不少知名圖論專家的興趣,其中包括了赫赫有名的艾狄胥 (Paul Erdos)。即便如此,集結眾人之力還是沒能完全解開這道難題。不過也不是無功而返,數學家們很快地就將這個涉及到無窮圖的難題的正確答案,限縮到一個乍看不可思議的小範圍──介於 4 到 7 之間

「開玩笑吧?!一個無窮多個頂點和邊的圖,這麼複雜的圖居然只要最多 7 色就能夠完成點著色。」我想許多讀者心裡會有這樣的 OS,事實就是如此,詳情我們稍後揭曉。

但正確答案究竟是什麼其實還是無人知曉,不過就在今年四月格雷 (Aubrey de Grey) 丟了一篇論文證明:四個顏色不夠用。讓正確答案的範圍又縮小了,只剩下 5、6、7 三種可能。不過,別小看他這一手,雖然看似輕鬆,其實困擾了眾多數學家六十年啊!

而令人感到驚奇的是,突破僵局的格雷教授並不是專門搞數學的,他的身份是一位致力於長生不老的生物學家,某天在玩棋盤遊戲時突發奇想突破了難關。

生物學家格雷 (Aubrey de Grey)。 圖 / Wikipedia

在此之前,格雷有一項著名事蹟廣為人知,他主張「老化是一種疾病」,只要掌握住關鍵的幾個要素,就能夠抗老,預言人類未來將可以活到一千歲,而且第一個活到一千歲的人已經誕生在世界上了。不論你信不信,我個人希望這件事不要成真,不然五十代同堂可不得了,光是過年吃個年夜飯,連洗碗都有問題啊啊啊!不過,跟秦始皇一樣對於長生不老有興趣的讀者還是參考一下 TED TALK 他的演講《A roadmap to end aging》。

 

為什麼無限多個點,只要有限個顏色就夠畫了?

其實用最簡單的方式, 9 色就可以順利完成了。理由很簡單,考慮一個邊長 2/3 單位的正方形,最遠的兩點落在對角線的兩個頂點上,簡單利用畢氏定理知道對角線長度不足 1 單位,因此,整個正方形可以塗單一色。接著用 9 個不同顏色的同尺寸正方形,排成九宮格。

再重複把這九宮格平移貼上,規律地鋪滿整個平面就完成了。檢查一下:看看是不是任意一個點,跟距離它 1 單位的點都塗不同色呢?

六十年前 7 色的塗法採用類似的概念,只不過用「正六邊形」取代「正方形」來鋪滿整個平面,中間一個加上外圍六個不同色的正六邊形,就是7色的塗法。

那為什麼至少需要 4 色呢?

首先畫兩個單位圓通過彼此的圓心,則兩圓心距離為 1,且兩交點距離圓心也是 1,因此光這四個頂點至少要用掉三個顏色才行。

複製中間這個菱形,將兩個菱形的上頂點釘在一起,分別向左右兩邊旋轉,直到下頂點彼此距離為 1 時停止,此時,兩個下頂點的顏色也被迫要相異,因此三個顏色已經不夠用了,不得已只好使用第四個顏色。這個 7 頂點的圖是需要四色的最小範例,由 Leo 和 William Moser 兩兄弟數學家所提出,後來被稱為莫澤圖(Moser spindle)。

格雷帶來的突破

同樣的道理,要證明 4 色不夠用的方法就是找一個至少需要 5 色的例子。格雷受到莫澤圖的啟發,依照三四個步驟,一步一步建構出一個有著兩萬多個點的圖,這個圖無法只用 4 色完成著色。驗證這個反例可不容易,想像光是頂點數量超過兩萬的圖有多複雜,更別說要驗證 4 個顏色夠不夠用。此時,演算法就派上用場,寫個高效率的程式交給電腦處理就行了。

Aubrey de Grey後來完成點數較少的 1,581 版本。(點圖放大)圖/Olena Shmahalo/Quanta Magazine; Source: Aubrey de Grey

任何一個需要至少 5 色的圖都是這個問題的一項重大進展。數學家希望找到小一點且同樣需要 5 色的圖,最好當然是找到最小的那一種,如此一來就可以更深入地了解究竟需要 5 色的理由是什麼,怎樣的結構會造成顏色數增加,唯有透過不斷地分析解構,才可能更接近真相。格雷也和華裔數學家陶哲軒等人的 polymath 團隊合作,希望藉由團隊的力量將點數大幅度下降。果然,不久後,俄亥俄州立大學的數學家 Dustin Mixon 和 Boris Alexeev 找到一個有 1577 個點的圖。沒多久,德州大學奧斯汀分校的資訊科學家 Marijn Heule 將點數縮小到 874,之後又進一步下降到 826。

雖然有進展,但這 826點的圖還是有點難分析啊。(點圖放大)圖/Olena Shmahalo/Quanta Magazine; Source: Marijn Heule

一系列的改進給沉寂 60 年的 Hadwiger-Nelson 問題帶來一道曙光。不過,要決定正確答案究竟是多少,恐怕還得需要更多時間才有機會解開謎底,這時候,我心裡反倒暗暗希望格雷的一千歲理論是對的了。

註解:

有人可能會將這個「把平面上所有點著色的問題」跟四色定理那個「把平面圖的點著色問題」搞混;平面圖是指可以把圖畫在平面上讓邊都不交叉。四色定理是在平面圖上著色,而本文討論的不是平面圖。

參考資料:

您最近是不是也有以下的感受?

1.各類議題中的科學及專業知識日益複雜,想懂實在太難。

2.資訊爆炸、真假難辨、覺得無所適從,甚至想不聽不看。

3.擔心身邊的人受偽科學與謠言所誤,但不知道該怎麼辦。

這時候你需要「科學思辨力」幫助你,建立自己的邏輯、跨過複雜議題討論的門檻、提升資訊選擇、處理與溝通的能力。

用 12 堂課讓你成為更能面對未來變化的公民吧!從即刻開始到 9/18 晚上 10 點前,預購達 250 組即確定推出,更多資訊請見預購頁面

關於作者

UniMath

UniMath (You Need Math) 是一個 Online 數學媒體,我們的目的是成為一個線上平台,發表數學相關的科普文章及影音,使數學用更柔軟的姿態走入群眾,提升數學素養。