四色定理 (Four Color Theorem)

原本, 這叫做四色猜想(Four Color Problem), 不過現在已被證實, 成為一個定理了.

今天剛好遇上要討論一個四色灰階的LCD是否足夠表現一張完整的地圖, 因此, 就開始稍稍說明了一下四色定理.

四色猜想被認為是費馬最後定理相媲美的難題. 猜想的內容很簡單, 但是證明卻很難. 目前的證明極為複雜, 是由電腦所算出的, 仍不斷的有數學家在找尋更簡單的證明方法.



西元1852年,一位英國的業餘數學家弗朗西斯.格斯裡閒來沒事,拿起色筆替一份英國的分郡地圖著色的時候,突然異想天開:『如果要替所有想像得到的地圖著色,而且有共同邊相鄰的區域都不同色的話,最多需要幾種顏色呢?』

這個問題流傳到數學界,許多數學家深入地思考與嘗試之後,發現找得到的例子裡,都只需要四種顏色就可以了!但是,這不夠,必須找出一種嚴謹的數學證明,可以涵蓋任何地圖才行。

到了1879年,當時英國的數學家肯普提出一份論文,似乎證明了這個『四色猜想』,而大家也都以為這個問題已經解決了。沒想到十一年後的1890年,數學家希伍德找出了肯普的錯誤,推翻了他的證明。但是希伍德自己卻證明出『五色定理』,也就是說最多不會超過五種顏色!

不過後來的進展就非常緩慢了!一直到了1970年,數學家才證明出所有少於三十九個區域的地圖,『四色猜想』是對的。

但是,如果有一千個區域,要等到哪一年才能證明出來呢?於是,有人從不同的方向著手,並成功地將無限多的地圖簡化成1482種基本圖。

問題是:每種基本圖的顏色組合,就幾乎已經等於無限多了,想要以人工來驗證這一千多種基本圖,根本是不可能的!

還好,電腦的出現,解決了這個難題!在1975年,數學家利用三台當時最先進的大型電腦,總共花了一千兩百小時的計算,分析驗證了1482種基本圖之後,終於證明成功,而使『四色猜想』正式成為『四色定理』!

相關參考網址:

四色問題
四色定理
The Four Color Theorem
Four-Color Theorem


意見

hoi tin 提到...

四色定理真的很難嗎?我們能不能用反方向來想,有何種情況下一定要用五種色。
一定要用五種色的情況是五個地區都互相連接,如A要連接B、C、D、E,B要連接A、C、D、E,C要連接B、A、D、E,……。但是這個假設是不能成立的,因為只要四個地區互相連接,有一個地區必定被其他三個地區包圍,所以在中間的那個地區必定不能跟第五個地區連接。而當第五個地區連接前四個地區時只要用被包在中間地區的色就可以一直無限放大地圖。
如果我的想法有任何不對的地方,請電郵給我指教。謝謝。

提到...

四色定理會比想像中來得難, 最主要是因為形狀. 一個地區的形狀通常不會是某種固定的幾何圖形, 所以地區之間的連接會變得很複雜. 維基百科上就有一個圖形可以做為四色定理範例

中學二年級 提到...

我的想法跟hoi tin一樣
因為一個扭曲的形狀,我們可以把它識為一個點,而在平面上
此點與另一點連線的含意便是相鄰,而平面上要畫出一區塊只要三個點(三角形)
,而此三角形的三點是相連的(相鄰)
。因此當有四個形狀圖形出現時,且互相相鄰,必有一個在中間(畫成點的話就是
4個點中,互相連線必有一點在三角形內)
『※一連線不可與另一連線相交,否則違反相鄰的定義。』因此4個行狀互相相鄰必有一個在中間,其餘的便類似hoi的理論了