20115641039 張超 淺談“四色問題”

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

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

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

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

4、伍中。（二）四色問題的內(nèi)容四色問題的主要內(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ì)引起混淆。（如圖1）（圖1）（圖2）一、四色問題的解決歷程(一）人工證明1878～1880年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，

5、大家都認(rèn)為四色猜想從此也就解決了。肯普的證明是這樣的：首先指出如果沒有一個(gè)國家包圍其他國家，或沒有三個(gè)以上的國家相遇于一點(diǎn)，這種地圖就說是“正規(guī)的”（如圖1），否則為非正規(guī)地圖（如圖2）。一張地圖往往是由正規(guī)地圖和非正規(guī)地圖聯(lián)系在一起，但非正規(guī)地圖所需顏色種數(shù)一般不超過正規(guī)地圖所需的顏色，如果有一張需要五種顏色的地圖，那就是指它的正規(guī)地圖是五色的，要證明四色猜想成立，只要證明不存在一張正規(guī)五色地圖就足夠了。因此，肯普采用了歸謬法來證明，大意是如果有一張正規(guī)的五色地圖，就會(huì)存在一張國數(shù)最少的“極小正規(guī)五色地圖”，如果極小正規(guī)五色地圖中有一個(gè)國家的鄰國數(shù)少于六個(gè)，就

6、會(huì)存在一張國數(shù)較少的正規(guī)地圖仍為五色的，這樣一來就不會(huì)有極小五色地圖的國數(shù)，也就不存在正規(guī)五色地圖了。這樣肯普就認(rèn)為他已經(jīng)證明了“四色問題”。但是，時(shí)隔十一年之后，即1890年，在牛津大學(xué)就讀的年僅29歲的數(shù)學(xué)家赫伍德以自己的精確計(jì)算，指出肯普的證明是錯(cuò)誤的。不久，泰勒的證明也被否定了。（二）計(jì)算機(jī)證明高速數(shù)字計(jì)算機(jī)的發(fā)明，促使更多數(shù)學(xué)家對(duì)“四色問題”的研究。從1936年就開始研究四色猜想的?？?，公開宣稱四色猜想可用尋找可約圖形的不可避免組來證明。他的學(xué)生丟雷寫了一個(gè)計(jì)算程序，?？瞬粌H能用這程序產(chǎn)生的數(shù)據(jù)來證明構(gòu)形可約，而且描繪可約構(gòu)形的方法是從改造地圖成為數(shù)學(xué)

7、上稱為“對(duì)偶”形著手。他把每個(gè)國家的首都標(biāo)出來，然后把相鄰國家的首都用一條越過邊界的鐵路連接起來，除首都(稱為頂點(diǎn))及鐵路(稱為弧或邊)外，擦掉其他所有的線，剩下的稱為原圖的對(duì)偶圖。到了六十年代后期，?？艘M(jìn)一個(gè)類似于在電網(wǎng)絡(luò)中移動(dòng)電荷的方法來求構(gòu)形的不可避免組。在海克的研究中第一次以頗不成熟的形式出現(xiàn)的“放電法”，這對(duì)以后關(guān)于不可避免組的研究是個(gè)關(guān)鍵，也是證明四色定理的中心要素。電子計(jì)算機(jī)問世以后，由于演算速度迅速提高，加之人機(jī)對(duì)話的出現(xiàn)，大大加快了對(duì)四色猜想證明的進(jìn)程。美國伊利諾大學(xué)哈肯在1970年著手改進(jìn)“放電過程”，后與阿佩爾合作編制一個(gè)很好的程序。就在

8、1976年6月，他們?cè)诿?/p>