四色定理:數學定理-中文百科頻道

發展簡史

來自地圖的啟示

相傳四色問題是一名英國繪圖員提出來的此人叫格思裡。1852年他在繪制英國地圖的發現如果給相鄰地區塗上不同顔色那麼隻要四種顔色就足夠了。需要注意的是任何兩個國家之間如果有邊界那麼其邊界不能隻是一個點否則四種顔色就可能不夠。

格思裡把這個猜想告訴了正在念大學的弟弟。弟弟認真思考了這個問題結果既不能證明也沒有找到反例于是向自己的老師、著名數學家德·摩根請教。德·摩根解釋不清當天就寫信告訴自己的同行、天才的哈密頓。可是直到哈密頓1865年逝世為止也沒有解決這個問題。從此這個問題在一些人中間傳來傳去當時三等分角和化圓為方問題已在社會上“臭名昭着”而“四色瘟疫”又悄悄地傳播開來了。

問題的證明一波三折

1878年凱萊正式向倫敦數學會提出了這個問題。凱萊可是英國響當當的數學家他看中的問題必定不同凡響。消息傳到了律師肯普的耳朵裡引起了他的極大興趣。不到一年肯普就提交了一篇論文聲稱證明了四色問題。人們以為事情到此就已經完結了。誰知到1890年希伍德在肯普的文章中找到一處不可饒恕的錯誤。

不過讓數學家感到欣慰的是希伍德沒有徹底否定肯普論文的價值運用肯普發明的方法希伍德證明了較弱的五色定理。這等于打了肯普一記悶棍又将其表揚一番總的來說是貶大于褒。真不知可憐的肯普律師是什麼心情。追根究底是數學家的本性。一方面五種顔色已足夠另一方面确實有例子表明三種顔色不夠。那麼四種顔色到底夠不夠呢？這就像一個淘金者明明知道某處有許多金礦，結果卻隻挖出一塊銀子你說他願意就這樣回去嗎？

接下去的戲就得由闵可夫斯基來演了。這裡得說他幾句好話他雖然沒有成功可自認第一流倒也并非自不量力。要知道19世紀末20世紀初德國格丁根大學能成為世界數學中心就是由于他和希爾伯特、克萊因“三巨頭”的努力。四色瘟疫在英國蔓延時還真沒有一個研究過它的數學家比得上闵可夫斯基。

令闵可夫斯基尴尬的一堂課

19世紀末德國有位天才的數學教授叫闵可夫斯基他曾是愛因斯坦的老師。愛因斯坦因為經常不去聽課便被他罵作“懶蟲”。萬萬沒想到就是這個“懶蟲”後來創立了著名的狹義相對論和廣義相對論。闵可夫斯基受到很大震動他把相對論中的時間和空間統一成“四維時空”這是近代物理發展史上的關鍵一步。

在闵可夫斯基的一生中把愛因斯坦罵作“懶蟲”恐怕還算不上是最尴尬的事……一天闵可夫斯基剛走進教室一名學生就遞給他一張紙條上面寫着“如果把地圖上有共同邊界的國家塗成不同顔色那麼隻需要四種顔色就足夠了您能解釋其中的道理嗎”

闵可夫斯基微微一笑對學生們說“這個問題叫四色問題是一個著名的數學難題。其實它之所以一直沒有得到解決僅僅是由于沒有第一流的數學家來解決它。”為證明紙條上寫的不是一道大餐隻是小菜一碟闵可夫斯基決定當堂掌勺問題就會變成定理……

下課鈴響了可“菜”還是生的。一連好幾天他都挂了黑闆。後來有一天闵可夫斯基走進教室時忽然雷聲大作，Minkowski很嚴肅的說：“上天被我的驕傲激怒了，我的證明是不完全的……”。

緩慢的進展

當時由大數學家黎曼、康托爾、龐加萊等創立的拓撲學之發展可謂一日千裡後來竟蓋過大數學家高斯寵愛的數論成為雍容華貴的數學女王。四色問題就是屬幹拓撲學範疇的一個大問題。拓撲學不僅引進了全新的研究對象也引進了全新的研究方式。對數學來說它不啻是一場革命。回顧拓撲學的曆史就可以說明為什麼四色問題對于20世紀數學來說是重要的。通俗地說連續變換就是你可以捏、拉一個東西但不能将其扯破也不能把原先不在一起的兩個點粘在一起。比如對于26個大寫英文字母一些拓撲學家就認為可将其分成3類

第一類

第二類

第三類。

第一類在連續變換下都可以變成第三類則都可變成I。

因為4是平面的色數它也是一種示性數可見示性數有很多種體現了平面的拓撲性質與國家的形狀無關将平面彎成曲面也沒關系。數學家必須确定這個數究竟是5還是4這很重要。如果國家分布在一個環面上畫地圖最多得要七種顔色。

吊起數學家胃口的還有一個原因。乍一看環面似乎更複雜事實上環面的七色定理卻比較容易證明希伍德當時就做到了到1968年其他所有複雜曲面的色數均已确定唯有平面或球面的四色問題依然故我。看來平面沒有人們想象的那麼簡單

1913年伯克霍夫引進了一些新的技巧導緻1939年弗蘭克林證明22國以下的地圖都可以用四色着色。1950年溫恩将22國提高為35。1968年奧爾又達到了39國。1975年有報道52國以下的地圖用四色足夠。可見其進展極其緩慢。

計算機幫助人們圓夢

不過情況也不是過分悲觀。數學家希奇早在1936年就認為讨論的情況是有限的不過非常之大大到可能有10000種。對于巨大而有限的數，最好由誰去對付？今天的人都明白：計算機。

從1950年起希奇就與其學生丢萊研究怎樣用計算機去驗證各種類型的圖形。這時計算機才剛剛發明。兩人的思想可謂十分超前。

1972年起黑肯與阿佩爾開始對希奇的方法作重要改進。到1976年他們認為問題已經壓縮到可以用計算機證明的地步了。于是從1月份起他們就在伊利諾伊大學的IBM360機上分1482種情況檢查曆時1200個小時，作了100億個判斷最終證明了四色定理。在當地的信封上蓋“Four colorssutfice”四色，足夠了的郵戳就是他們想到的一種傳播這一驚人消息的别緻的方法。

人類破天荒運用計算機證明著名數學猜想應該說是十分轟動的。贊賞者有之，懷疑者也不少，因為真正确性一時不能肯定。後來也的确有人指出其錯誤。1989年，黑肯與阿佩爾發表文章宣稱錯誤已被修改。1998年托馬斯簡化了黑肯與阿佩爾的計算程序但仍依賴于計算機。無論如何四色問題的計算機解決給數學研究帶來了許多重要的新思維。

定理定義

四色問題又稱四色猜想、四色定理是世界近代三大數學難題之一。地圖四色定理(Four color theorem)最先是由一位叫古德裡Francis Guthrie的英國大學生提出來的。德·摩爾根Augustus De Morgan1806-1871，1852年10月23日緻哈密頓的一封信提供了有關四色定理來源的最原始的記載。他在信中簡述了自己證明四色定理的設想與感受。一個多世紀以來數學家們為證明這條定理絞盡腦汁所引進的概念與方法刺激了拓撲學與圖論的生長、發展。1976年美國數學家阿佩爾K.Appel與哈肯W.Haken宣告借助電子計算機獲得了四色定理的證明又為用計算機證明數學定理開拓了前景。

地圖四色定理(Four color theorem)最先是由一位叫古德裡Francis Guthrie的英國大學生提出來的。四色問題的内容是“任何一張地圖隻用四種顔色就能使具有共同邊界的國家着上不同的顔色。”用數學語言表示即“将平面任意地細分為不相重疊的區域每一個區域總可以用1234這四個數字之一來标記而不會使相鄰的兩個區域得到相同的數字。”這裡所指的相鄰區域是指有一整段邊界是公共的。如果兩個區域隻相遇于一點或有限多點就不叫相鄰的。因為用相同的顔色給它們着色不會引起混淆。四色問題的内容是“任何一張地圖隻用四種顔色就能使具有共同邊界的國家着上不同的顔色。”也就是說在不引起混淆的情況下一張地圖隻需四種顔色來标記就行。

拓撲學問題，找出給地圖着色所需用的不同顔色的最小數目，使所有相鄰的區域都有不同的顔色。最早在1852年由一名英國數學學者F.格思裡提出。這個問題由K.阿佩爾和W.哈肯于1976年在計算機的輔助下驗算解決。

定理意義

一個多世紀以來，數學家們為證明這條定理絞盡腦汁，所引進的概念與方法刺激了拓撲學與圖論的生長、發展。在“四色問題”的研究過程中，不少新的數學理論随之産生，也發展了很多數學計算技巧。如将地圖的着色問題化為圖論問題，豐富了圖論的内容。不僅如此，“四色問題”在有效地設計航空班機日程表，設計計算機的編碼程序上都起到了推動作用。

定理推廣

雖然任何平面地圖可以隻用四個顔色着色，但是這個定理的應用卻相當有限，因為現實中的地圖常會出現飛地，即兩個不連通的區域屬于同一個國家的情況（例如美國的阿拉斯加州），而制作地圖時我們仍會要求這兩個區域被塗上同樣的顔色，在這種情況下，隻用四種顔色将會造成諸多不便。

實際中用四種顔色着色的地圖是不多見的，而且這些地圖往往最少隻需要三種顔色來染色。此外，即便地圖能夠隻用四種顔色染色，為了區分起見，也會采用更多的顔色，以提示不同地區的差别。

驗證推導

地圖上任何一個區域必将存在鄰域，且又通過鄰域與其他非鄰域發生間接聯系，我們可以将任何一個地圖以圖論圖形的表示出來。

假設存在一張至少需要種着色的地圖，那麼決定該地圖必須要用種着色的條件有且隻有一個，即該地圖至少存在這樣一個區域，與該區域相鄰的所有區域必須滿足着色。首先滿足這個條件後，隻能用第種顔色，其次如果這個推論一是錯誤的，對于着色地圖不存在這樣的區域，那麼地圖上任何一個區域的鄰域隻能滿足少于的着色，那麼整個地圖勢必不需要中顔色，這與假設相矛盾，所以這是一個充分必要條件。（推論一）

假設随意取一張任意結構的至少着色的地圖，其上滿足上述條件的區域有個，那麼将圖論圖形中的這個區域及其與鄰域的關系線我們可以全部去掉，這樣我們就将構建一個至少着色地圖的問題轉化成了一個在至少需要着色地圖上添加個滿足推論一條件的區域問題。

如果五着色地圖存在且能構建成功，那麼必然存在構建這樣五着色的四着色模型圖，而要存在這樣的四着色模型圖必然存在構建該四着色的三着色模型圖，同理要存在這樣的三着色模型圖必然要存在構建它的二着色模型圖，那麼我們來構建一下五色圖是否存在：

二着色地圖是由一着色而來的一種簡單的着色地圖模型，我們很容易得到滿足二着色的地圖僅有的兩種類型的結構，一種是不閉合的鍊狀結構，如圖一；另一種是由第一種衍生出來的閉合的環狀結構且環所聯系的區域為偶數個，稱為偶數環，如圖二。

我們看下二着色結構特點發現，圖一圖二都是一個原理就是奇偶位置決定着色，任何兩個區域的任何聯系鍊條隻有相隔偶數個區域才滿足兩區域着色不同，我們定義這兩個區域為偶隔域。

我們随意取一張任意結構的二着色的地圖，來構建一個具有個滿足推論一條件區域的地圖，構建方式有且隻有一個，就是在圖論圖形中我們如何去掉的這個區域及其與鄰域的關系線，我們接怎麼給它添加回去。我們任取這個區域中一個區域為例，隻要我們在地圖上将必須滿足二着色的幾個區域直接聯系到上，這樣就滿足推論一中的條件而使必須為三着色。

而要滿足二着色則必定含有偶隔域，如果有個區域和發生直接聯系，則上出去的關系線有個，那麼我們一定可以将該複雜的聯系分解成個不可分解關系環，其中至少有一個不可再分的關系環是中的偶隔域與聯系的，（推論二）假設這個推論是錯誤的，所有不可再分的環全部是奇隔域，那麼這些環拼接回去時滿足每個小環的間隔區域數相加再減去共用的區域，仍舊是奇隔域，這樣便不滿足二着色，所以這些不可再分環中一定有偶隔域和發生聯系而構成奇數環（環連的區域為奇數），并且導緻必須使用第三色的就是這些不可再分的奇數環。

由于滿足二着色的隻有偶隔域一種條件，那麼構造的三着色地圖中決定三着色的條件也隻有一種，存在不可再分的奇數環。

在上面構建的三色着色地圖基礎上我們再來構建四着色地圖，假如存在滿足推論一條件的區域有個，同樣的方法，我們任取中一個區域，隻要我們在地圖上将必須滿足三着色的幾個區域直接聯系到上，這樣就滿足推論一中的條件而使必須為四着色。

而要滿足三着色則必定含有奇數環并且組成奇數環的區域都能夠與發生聯系（保證奇數環沒有被包圍在其他閉合環内的部分），如果有個區域和發生直接聯系，則上出去的關系線有個，那麼導緻為第四色原因是可發生聯系的奇數環，既隻要有一個這樣的奇數環存在就一定會導緻使用第四色（推論三），假設這一推論不成立那麼沒有這樣的奇數環存在，則由前面二着色建立三着色正經得到，除了奇數環再沒有能使地圖為三着色的條件了，或者當奇數環區域不能全部與發生聯系，這樣必然的不需要第四色了。

故我們的推論三成立。由于三着色條件唯一而使得四着色的條件唯一，我們來看四着色條件的特點，當與發生聯系後，不管有多少滿足條件的奇數環，勢必最終隻能有包括在内的三個區域能與外界區域發生聯系。因為和上的任何兩個區域都可以構成一個封閉的三角形，而當我們選的上這倆區域與關系線是最外側的關系線時，則上其他區域一定不能在三角形外，不然或造成以上兩根關系線不再是最外側或者有關系線出現交叉，所以上剩馀區域必定在三角形内而造成四着色圖最多隻有三個區域能與外界發生聯系。