主題

完美著色配方--談X色定理

伍德‧瓦懷特 | 2021-09-19 13:51:15 | 巴幣 270 | 人氣 279

  好幾個月沒有寫談天說數專欄了,離上一篇都間隔九個月。一方面是要找些盡量不牽涉太複雜式子或觀念的的題材不是那麼容易,另一方面大家也很熱愛伍德的提問箱,總讓伍德有料能大家聊,當然最大原因還是懶。但話說回來,要是伍德都不發文,原本就已經很稀薄的存在感大概會更加縹緲吧。

  開場白說得有些太長了,來聊聊今天的問題吧!今天的問題不需要複雜的方程式,也還算跟大家的生活相關──大家還記得上次看地圖是什麼時候嗎?這裡伍德說的不是Google街景地圖或有畫出山脈、氣候那類精細的圖,而是像是地理課本每章一開始,只用各種顏色分隔不同國家的圖。大家有數過除了用來表示海洋、湖泊水域的藍色之外,總共用了多少顏色嗎?

  而這就是今天的問題:「隨便給定一張地圖,最多需要幾種顏色就能將其上色完成?
  當然,這裡的「上色」要求相鄰的不同國家(像是美國和加拿大)需要上不同的顏色(像是田的左上和右下角,只有一個點碰到沒關係)。而地圖可以長得奇形怪狀,不必然是地理課本的世界地圖割一塊下來。

  這個問題在眾多數學問題裡,用白話敘述起來很簡單,但證明卻意外困難。最後的答案需要的顏色不多,也被冠上「X色定理」的名字(X是答案),許多數學科普書也會提及,或許你也聽過。這裡伍德先把答案遮起來,是希望藉機談談切入問題的思路。而這類談論圖、事物關聯的數學問題一般歸在「圖論」(Graph Theory)下,是離散數學的分支。不只數學系,在寫程式規劃演算法時,圖論也有不少應用。

一、夾出答案
  一般看到這類問題,首要任務不是證明,而是先猜出答案。直覺好的天才或許可以馬上猜到,但我們普通人還是得慢慢來,先猜個範圍。要多少顏色就保證夠呢?或許可以從生活經驗下手,常看見的地圖再多彩,似乎六七種就很多了(不含標示地形等特殊要求),保守一點猜,搞不好八種?至少先猜出個上界,在這裡我們指的是八種一定夠。

  另一個方向是去猜幾種顏色一定不夠。將一個圓形切成三等分的扇形,一定要三種顏色才夠,所以至少知道兩種不夠。事實上下面的圖形一定需要四種顏色(大家可以自己試試看三種夠不夠)。所以至少需要四種。


  從上面的討論,我們猜答案是至少四種到八種之間。而這時數學家們才會再繼續往下細想,一步一步把答案逼出來。那麼再往下的證明伍德在科普專欄就不深究,直接捏他(?)大家最後結果:只要四種顏色就能保證上色完所有地圖。這個定理也因此被後世稱為「四色定理」。

二、四色定理
  四色定理的起源是1852年由南非數學家法蘭西斯‧古德里(Francis Guthrie)所提出,當時他看了許多地圖,發現四種顏色似乎就夠了。在和家人的書信往返後,這個問題輾轉傳到當時的數學圈,其中奧古斯塔斯‧德摩根(Augustus De Morgan)*1對這問題很有興趣,也把它推廣給其他數學家研究。

  時間來到1879年,律師兼數學家阿爾弗雷德‧肯普(Alfred Kempe)提出了四色定理的證明──但是是錯的。這個錯誤在1890年,由另一位數學家彭西‧西伍德(Percy Heawood)指出,但西伍德除了證明肯普是錯的之外,也只能證明「五個顏色一定夠」的「五色定理」,離四色定理還是差了臨門一腳。有趣的是,當時的數學學界也認為這臨門一腳大概不難,自己不解決也總會有好事者解決*2,而讓研究在歐洲停滯。相關研究由美國承繼,但一時也沒有重大發展。

  於是又過了一個世紀,四色定理終於在1976年,由凱尼斯‧阿佩爾(Kenneth Appel)和沃夫岡‧哈肯(Wolfgang Haken)兩位數學家完成證明,但這證明偏偏不是人人買單。怎麼回事呢?原來兩人的證明到了最後一步,將所有圖都只需要四色,簡化到檢驗1936種圖(之後的證明版本簡化到633種)能被四色上完就夠了,而這最後一步──使用了電腦

  在2021年的現在看來,使用電腦根本不是什麼大不了的事情。但在約半個世紀前,「沒有用手算」的證明在某些數學家看來可是離經叛道。事實上,直到今日也仍有數學家在尋找不需要電腦,比較簡潔的證明。雖說伍德不算數學家,但真要我說,只要電腦的演算法能正確達成要求,在證明過程中使用電腦又有何不可呢?雖然可能是個比較暴力直接而不巧妙的證明,但至少是把問題解決了。當然,審查時的重點就得放在演算法是否正確了。

  時至今日,大部分人都承認使用電腦的證明,即便仍有人繼續研究,也只是為了找出更精簡、不須電腦的證明,而沒有對其正確性再有質疑。四色定理大概是第一個透過電腦證明的知名定理,爾後在圖論、甚至更多領域中也有不少透過電腦輔助證明的定理,甚至今日的研究可說已經離不開電腦了。當代一個有趣的問題是能不能讓人工智慧思考定理證明,甚至自己發現有趣的定理──會是個好科幻題材,不過伍德不是專家,也說不準,就留給大家自行想像吧!

  下一次有機會的話我們來聊聊圖論裡另一個也很有趣的問題:「拉姆齊(Ramsey)問題」。它最初的敘述很簡單、也很白話,但似乎挺令人意外:「任意六個人裡面,一定抓得出相互認識的三人,或相互不認識的三人」。到底怎麼回事,我們下期分曉。

  那麼這次就先跟大家聊到這裡,伍德說數,我們下次見!

*1. 這位就是各位高中或大學邏輯課裡學到「德摩根定律」的那位德摩根(狄摩根)。
*2. 甚至當時不少教授把四色定理的證明出成回家作業──沒錯,別以為大學教授都知道回家作業的解答...(但大多數還是知道的。)
送禮物贊助創作者 !
0
留言

創作回應

灰塵
又學到了一些知識ˊˇˋ
2021-09-20 10:33:26
伍德‧瓦懷特
下次看地圖數數看有幾種顏色(X?)
2021-09-20 10:43:12
老周(LeviChou)
跟機率不太熟欸,因為領域關係我接觸比較多偏微分方程的東西,但那個拉姆齊問題我覺得可以簡化成這樣:

Claim: 在二維平面上,有六個互相不共線的點ABCDEF,點與點可能連線、可能不連線(就像可能互相認識、可能不互相認識)。如果沒有形成三角形(就像如果找不到互相認識的三個人),則可以找出彼此之間沒有任何線相連的三個點(就一定可以找到互相不認識的三人)
Proof:
case 1: 沒有任何點與其他點有連線->trival
case 2: 每個點最多只有連出一條線,比如說A只跟B有連線,則A只要找C跟D就可滿足
case 3: 每個點最多只連出兩條線,且這兩條線連出去的點彼此不相連,比如說A同時與B和C之間有連線,可是B跟C不相連。
3a. B或C其中一個只與A相連->看另外一個跟誰連線,比如說B跟D又連線但C就只跟A,那BCE彼此之間就都完全沒有連線
3b. B跟C各別與另外一個點連線,比如說B跟D、C跟E之間有連線->BCF
3C. B跟C與同一個點有另外連線,比如說B跟D、C跟D之間有連線->BCE



我本來在思考能不能用集合的觀點去證明但是這種彼此之間有關係的分成集合好難,所以就很潦草地寫了
2021-09-20 22:06:24
伍德‧瓦懷特
啊啊啊不要捏他下集內容啊啊啊(欸)
其實這也不是機率啦,是圖論XD
我沒有仔細審證明過程,但我想這個思路雖然跟我預計寫的方法有些微差別,應該是可行的。(也的確是換成點和線來想)
不過需要稍微修一下,像是Case 2裡C和D如果恰恰好連線的話,就要找ACE這樣。
那個我會提的方法真的蠻厲害的(當然不是我想的),出乎意料地短XD
2021-09-21 04:34:36
項熙
我看不是很懂,但我知道要祝伍德鴿中秋節快樂!
2021-09-20 23:04:06
伍德‧瓦懷特
嗯,果然應該多配點圖...
也祝你中秋快樂呀!
2021-09-21 04:35:12
熟魚片
沒用的知識增加了(

我覺得目前的圖配文字看得懂,只是不懂四個顏色的證明過程xd但寫出來想必也看不懂,還是算了!
2021-09-22 12:58:46
伍德‧瓦懷特
嗚嗚嗚寫半天被說沒用QAQ (玻璃心)
那個證明過程我省略沒寫,光是解釋大概就能寫好幾個禮拜──前提是我也要看得懂QAQ
2021-09-22 13:02:02
悠閒紅茶(冷卻中)
伍德伍德!請問只是看了前面一眼就一頭霧水是正常的嗎?
2021-10-15 21:43:37
伍德‧瓦懷特
嗚嗚嗚我會努力檢討自己的敘事技巧QQ
2021-10-16 05:07:01

相關創作

更多創作