四色定理

四色問題又稱四色猜想，是世界近代三大數學難題之一。
四色問題的內容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。”用數學語言表示，即“將平面任意地細分為不相重迭的區域，每一個區域總可以用1，2，3，4這四個數字之一來標記，而不會使相鄰的兩個區域得到相同的數字。”（右圖）
這裡所指的相鄰區域，是指有一整段邊界是公共的。如果兩個區域只相遇於一點或有限多點，就不叫相鄰的。因為用相同的顏色給它們著色不會引起混淆。
四色猜想的提出來自英國。 1852年，畢業於倫敦大學的弗南西斯·格思裡來到一家科研單位搞地圖著色工作時，發現了一種有趣的現象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色。”這個現象能不能從數學上加以嚴格證明呢？ 他和在大學讀書的弟弟格裡斯決心試一試。 兄弟二人為證明這一問題而使用的稿紙已經堆了一大疊，可是研究工作沒有進展。
1852年10月23日，他的弟弟就這個問題的證明請教了他的老師、著名數學家德·摩爾根，摩爾根也沒有能找到解決這個問題的途徑，於是寫信向自己的好友、著名數學家漢密爾頓爵士請教。 漢密爾頓接到摩爾根的信後，對四色問題進行論證。但直到1865年漢密爾頓逝世為止，問題也沒有能夠解決。
1872年，英國當時最著名的數學家凱利正式向倫敦數學學會提出了這個問題，於是四色猜想成了世界數學界關注的問題。世界上許多一流的數學家都紛紛參加了四色猜想的大會戰。 1878～1880年兩年間，著名的律師兼數學家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣佈證明了四色定理，大家都認為四色猜想從此也就解決了。
肯普的證明是這樣的：首先指出如果沒有一個國家包圍其他國家，或沒有三個以上的國家相遇於一點，這種地圖就說是“正規的”（左圖）。家相遇於一點，這種地圖就說是“正規的”（左圖）。 如為正規地圖，否則為非正規地圖（右圖）。一張地圖往往是由正規地圖和非正規地圖聯繫在一起，但非正規地圖所需顏色種數一般不超過正規地圖所需的顏色，如果有一張需要五種顏色的地圖，那就是指它的正規地圖是五色的，要證明四色猜想成立，只要證明不存在一張正規五色地圖就足夠了。

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

不過肯普的證明闡明了兩個重要的概念，對以後問題的解決提供了途徑。第一個概念是“構形”。 他證明了在每一張正規地圖中至少有一國具有兩個、三個、四個或五個鄰國，不存在每個國家都有六個或更多個鄰國的正規地圖，也就是說，由兩個鄰國，三個鄰國、四個或五個鄰國組成的一組“構形”是不可避免的，每張地圖至少含有這四種構形中的一個。
肯普提出的另一個概念是“可約”性。"可約"這個詞的使用是來自肯普的論證。 他證明瞭只要五色地圖中有一國具有四個鄰國，就會有國數減少的五色地圖。 自從引入“構形”，“可約”概念後，逐步發展了檢查構形以決定是否可約的一些標準方法，能夠尋求可約構形的不可避免組，是證明“四色問題”的重要依據。但要證明大的構形可約，需要檢查大量的細節，這是相當複雜的。
11年後，即1890年，在牛津大學就讀的年僅29歲的赫伍德以自己的精確計算指出了肯普在證明上的漏洞。 他指出肯普說沒有極小五色地圖能有一國具有五個鄰國的理由有破綻。 不久，泰勒的證明也被人們否定了。 人們發現他們實際上證明瞭一個較弱的命題——五色定理。 就是說對地圖著色，用五種顏色就夠了。後來，越來越多的數學家雖然對此絞盡腦汁，但一無所獲。 於是，人們開始認識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。
進入20世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在進行。 1913年，美國著名數學家、哈佛大學的伯克霍夫利用肯普的想法，結合自己新的設想；證明瞭某些大的構形可約。 後來美國數學家富蘭克林於1939年證明瞭22國以下的地圖都可以用四色著色。1950年，有人從22國推進到35國。 1960年，有人又證明瞭39國以下的地圖可以只用四種顏色著色；隨後又推進到了50國。 看來這種推進仍然十分緩慢。
高速數字計算機的發明，促使更多數學家對“四色問題”的研究。 從1936年就開始研究四色猜想的海克，公開宣稱四色猜想可用尋找可約圖形的不可避免組來證明。 他的學生丟雷寫了一個計算程式，海克不僅能用這程式產生的數據來證明構形可約，而且描繪可約構形的方法是從改造地圖成為數學上稱為“對偶”形著手。

他把每個國家的首都標出來，然後把相鄰國家的首都用一條越過邊界的鐵路連接起來，除首都(稱為頂點)及鐵路(稱為弧或邊)外，擦掉其他所有的線，剩下的稱為原圖的對偶圖。 到了六十年代後期，海克引進一個類似於在電網絡中移動電荷的方法來求構形的不可避免組。 在海克的研究中第一次以頗不成熟的形式出現的“放電法”，這對以後關於不可避免組的研究是個關鍵，也是證明四色定理的中心要素。
電子電腦問世以後，由於演算速度迅速提高，加之人機對話的出現，大大加快了對四色猜想證明的進程。美國伊利諾大學哈肯在1970年著手改進“放電過程”，後與阿佩爾合作編制一個很好的程式。 就在1976年6月，他們在美國伊利諾斯大學的兩台不同的電子計算機上，用了1200個小時，作了100億判斷，終於完成了四色定理的證明，轟動了世界。
這是一百多年來吸引許多數學家與數學愛好者的大事，當兩位數學家將他們的研究成果發表的時候，當地的郵局在當天發出的所有郵件上都加蓋了“四色足夠”的特製郵戳，以慶祝這一難題獲得解決。
“四色問題”的被證明僅解決了一個歷時100多年的難題，而且成為數學史上一系列新思維的起點。 在“四色問題”的研究過程中，不少新的數學理論隨之產生，也發展了很多數學計算技巧。如將地圖的著色問題化為圖論問題，豐富了圖論的內容。 不僅如此，“四色問題”在有效地設計航空班機日程表，設計電腦的編碼程式上都起到了推動作用。
不過不少數學家並不滿足于電腦取得的成就，他們認為應該有一種簡捷明快的書面證明方法。直到現在，仍由不少數學家和數學愛好者在尋找更簡潔的證明方法。