四色定理 (Four Color Theorem)

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

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

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

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

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

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

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

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

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

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

相關參考網址:

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