-
四色定理
鎖定
四色定理(世界近代三大數學難題之一),又稱四色猜想、四色問題,是世界三大數學猜想之一。
四色問題的內容是“任何一張地圖只用四種顏色就能使具有共同邊界的國家着上不同的顏色。”也就是説在不引起混淆的情況下一張地圖只需四種顏色來標記就行。
用數學語言表示即“將平面任意地細分為不相重疊的區域,每一個區域總可以用1234這四個數字之一來標記而不會使相鄰的兩個區域得到相同的數字。”這裏所指的相鄰區域是指有一整段邊界是公共的。如果兩個區域只相遇於一點或有限多點就不叫相鄰的。
- 中文名
- 四色定理
- 外文名
- Four color theorem
- 別 名
- 四色問題,四色猜想
- 提出者
- 格斯里(Francis Guthrie)
- 提出時間
- 1852年
- 適用領域
- 地圖編輯
- 應用學科
-
拓撲學
圖論 - 類 別
- 世界近代三大數學難題之一
四色定理簡史
四色定理問題的提出
1852年,畢業於倫敦大學的格斯里(Francis Guthrie)來到一家科研單位搞地圖着色工作時,發現每幅地圖都可以只用四種顏色着色。這個現象能不能從數學上加以嚴格證明呢?他和他正在讀大學的弟弟決心試一試,但是稿紙已經堆了一大疊,研究工作卻是沒有任何進展。
[1]
1852年10月23日,他的弟弟就這個問題的證明請教了他的老師、著名數學家德·摩爾根,摩爾根也沒有能找到解決這個問題的途徑,於是寫信向自己的好友、著名數學家哈密頓爵士請教,但直到1865年哈密頓逝世為止,問題也沒有能夠解決。
[1]
四色定理肯普的研究
大家都認為四色猜想從此也就解決了,但其實肯普並沒有證明四色問題。11年後,即1890年,在牛津大學就讀的年僅29歲的赫伍德以自己的精確計算指出了肯普在證明上的漏洞。他指出肯普説沒有極小五色地圖能有一國具有五個鄰國的理由有破綻。不久泰勒的證明也被人們否定了。人們發現他們實際上證明了一個較弱的命題——五色定理。就是説對地圖着色,用五種顏色就夠了。
[2]
不過,郝伍德沒有徹底否定肯普論文的價值,運用肯普發明的方法,郝伍德證明了較弱的五色定理。一方面,五種顏色已足夠,另一方面,確實有例子表明三種顏色不夠。
四色定理肯普的貢獻
肯普是用歸謬法來證明的,大意是如果有一張正規的五色地圖,就會存在一張國數最少的“極小正規五色地圖”,如果極小正規五色地圖中有一個國家的鄰國數少於六個,就會存在一張國數較少的正規地圖仍為五色的,這樣一來就不會有極小五色地圖的國數,也就不存在正規五色地圖了。這樣肯普就認為他已經證明了“四色問題”,但是後來人們發現他錯了。
[2]
[1]
不過肯普的證明闡明瞭兩個重要的概念,對以後問題的解決提供了途徑。第一個概念是“構形”。他證明了在每一張正規地圖中至少有一國具有兩個、三個、四個或五個鄰國,不存在每個國家都有六個或更多個鄰國的正規地圖,也就是説,由兩個鄰國,三個鄰國、四個或五個鄰國組成的一組“構形”是不可避免的,每張地圖至少含有這四種構形中的一個。
[2]
[3]
肯普提出的另一個概念是“可約”性。“可約”這個詞的使用是來自肯普的論證。他證明了只要五色地圖中有一國具有四個鄰國,就會有國數減少的五色地圖。
自從引入“構形”,“可約”概念後,逐步發展了檢查構形以決定是否可約的一些標準方法,能夠尋求可約構形的不可避免組,是證明“四色問題”的重要依據。但要證明大的構形可約,需要檢查大量的細節,這是相當複雜的。
[2]
[3]
四色定理緩慢的進展
人們發現四色問題出人意料地異常困難,曾經有許多人發表四色問題的證明或反例,但都被證實是錯誤的。後來,越來越多的數學家雖然對此絞盡腦汁,但一無所獲。於是,人們開始認識到,這個貌似容易的題目,其實是一個可與費馬猜想相媲美的難題。
進入20世紀以來,科學家們對四色猜想的證明基本上是按照肯普的想法在進行。
1913年,美國著名數學家、哈佛大學的伯克霍夫利用肯普的想法,結合自己新的設想;證明了某些大的構形可約。後來美國數學家克莉絲汀·拉德-富蘭克林於1939年證明了22國以下的地圖都可以用四色着色。
1950年,温恩從22國推進到35國。
四色定理計算機證明
高速數字計算機的發明,促使更多數學家對“四色問題”的研究。電子計算機問世以後,由於演算速度迅速提高,加之人機對話的出現,大大加快了對四色猜想證明的進程。就在1976年6月,在美國伊利諾斯大學的兩台不同的電子計算機上,用了1200個小時,作了100億個判斷,結果沒有一張地圖是需要五色的,最終證明了四色定理,轟動了世界。
[1]
[5]
第一個計算機解是由美國數學家Appel和Haken與運用計算機的專家Kock三人合作的成果
[6]
。這是一百多年來吸引許多數學家與數學愛好者的大事,當兩位數學家將他們的研究成果發表的時候,當地的郵局在當天發出的所有郵件上都加蓋了“四色足夠”的特製郵戳,以慶祝這一難題獲得解決。
四色定理影響
數學家們為證明這條定理絞盡腦汁,所引進的概念與方法刺激了拓撲學與圖論的生長、發展。
在“四色問題”的研究過程中,不少新的數學理論隨之產生,也發展了很多數學計算技巧。如將地圖的着色問題化為圖論問題,豐富了圖論的內容。不僅如此,“四色問題”在有效地設計航空班機日程表,設計計算機的編碼程序上都起到了推動作用。