四色問題又稱四色猜想,是世界近代三大數(shù)學(xué)難題之一.
四色問題的內(nèi)容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色.”用數(shù)學(xué)語言表示,即“將平面任意地細(xì)分為不相重迭的區(qū)域,每一個(gè)區(qū)域總可以用1,2,3,4這四個(gè)數(shù)字之一來標(biāo)記,而不會(huì)使相鄰的兩個(gè)區(qū)域得到相同的數(shù)字.”（右圖）
這里所指的相鄰區(qū)域,是指有一整段邊界是公共的.如果兩個(gè)區(qū)域只相遇于一點(diǎn)或有限多點(diǎn),就不叫相鄰的.因?yàn)橛孟嗤念伾o它們著色不會(huì)引起混淆.
四色猜想的提出來自英國.1852年,畢業(yè)于倫敦大學(xué)的弗南西斯·格思里來到一家科研單位搞地圖著色工作時(shí),發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來,每幅地圖都可以用四種顏色著色,使得有共同邊界的國家都被著上不同的顏色.”這個(gè)現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢?他和在大學(xué)讀書的弟弟格里斯決心試一試.兄弟二人為證明這一問題而使用的稿紙已經(jīng)堆了一大疊,可是研究工作沒有進(jìn)展.
1852年10月23日,他的弟弟就這個(gè)問題的證明請教了他的老師、著名數(shù)學(xué)家德·摩爾根,摩爾根也沒有能找到解決這個(gè)問題的途徑,于是寫信向自己的好友、著名數(shù)學(xué)家漢密爾頓爵士請教.漢密爾頓接到摩爾根的信后,對(duì)四色問題進(jìn)行論證.但直到1865年漢密爾頓逝世為止,問題也沒有能夠解決.
1872年,英國當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問題,于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題.世界上許多一流的數(shù)學(xué)家都紛紛參加了四色猜想的大會(huì)戰(zhàn).1878～1880年兩年間,著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文,宣布證明了四色定理,大家都認(rèn)為四色猜想從此也就解決了.
肯普的證明是這樣的：首先指出如果沒有一個(gè)國家包圍其他國家,或沒有三個(gè)以上的國家相遇于一點(diǎn),這種地圖就說是“正規(guī)的”（左圖）.如為正規(guī)地圖,否則為非正規(guī)地圖（右圖）.一張地圖往往是由正規(guī)地圖和非正規(guī)地圖聯(lián)系在一起,但非正規(guī)地圖所需顏色種數(shù)一般不超過正規(guī)地圖所需的顏色,如果有一張需要五種顏色的地圖,那就是指它的正規(guī)地圖是五色的,要證明四色猜想成立,只要證明不存在一張正規(guī)五色地圖就足夠了.
肯普是用歸謬法來證明的,大意是如果有一張正規(guī)的五色地圖,就會(huì)存在一張國數(shù)最少的“極小正規(guī)五色地圖”,如果極小正規(guī)五色地圖中有一個(gè)國家的鄰國數(shù)少于六個(gè),就會(huì)存在一張國數(shù)較少的正規(guī)地圖仍為五色的,這樣一來就不會(huì)有極小五色地圖的國數(shù),也就不存在正規(guī)五色地圖了.這樣肯普就認(rèn)為他已經(jīng)證明了“四色問題”,但是后來人們發(fā)現(xiàn)他錯(cuò)了.
不過肯普的證明闡明了兩個(gè)重要的概念,對(duì)以后問題的解決提供了途徑.第一個(gè)概念是“構(gòu)形”.他證明了在每一張正規(guī)地圖中至少有一國具有兩個(gè)、三個(gè)、四個(gè)或五個(gè)鄰國,不存在每個(gè)國家都有六個(gè)或更多個(gè)鄰國的正規(guī)地圖,也就是說,由兩個(gè)鄰國,三個(gè)鄰國、四個(gè)或五個(gè)鄰國組成的一組“構(gòu)形”是不可避免的,每張地圖至少含有這四種構(gòu)形中的一個(gè).
肯普提出的另一個(gè)概念是“可約”性.“可約”這個(gè)詞的使用是來自肯普的論證.他證明了只要五色地圖中有一國具有四個(gè)鄰國,就會(huì)有國數(shù)減少的五色地圖.自從引入“構(gòu)形”,“可約”概念后,逐步發(fā)展了檢查構(gòu)形以決定是否可約的一些標(biāo)準(zhǔn)方法,能夠?qū)で罂杉s構(gòu)形的不可避免組,是證明“四色問題”的重要依據(jù).但要證明大的構(gòu)形可約,需要檢查大量的細(xì)節(jié),這是相當(dāng)復(fù)雜的.
11年后,即1890年,在牛津大學(xué)就讀的年僅29歲的赫伍德以自己的精確計(jì)算指出了肯普在證明上的漏洞.他指出肯普說沒有極小五色地圖能有一國具有五個(gè)鄰國的理由有破綻.不久,泰勒的證明也被人們否定了.人們發(fā)現(xiàn)他們實(shí)際上證明了一個(gè)較弱的命題——五色定理.就是說對(duì)地圖著色,用五種顏色就夠了.后來,越來越多的數(shù)學(xué)家雖然對(duì)此絞盡腦汁,但一無所獲.于是,人們開始認(rèn)識(shí)到,這個(gè)貌似容易的題目,其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題.
進(jìn)入20世紀(jì)以來,科學(xué)家們對(duì)四色猜想的證明基本上是按照肯普的想法在進(jìn)行.1913年,美國著名數(shù)學(xué)家、哈佛大學(xué)的伯克霍夫利用肯普的想法,結(jié)合自己新的設(shè)想；證明了某些大的構(gòu)形可約.后來美國數(shù)學(xué)家富蘭克林于1939年證明了22國以下的地圖都可以用四色著色.1950年,有人從22國推進(jìn)到35國.1960年,有人又證明了39國以下的地圖可以只用四種顏色著色；隨后又推進(jìn)到了50國.看來這種推進(jìn)仍然十分緩慢.
高速數(shù)字計(jì)算機(jī)的發(fā)明,促使更多數(shù)學(xué)家對(duì)“四色問題”的研究.從1936年就開始研究四色猜想的?？?公開宣稱四色猜想可用尋找可約圖形的不可避免組來證明.他的學(xué)生丟雷寫了一個(gè)計(jì)算程序,海克不僅能用這程序產(chǎn)生的數(shù)據(jù)來證明構(gòu)形可約,而且描繪可約構(gòu)形的方法是從改造地圖成為數(shù)學(xué)上稱為“對(duì)偶”形著手.
他把每個(gè)國家的首都標(biāo)出來,然后把相鄰國家的首都用一條越過邊界的鐵路連接起來,除首都(稱為頂點(diǎn))及鐵路(稱為弧或邊)外,擦掉其他所有的線,剩下的稱為原圖的對(duì)偶圖.到了六十年代后期,?？艘M(jìn)一個(gè)類似于在電網(wǎng)絡(luò)中移動(dòng)電荷的方法來求構(gòu)形的不可避免組.在?？说难芯恐械谝淮我灶H不成熟的形式出現(xiàn)的“放電法”,這對(duì)以后關(guān)于不可避免組的研究是個(gè)關(guān)鍵,也是證明四色定理的中心要素.
電子計(jì)算機(jī)問世以后,由于演算速度迅速提高,加之人機(jī)對(duì)話的出現(xiàn),大大加快了對(duì)四色猜想證明的進(jìn)程.美國伊利諾大學(xué)哈肯在1970年著手改進(jìn)“放電過程”,后與阿佩爾合作編制一個(gè)很好的程序.就在1976年6月,他們在美國伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上,用了1200個(gè)小時(shí),作了100億判斷,終于完成了四色定理的證明,轟動(dòng)了世界.
這是一百多年來吸引許多數(shù)學(xué)家與數(shù)學(xué)愛好者的大事,當(dāng)兩位數(shù)學(xué)家將他們的研究成果發(fā)表的時(shí)候,當(dāng)?shù)氐泥]局在當(dāng)天發(fā)出的所有郵件上都加蓋了“四色足夠”的特制郵戳,以慶祝這一難題獲得解決.
“四色問題”的被證明僅解決了一個(gè)歷時(shí)100多年的難題,而且成為數(shù)學(xué)史上一系列新思維的起點(diǎn).在“四色問題”的研究過程中,不少新的數(shù)學(xué)理論隨之產(chǎn)生,也發(fā)展了很多數(shù)學(xué)計(jì)算技巧.如將地圖的著色問題化為圖論問題,豐富了圖論的內(nèi)容.不僅如此,“四色問題”在有效地設(shè)計(jì)航空班機(jī)日程表,設(shè)計(jì)計(jì)算機(jī)的編碼程序上都起到了推動(dòng)作用.
不過不少數(shù)學(xué)家并不滿足于計(jì)算機(jī)取得的成就,他們認(rèn)為應(yīng)該有一種簡捷明快的書面證明方法.直到現(xiàn)在,仍由不少數(shù)學(xué)家和數(shù)學(xué)愛好者在尋找更簡潔的證明方法.