20115641039 張超 淺談“四色問題”

《20115641039 張超 淺談“四色問題”》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、淺談四色問題【摘要】在日常生活中,我們會發(fā)現(xiàn)一個有趣的現(xiàn)象，如果你仔細(xì)留心一張世界地圖，你會發(fā)現(xiàn)用一種顏色給一個國家著色，那么一共只需要四種顏色就能保證每兩個相鄰國家的顏色不同，這樣的著色效果能使每一個國家都能清楚地顯示出來，這就是由地圖著色問題引發(fā)的著名的數(shù)學(xué)問題：“四色問題”。但要證明這個結(jié)論卻是一個著名的世界難題，許許多多的中外數(shù)學(xué)家都被這個問題所折服，最終借助計算機(jī)才得以解決，但結(jié)論并不是很完美，因此諸多數(shù)學(xué)學(xué)者都在尋找其嚴(yán)格的數(shù)學(xué)證明方法?！娟P(guān)鍵詞】四色問題的背景四色問題的解決歷程四色問題的應(yīng)用四色問題又稱四色猜想、四色定理，與

2、哥德巴赫猜想、費馬大定理一起被稱作世界三大著名數(shù)學(xué)難題?！八纳珕栴}”是世界數(shù)學(xué)史上一個非常著名的證明難題，它要求證明在平面地圖上只用四種顏色就能使任何復(fù)雜形狀的各塊相鄰區(qū)域之間顏色不會重復(fù)，也就是說相互之間都有交界的區(qū)域最多只能有四塊。一百五十多年來有許多數(shù)學(xué)家用了很長時間，花了很多精力才艱難地證明了這個問題。下面我就來談一談著名的“四色問題”。一、四色問題的背景（一）四色問題的提出四色猜想的提出來自英國。1852年，畢業(yè)于倫敦大學(xué)的弗南西斯·格思里來到一家科研單位搞地圖著色工作時，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“每幅地圖都可以用四種顏色著色，使

3、得有共同邊界的國家都被著上不同的顏色?！边@個現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？他和在大學(xué)讀書的弟弟格里斯決心試一試，兄弟二人為證明這一問題而使用的稿紙已經(jīng)堆了一大疊，可是研究工作沒有進(jìn)展。1852年10月23日，他的弟弟就這個問題的證明請教了他的老師，著名數(shù)學(xué)家德·摩爾根，摩爾根也沒有能找到解決這個問題的途徑，于是寫信向自己的好友，著名數(shù)學(xué)家哈密頓爵士請教，哈密頓接到摩爾根的信后，對四色問題進(jìn)行論證，但直到1865年哈密頓逝世為止，問題也沒有能夠解決。1872年，英國當(dāng)時最著名的數(shù)學(xué)家凱利正式向倫敦數(shù)學(xué)學(xué)會提出了這個問題，于是四色猜想成了

4、世界數(shù)學(xué)界關(guān)注的問題。世界上許多一流的數(shù)學(xué)家都紛紛加入到證明四色猜想的隊伍中。（二）四色問題的內(nèi)容四色問題的主要內(nèi)容是：“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色?！庇脭?shù)學(xué)語言表示，即“將平面任意地細(xì)分為不相重迭的區(qū)域，每一個區(qū)域總可以用1，2，3，4這四個數(shù)字之一來標(biāo)記，而不會使相鄰的兩個區(qū)域得到相同數(shù)字”。這里所指的相鄰區(qū)域，是指有一整段邊界是公共的，如果兩個區(qū)域只相遇于一點或有限多點，就不叫相鄰，因為用相同的顏色給它們著色不會引起混淆。（如圖1）（圖1）（圖2）一、四色問題的解決歷程(一）人工證明1878～18

5、80年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了?？掀盏淖C明是這樣的：首先指出如果沒有一個國家包圍其他國家，或沒有三個以上的國家相遇于一點，這種地圖就說是“正規(guī)的”（如圖1），否則為非正規(guī)地圖（如圖2）。一張地圖往往是由正規(guī)地圖和非正規(guī)地圖聯(lián)系在一起，但非正規(guī)地圖所需顏色種數(shù)一般不超過正規(guī)地圖所需的顏色，如果有一張需要五種顏色的地圖，那就是指它的正規(guī)地圖是五色的，要證明四色猜想成立，只要證明不存在一張正規(guī)五色地圖就足夠了。因此，肯普采用了歸謬法來證明，大意是如

6、果有一張正規(guī)的五色地圖，就會存在一張國數(shù)最少的“極小正規(guī)五色地圖”，如果極小正規(guī)五色地圖中有一個國家的鄰國數(shù)少于六個，就會存在一張國數(shù)較少的正規(guī)地圖仍為五色的，這樣一來就不會有極小五色地圖的國數(shù)，也就不存在正規(guī)五色地圖了。這樣肯普就認(rèn)為他已經(jīng)證明了“四色問題”。但是，時隔十一年之后，即1890年，在牛津大學(xué)就讀的年僅29歲的數(shù)學(xué)家赫伍德以自己的精確計算，指出肯普的證明是錯誤的。不久，泰勒的證明也被否定了。（二）計算機(jī)證明高速數(shù)字計算機(jī)的發(fā)明，促使更多數(shù)學(xué)家對“四色問題”的研究。從1936年就開始研究四色猜想的?？?，公開宣稱四色猜想可用尋找

7、可約圖形的不可避免組來證明。他的學(xué)生丟雷寫了一個計算程序，海克不僅能用這程序產(chǎn)生的數(shù)據(jù)來證明構(gòu)形可約，而且描繪可約構(gòu)形的方法是從改造地圖成為數(shù)學(xué)上稱為“對偶”形著手。他把每個國家的首都標(biāo)出來，然后把相鄰國家的首都用一條越過邊界的鐵路連接起來，除首都(稱為頂點)及鐵路(稱為弧或邊)外，擦掉其他所有的線，剩下的稱為原圖的對偶圖。到了六十年代后期，海克引進(jìn)一個類似于在電網(wǎng)絡(luò)中移動電荷的方法來求構(gòu)形的不可避免組。在?？说难芯恐械谝淮我灶H不成熟的形式出現(xiàn)的“放電法”，這對以后關(guān)于不可避免組的研究是個關(guān)鍵，也是證明四色定理的中心要素。電子計算機(jī)問世以

8、后，由于演算速度迅速提高，加之人機(jī)對話的出現(xiàn)，大大加快了對四色猜想證明的進(jìn)程。美國伊利諾大學(xué)哈肯在1970年著手改進(jìn)“放電過程”，后與阿佩爾合作編制一個很好的程序。就在1976年6月，他們在美