四色問(wèn)題

四色問(wèn)題又稱(chēng)四色猜想，是世界近代三大數(shù)學(xué)難題之一。

　　四色問(wèn)題的內(nèi)容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國(guó)家著上不同的顏色。”用數(shù)學(xué)語(yǔ)言表示，即“將平面任意地細(xì)分為不相重迭的區(qū)域，每一個(gè)區(qū)域總可以用1，2，3，4這四個(gè)數(shù)字之一來(lái)標(biāo)記，而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字。”（右圖）

　　這里所指的相鄰區(qū)域，是指有一整段邊界是公共的。如果兩個(gè)區(qū)域只相遇于一點(diǎn)或有限多點(diǎn)，就不叫相鄰的。因?yàn)橛孟嗤�的顏色給它們著色不會(huì)引起混淆。

　　四色猜想的提出來(lái)自英國(guó)。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯·格思里來(lái)到一家科研單位搞地圖著色工作時(shí)，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來(lái)，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家都被著上不同的顏色。”這個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？他和在大學(xué)讀書(shū)的弟弟格里斯決心試一試。兄弟二人為證明這一問(wèn)題而使用的稿紙已經(jīng)堆了一大疊，可是研究工作沒(méi)有進(jìn)展。

　　1852年10月23日，他的弟弟就這個(gè)問(wèn)題的證明請(qǐng)教了他的老師、著名數(shù)學(xué)家德·摩爾根，摩爾根也沒(méi)有能找到解決這個(gè)問(wèn)題的途徑，于是寫(xiě)信向自己的好友、著名數(shù)學(xué)家漢密爾頓爵士請(qǐng)教。漢密爾頓接到摩爾根的信后，對(duì)四色問(wèn)題進(jìn)行論證。但直到1865年漢密爾頓逝世為止，問(wèn)題也沒(méi)有能夠解決。

　　1872年，英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問(wèn)題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問(wèn)題。世界上許多一流的數(shù)學(xué)家都紛紛參加了四色猜想的大會(huì)戰(zhàn)。1878～1880年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了。

　　肯普的證明是這樣的：首先指出如果沒(méi)有一個(gè)國(guó)家包圍其他國(guó)家，或沒(méi)有三個(gè)以上的國(guó)家相遇于一點(diǎn)，這種地圖就說(shuō)是“正規(guī)的”（左圖）。如為正規(guī)地圖，否則為非正規(guī)地圖（右圖）。一張地圖往往是由正規(guī)地圖和非正規(guī)地圖聯(lián)系在一起，但非正規(guī)地圖所需顏色種數(shù)一般不超過(guò)正規(guī)地圖所需的顏色，如果有一張需要五種顏色的地圖，那就是指它的正規(guī)地圖是五色的，要證明四色猜想成立，只要證明不存在一張正規(guī)五色地圖就足夠了。

　　肯普是用歸謬法來(lái)證明的，大意是如果有一張正規(guī)的五色地圖，就會(huì)存在一張國(guó)數(shù)最少的“極小正規(guī)五色地圖”，如果極小正規(guī)五色地圖中有一個(gè)國(guó)家的鄰國(guó)數(shù)少于六個(gè)，就會(huì)存在一張國(guó)數(shù)較少的正規(guī)地圖仍為五色的，這樣一來(lái)就不會(huì)有極小五色地圖的國(guó)數(shù)，也就不存在正規(guī)五色地圖了。這樣肯普就認(rèn)為他已經(jīng)證明了“四色問(wèn)題”，但是后來(lái)人們發(fā)現(xiàn)他錯(cuò)了。

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

　　肯普提出的另一個(gè)概念是“可約”性。“可約”這個(gè)詞的使用是來(lái)自肯普的論證。他證明了只要五色地圖中有一國(guó)具有四個(gè)鄰國(guó)，就會(huì)有國(guó)數(shù)減少的五色地圖。自從引入“構(gòu)形”，“可約”概念后，逐步發(fā)展了檢查構(gòu)形以決定是否可約的一些標(biāo)準(zhǔn)方法，能夠?qū)で罂杉s構(gòu)形的不可避免組，是證明“四色問(wèn)題”的重要依據(jù)。但要證明大的構(gòu)形可約，需要檢查大量的細(xì)節(jié)，這是相當(dāng)復(fù)雜的。

　　11年后，即1890年，在牛津大學(xué)就讀的年僅29歲的赫伍德以自己的精確計(jì)算指出了肯普在證明上的漏洞。他指出肯普說(shuō)沒(méi)有極小五色地圖能有一國(guó)具有五個(gè)鄰國(guó)的理由有破綻。不久，泰勒的證明也被人們否定了。人們發(fā)現(xiàn)他們實(shí)際上證明了一個(gè)較弱的命題——五色定理。就是說(shuō)對(duì)地圖著色，用五種顏色就夠了。后來(lái)，越來(lái)越多的數(shù)學(xué)家雖然對(duì)此絞盡腦汁，但一無(wú)所獲。于是，人們開(kāi)始認(rèn)識(shí)到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題。

　　進(jìn)入20世紀(jì)以來(lái)，科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在進(jìn)行。1913年，美國(guó)著名數(shù)學(xué)家、哈佛大學(xué)的伯克霍夫利用肯普的想法，結(jié)合自己新的設(shè)想；證明了某些大的構(gòu)形可約。后來(lái)美國(guó)數(shù)學(xué)家富蘭克林于1939年證明了22國(guó)以下的地圖都可以用四色著色。1950年，有人從22國(guó)推進(jìn)到35國(guó)。1960年，有人又證明了39國(guó)以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到了50國(guó)。看來(lái)這種推進(jìn)仍然十分緩慢。

　　高速數(shù)字計(jì)算機(jī)的發(fā)明，促使更多數(shù)學(xué)家對(duì)“四色問(wèn)題”的研究。從1936年就開(kāi)始研究四色猜想的海克，公開(kāi)宣稱(chēng)四色猜想可用尋找可約圖形的不可避免組來(lái)證明。他的學(xué)生丟雷寫(xiě)了一個(gè)計(jì)算程序，海克不僅能用這程序產(chǎn)生的數(shù)據(jù)來(lái)證明構(gòu)形可約，而且描繪可約構(gòu)形的方法是從改造地圖成為數(shù)學(xué)上稱(chēng)為“對(duì)偶”形著手。

　　他把每個(gè)國(guó)家的首都標(biāo)出來(lái)，然后把相鄰國(guó)家的首都用一條越過(guò)邊界的鐵路連接起來(lái)，除首都(稱(chēng)為頂點(diǎn))及鐵路(稱(chēng)為弧或邊)外，擦掉其他所有的線(xiàn)，剩下的稱(chēng)為原圖的對(duì)偶圖。到了六十年代后期，海克引進(jìn)一個(gè)類(lèi)似于在電網(wǎng)絡(luò)中移動(dòng)電荷的方法來(lái)求構(gòu)形的不可避免組。在海克的研究中第一次以頗不成熟的形式出現(xiàn)的“放電法”，這對(duì)以后關(guān)于不可避免組的研究是個(gè)關(guān)鍵，也是證明四色定理的中心要素。

　　電子計(jì)算機(jī)問(wèn)世以后，由于演算速度迅速提高，加之人機(jī)對(duì)話(huà)的出現(xiàn)，大大加快了對(duì)四色猜想證明的進(jìn)程。美國(guó)伊利諾大學(xué)哈肯在1970年著手改進(jìn)“放電過(guò)程”，后與阿佩爾合作編制一個(gè)很好的程序。就在1976年6月，他們?cè)诿绹?guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明，轟動(dòng)了世界。

　　這是一百多年來(lái)吸引許多數(shù)學(xué)家與數(shù)學(xué)愛(ài)好者的大事，當(dāng)兩位數(shù)學(xué)家將他們的研究成果發(fā)表的時(shí)候，當(dāng)?shù)氐泥]局在當(dāng)天發(fā)出的所有郵件上都加蓋了“四色足夠”的特制郵戳，以慶祝這一難題獲得解決。

　　“四色問(wèn)題”的被證明僅解決了一個(gè)歷時(shí)100多年的難題，而且成為數(shù)學(xué)史上一系列新思維的起點(diǎn)。在“四色問(wèn)題”的研究過(guò)程中，不少新的數(shù)學(xué)理論隨之產(chǎn)生，也發(fā)展了很多數(shù)學(xué)計(jì)算技巧。如將地圖的著色問(wèn)題化為圖論問(wèn)題，豐富了圖論的內(nèi)容。不僅如此，“四色問(wèn)題”在有效地設(shè)計(jì)航空班機(jī)日程表，設(shè)計(jì)計(jì)算機(jī)的編碼程序上都起到了推動(dòng)作用。

　　不過(guò)不少數(shù)學(xué)家并不滿(mǎn)足于計(jì)算機(jī)取得的成就，他們認(rèn)為應(yīng)該有一種簡(jiǎn)捷明快的書(shū)面證明方法。直到現(xiàn)在，仍由不少數(shù)學(xué)家和數(shù)學(xué)愛(ài)好者在尋找更簡(jiǎn)潔的證明方法。