四色定理

四色定理（世界近代三大數學難題之一），又稱四色猜想、四色問題，是世界三大數學猜想之一。四色定理的本質正是二維平面的固有屬性，即平面內不可出現交叉而沒有公共點的兩條直線。很多人證明了二維平面內無法構造五個或五個以上兩兩相連區域，但卻沒有將其上升到邏輯關係和二維固有屬性的層面，以致出現了很多偽反例。不過這些恰恰是對圖論嚴密性的考證和發展推動。計算機證明雖然做了百億次判斷，終究只是在龐大的數量優勢上取得成功，這並不符合數學嚴密的邏輯體系，至今仍有無數數學愛好者投身其中研究。

基本介紹

• 中文名：四色定理
• 外文名：Four color theorem
• 別稱：四色問題，四色猜想
• 提出者：格斯里（Francis Guthrie）
• 提出時間：1852年
• 套用學科：拓撲學、圖論
• 適用領域範圍：地圖編輯
• 類別：世界近代三大數學難題之一

四色問題簡介

四色問題又稱四色猜想、四色定理，是世界近代三大數學難題之一。地圖四色定理（Four color theorem）最先是由一位叫古德里（Francis Guthrie）的英國大學生提出來的。

四色問題的內容是“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。”也就是說在不引起混淆的情況下一張地圖只需四種顏色來標記就行。

用數學語言表示即“將平面任意地細分為不相重疊的區域，每一個區域總可以用1234這四個數字之一來標記而不會使相鄰的兩個區域得到相同的數字。”這裡所指的相鄰區域是指有一整段邊界是公共的。如果兩個區域只相遇於一點或有限多點就不叫相鄰的。因為用相同的顏色給它們著色不會引起混淆。

發展簡史

問題的提出

1852年，畢業於倫敦大學的格斯里（Francis Guthrie）來到一家科研單位搞地圖著色工作時，發現每幅地圖都可以只用四種顏色著色。這個現象能不能從數學上加以嚴格證明呢？他和他正在讀大學的弟弟決心試一試，但是稿紙已經堆了一大疊，研究工作卻是沒有任何進展。

1852年10月23日，他的弟弟就這個問題的證明請教了他的老師、著名數學家德·摩爾根，摩爾根也沒有能找到解決這個問題的途徑，於是寫信向自己的好友、著名數學家哈密頓爵士請教，但直到1865年哈密頓逝世為止，問題也沒有能夠解決。

1872年，英國當時最著名的數學家凱利正式向倫敦數學學會提出了這個問題，於是四色猜想成了世界數學界關注的問題，世界上許多一流的數學家都紛紛參加了四色猜想的大會戰。

從此，這個問題在一些人中間傳來傳去，當時，三等分角和化圓為方問題已在社會上“臭名昭著”，而“四色瘟疫”又悄悄地傳播開來了。

肯普的研究

1878～1880年兩年間，著名的律師兼數學家肯普(Alfred Kempe)和泰勒(Peter Guthrie Tait)兩人分別提交了證明四色猜想的論文，宣布證明了四色定理。

大家都認為四色猜想從此也就解決了，但其實肯普並沒有證明四色問題。11年後，即1890年，在牛津大學就讀的年僅29歲的赫伍德以自己的精確計算指出了肯普在證明上的漏洞。他指出肯普說沒有極小五色地圖能有一國具有五個鄰國的理由有破綻。不久泰勒的證明也被人們否定了。人們發現他們實際上證明了一個較弱的命題——五色定理。就是說對地圖著色，用五種顏色就夠了。

這是不正規的四色地圖，實為五色

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

肯普的貢獻

肯普是用歸謬法來證明的，大意是如果有一張正規的五色地圖，就會存在一張國數最少的“極小正規五色地圖”，如果極小正規五色地圖中有一個國家的鄰國數少於六個，就會存在一張國數較少的正規地圖仍為五色的，這樣一來就不會有極小五色地圖的國數，也就不存在正規五色地圖了。這樣肯普就認為他已經證明了“四色問題”，但是後來人們發現他錯了。

不過肯普的證明闡明了兩個重要的概念，對以後問題的解決提供了途徑。第一個概念是“構形”。他證明了在每一張正規地圖中至少有一國具有兩個、三個、四個或五個鄰國，不存在每個國家都有六個或更多個鄰國的正規地圖，也就是說，由兩個鄰國，三個鄰國、四個或五個鄰國組成的一組“構形”是不可避免的，每張地圖至少含有這四種構形中的一個。

肯普提出的另一個概念是“可約”性。“可約”這個詞的使用是來自肯普的論證。他證明了只要五色地圖中有一國具有四個鄰國，就會有國數減少的五色地圖。自從引入“構形”，“可約”概念後，逐步發展了檢查構形以決定是否可約的一些標準方法，能夠尋求可約構形的不可避免組，是證明“四色問題”的重要依據。但要證明大的構形可約，需要檢查大量的細節，這是相當複雜的。

緩慢的進展

人們發現四色問題出人意料地異常困難，曾經有許多人發表四色問題的證明或反例，但都被證實是錯誤的。後來，越來越多的數學家雖然對此絞盡腦汁，但一無所獲。於是，人們開始認識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。　進入20世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在進行。

四色定理的本質就是在平面或者球面無法構造有五個或者五個以上的兩兩相連的區域，如果有五個以上兩兩相連區域，第五個區域至少與一個區域同一種顏色。這個理論在其他構造中是顯然的，例如在環面上（虧格為1），需要7色，就是因為環面不能構造8個兩兩相連區域。在虧格為2的雙環面上，需要8色，就是不能構造9個區域兩兩相連。

1913年，美國著名數學家、哈佛大學的伯克霍夫利用肯普的想法，結合自己新的構想；證明了某些大的構形可約。後來美國數學家富蘭克林於1939年證明了22國以下的地圖都可以用四色著色。1950年，溫恩從22國推進到35國。1960年，有人又證明了39國以下的地圖可以只用四種顏色著色；隨後又推進到了50國。看來這種推進仍然十分緩慢。

計算機證明

高速數字計算機的發明，促使更多數學家對“四色問題”的研究。電子計算機問世以後，由於演算速度迅速提高，加之人機對話的出現，大大加快了對四色猜想證明的進程。就在1976年6月，在美國伊利諾斯大學的兩台不同的電子計算機上，用了1200個小時，作了100億個判斷，結果沒有一張地圖是需要五色的，最終證明了四色定理，轟動了世界。

這是一百多年來吸引許多數學家與數學愛好者的大事，當兩位數學家將他們的研究成果發表的時候，當地的郵局在當天發出的所有郵件上都加蓋了“四色足夠”的特製郵戳，以慶祝這一難題獲得解決。

但證明並未止步，計算機證明無法給出令人信服的思考過程。問題影響

四色定理-非正規地圖

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

邏輯證明

理論基礎

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

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

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

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

二著色地圖

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

二著色結構特點是奇偶位置決定著色，任何兩個區域的任何聯繫鏈條只有相隔偶數個區域才滿足兩區域著色不同，我們定義這兩個區域為偶隔域。

三著色地圖

我們隨意取一張任意結構的二著色的地圖M，來構建一個具有n個滿足推論一條件區域的地圖Q，構建方式有且只有一個，就是在圖論圖形中我們如何去掉的這n個區域及其與鄰域的關係線，我們接怎么給它添加回去。我們任取這n個區域中一個區域q為例，只要我們在M地圖上將必須滿足二著色的幾個區域W直接聯繫到q上，這樣就滿足推論一中的條件而使Q必須為三著色。而W要滿足二著色則必定含有偶隔域，如果W有x個區域和q發生直接聯繫，則q上出去的關係線有x個，那么我們一定可以將該複雜的聯繫分解成x-1個不可分解關係環，其中至少有一個不可再分的關係環是M中的偶隔域與q聯繫的，（推論二）假設這個推論是錯誤的，所有不可再分的環全部是奇隔域，那么這些環拼接回去時滿足每個小環的間隔區域數相加再減去共用的區域，仍舊是奇隔域，這樣W便不滿足二著色，所以這些不可再分環中一定有偶隔域和q發生聯繫而構成奇數環（環連的區域為奇數），並且導致q必須使用第三色的就是這些不可再分的奇數環。由於滿足二著色的只有偶隔域一種條件，那么構造的三著色地圖中決定三著色的條件也只有一種，存在不可再分的奇數環。

四著色地圖

在上面構建的三色著色地圖Q基礎上我們再來構建四著色地圖P，假如P存在滿足推論一條件的區域有k個，同樣的方法，我們任取k中一個區域p，只要我們在Q地圖上將必須滿足三著色的幾個區域R直接聯繫到p上，這樣就滿足推論一中的條件而使P必須為四著色。而R要滿足三著色則必定含有奇數環並且組成奇數環的區域都能夠與p發生聯繫（保證奇數環沒有被包圍在其他閉合環內的部分），如果R有y個區域和p發生直接聯繫，則p上出去的關係線有y個，那么導致p為第四色原因是可發生聯繫的奇數環，既只要有一個這樣的奇數環存在就一定會導致p使用第四色（推論三），假設這一推論不成立那么沒有這樣的奇數環存在，則由前面二著色建立三著色正經得到，除了奇數環再沒有能使地圖為三著色的條件了，或者當奇數環區域不能全部與p發生聯繫，這樣p必然的不需要第四色了。故我們的推論三成立。由於三著色條件唯一而使得p四著色的條件唯一，我們來看四著色條件的特點，當p與R發生聯繫後，不管R有多少滿足條件的奇數環，勢必最終只能有包括p在內的三個區域能與外界區域發生聯繫。因為p和R上的任何兩個區域都可以構成一個封閉的三角形，而當我們選的R上這倆區域與p關係線是最外側的關係線時，則R上其他區域一定不能在三角形外，不然或造成以上兩根關係線不再是最外側或者有關係線出現交叉，所以R上剩餘區域必定在三角形內而造成四著色圖最多只有三個區域能與外界發生聯繫。

五著色地圖

那么我們在構建五著色地圖時，四著色結構最多提供三種不同著色，不能滿足推論一的條件，而決定將無法構建五著色地圖。

拓撲證明

四色定理證明的關鍵可以歸納為二維平面內兩條直線相交的問題。

1.將地圖上不同的區域用不同的點來表示。

2.點與點之間的連線用來表示地圖上兩區域之間的相鄰邏輯關係，所以,線與線之間不可交叉（即不可存在交叉而沒有公共交點的情況），否則就超越了二維平面，而這種平面暫時稱它為邏輯平面，它只反應區域之間的關係，並不反應實際位置。

通過以上的變換處理，可以將對無窮盡的實際位置的討論，變為有條理可歸納的邏輯關係的討論，從而提供了簡單書面證明的可行性。

如果證明可以用一句話來說，那就是：“二維平面不存在交叉直線，只存在共點直線。