四色定理.docVIP

四　色　定　理 1852年，一名倫敦大學畢業生格思里提出猜想：每幅地圖都可以只用四種顏色著色，使得有共同邊界的國家塗上不同的顏色。為了判定這猜想的真偽，百多年來數學家不斷努力。 1879年，肯普發表了一個證明，後來被發現有漏洞，但卻可證明五色定理。 1940年，溫恩證明了任意35個或以下區域的地圖，只需要四種顏色著色。 在最終得到證明前，區域的數目最高曾經達到96。 1976年，數學界發生一件大事，兩名美國數學家利用電腦，經過1200小時的四色猜想證明為四色定理。 四色定理：替所有想像得到的地圖著色，有共同邊相鄰的區域不同色的話，最多只需要四色！ 在數學史上，有許多有趣的發現，這些發現看似簡單，可是卻往往難以解答！其中一個這類的問題，就是著名的『四色定理』。這個定理說什麼呢？先讓我們來了解一下： 四色定理：替所有想像得到的地圖著色，有共同邊相鄰的區域不同色的話，最多只需要四色！ 好，現在就讓維尼哥哥先說個故事，再來講講這個定理的來龍去脈！ 相傳，古時候有一個國王，臨終前留下一份遺囑，告訴五位王子，如果想各自立國的話，可以將國土分成五份，但是，每一小國都必須和其他四小國有共同的國界，否則不准分開！ 國王去世後，五位王子急忙想分割國土，但是，不論怎麼分，就是無法達成國王的要求，讓每一小國都和其他四小國有共同的國界。後來，一位大臣拿出一個錦囊，裡面放了一封國王親筆寫的信，內容說道：『親愛的王子們，我的遺囑是一道永遠也解不開的難題，我這樣要求是希望你們親密團結在一起，永遠不要分開。』於是，王子們和睦共處，將國家共同治理得非常好。 這個故事不知是真是假，但是，故事裡可以知道：如果想將一個區域分成五小塊話，絕對不可能讓每一小塊都與其他小塊有共同邊。這表示什麼呢？這表示要替一個有五個區域的地圖著色的話，最多只需要四色就好了！ 西元1852年，一位英國的業餘數學家弗朗西斯．格斯里閒來沒事，拿起色筆替一份英國的分郡地圖著色的時候，突然異想天開：『如果要替所有想像得到的地圖著色，而且有共同邊相鄰的區域都不同色的話，最多需要幾種顏色呢？』 這個問題流傳到數學界，許多數學家深入地思考與嘗試之後，發現找得到的例子裡，都只需要四種顏色就可以了！但是，這不夠，必須找出一種嚴謹的數學證明，可以涵蓋任何地圖才行。 到了1879年，當時英國的數學家肯普提出一份論文，似乎證明了這個『四色猜想』，而大家也都以為這個問題已經解決了。沒想到十一年後的1890年，數學家希伍德找出了肯普的錯誤，推翻了他的證明。但是希伍德自己卻證明出『五色定理』，也就是說最多不會超過五種顏色！ 不過後來的進展就非常緩慢了！一直到了1970年，數學家才證明出所有少於三十九個區域的地圖，『四色猜想』是對的。 但是，如果有一千個區域，要等到哪一年才能證明出來呢？於是，有人從不同的方向著手，並成功地將無限多的地圖簡化成1482種基本圖。 問題是：每種基本圖的顏色組合，就幾乎已經等於無限多了，想要以人工來驗證這一千多種基本圖，根本是不可能的！ 還好，電腦的出現，解決了這個難題！在1975年，數學家利用三台當時最先進的大型電腦，總共花了一千兩百小時的計算，分析驗證了1482種基本圖之後，終於證明成功，而使『四色猜想』正式成為『四色定理』！ 參考網址： /iclub_files/a/1/68/subjectworld_cabinet/1394/1726/3098/Colour4final.htm 所謂四色問題, 其敘述非常簡單： 一張平面地圖, 如果要求共邊 (只有共點的不算) 之兩個區域塗上不同顏色, 則至多只需要四種不同顏色. 讀者可以翻開任何地圖冊, 不論是世界地圖還是臺灣的鄉鎮圖, 試著按照上述規則著色, 就會發現 (如果足夠認真), 總是使用四種以內的顏色就夠了. 讀者也可以自己拿一張紙, 畫出任意奇特的假想地圖, 然後試著著色. 例如以下的假設性地圖. 根據歷史上知道的記錄, 四色問題首先由英國的 Francis Guthrie 在 1852 提出. 當時他在畫英國各郡的地圖, 而發現了這個現象. 經過許多實驗之後, 他歸納出一個結論, 就是: 最多只需要四種不同顏色, 就可以畫任何地圖. 他將這個心得告訴了他的兄弟: Frederick Guthrie. 後者又請教了當時英國最主要的數學家: deMorgan. 這個問題首次見於文獻, 是在 1878 年, 由 Cayley 所寫. 就在問題傳出去之後, 立刻就有所回響. 在 1879 年 Kempe 發表了一個證明; 1880 年 Tait 也發表了一個證明. 事隔十一年後, 這兩個證明分別被 Heawood 和 Petersen 發現是有錯的. 但是, 兩個錯誤的嘗試都有所貢獻. Kempe 的論述, 其實是證明