四色問題四色

1、a) 任一不小于6之偶數(shù)，都可以表示成兩個奇質(zhì)數(shù)之和；b) 任一不小于9之奇數(shù)，都可以表示成三個奇質(zhì)數(shù)之和。 陳景潤證明了1+2成立，即任何一個大偶數(shù)都可表示成一個素數(shù)與另一個素因子不超過2個的數(shù)之和。 四四色色問問題題 數(shù)學(xué)語言：將平面任意地細分為不相重疊的區(qū)域，每一個數(shù)學(xué)語言：將平面任意地細分為不相重疊的區(qū)域，每一個區(qū)域總可以用區(qū)域總可以用1 1，2 2，3 3，4 4這四個數(shù)字之一來標記，而不會使這四個數(shù)字之一來標記，而不會使相鄰的兩個區(qū)域得到相同的數(shù)字。相鄰的兩個區(qū)域得到相同的數(shù)字。 （相鄰區(qū)域，是指有一整段邊界是公共的。如果兩個區(qū)域只相遇于一點或有限多點，就不叫相鄰的。） 四色猜想四

2、色猜想的提出的提出: : 英英國畢業(yè)國畢業(yè)于于倫倫敦大敦大學(xué)學(xué)的的弗南西斯弗南西斯 格思里格思里來來到一家科到一家科研單研單位位搞搞地地圖圖著著色工作色工作時時，發(fā)現(xiàn)發(fā)現(xiàn)了一了一種種有趣的有趣的現(xiàn)現(xiàn)象：象：“ “看看來來，每幅地，每幅地圖圖都可以用四都可以用四種顏種顏色色著色，使得有共同著色，使得有共同邊邊界的界的國國家都被著上不同的家都被著上不同的顏顏色。他和在大色。他和在大學(xué)讀書學(xué)讀書的的弟弟格里斯弟弟格里斯決決心心試試一一試試, ,可是可是研研究工作究工作沒沒有有進進展。展。 著名著名數(shù)學(xué)數(shù)學(xué)家家奧奧古斯都古斯都 德德 摩根摩根也也沒沒有能找到解有能找到解決這個問題決這個問題的途的途徑徑

3、，著，著名名數(shù)學(xué)數(shù)學(xué)家家威廉威廉 哈密哈密頓頓對對四色四色問題進問題進行行論證論證。但直到。但直到18651865年哈密年哈密頓頓逝世逝世為為止，止，問題問題也也沒沒有能有能夠夠解解決決。 18781880年兩年間，著名的律師兼數(shù)學(xué)家年兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒肯普和泰勒兩人分別提交兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認為四色猜想從了證明四色猜想的論文，宣布證明了四色定理，大家都認為四色猜想從此也就解決了。此也就解決了。 首先指出如果首先指出如果沒沒有一有一個國個國家包家包圍圍其他其他國國家，或家，或沒沒有三有三個個以上的以上的國國家相遇于一點，家相遇于一點，

4、這種這種地地圖圖就就說說是是“ “正正規(guī)規(guī)的的” ” 否否則為則為非正非正規(guī)規(guī)地地圖圖。 ，但非正，但非正規(guī)規(guī)地地圖圖所需所需顏顏色色種數(shù)種數(shù)一般一般不超不超過過正正規(guī)規(guī)地地圖圖所需的所需的顏顏色，如果有一色，如果有一張張需要五需要五種顏種顏色的地色的地圖圖，那就是指，那就是指它它的正的正規(guī)規(guī)地地圖圖是五色的，是五色的，要要證證明四色猜想成立，只要明四色猜想成立，只要證證明不存在一明不存在一張張正正規(guī)規(guī)五色地五色地圖圖就足就足夠夠了。了。 ：大意是如果有一：大意是如果有一張張正正規(guī)規(guī)的五色地的五色地圖圖，就，就會會存在一存在一張國數(shù)張國數(shù)最少的最少的“ “極極小正小正規(guī)規(guī)五色地五色地圖圖” ”

5、，如果，如果極極小正小正規(guī)規(guī)五色地五色地圖圖中有一中有一個國個國家的家的鄰國數(shù)鄰國數(shù)少于六少于六個個，就，就會會存在一存在一張國數(shù)較張國數(shù)較少的正少的正規(guī)規(guī)地地圖圖仍仍為為五色的，五色的，這樣這樣一一來來就不就不會會有有極極小五色地小五色地圖圖的的國國數(shù)數(shù)，也就不存在正，也就不存在正規(guī)規(guī)五色地五色地圖圖了。了。這樣這樣肯普就肯普就認為認為他已他已經(jīng)證經(jīng)證明了明了“ “四色四色問題問題” ”，但是，但是后后來來人人們發(fā)現(xiàn)們發(fā)現(xiàn)他他錯錯了。了。 18901890年，在牛津大年，在牛津大學(xué)學(xué)就就讀讀的年的年僅僅2929歲歲的的赫伍德赫伍德以自己的精確以自己的精確計計算算指出了指出了肯普在肯普在證證明

6、上的漏洞明上的漏洞。不久，泰勒的。不久，泰勒的證證明也被人明也被人們們否定了。否定了。 人人們發(fā)現(xiàn)們發(fā)現(xiàn)他他們實際們實際上上證證明了一明了一個較個較弱的命弱的命題題五色定理。就是五色定理。就是說對說對地地圖圖著色，用五著色，用五種顏種顏色就色就夠夠了。了。 后來，越來越多的數(shù)學(xué)家雖然對此絞盡腦汁，但一無所獲。后來，越來越多的數(shù)學(xué)家雖然對此絞盡腦汁，但一無所獲。于是，人們開始認識到，這個貌似容易的題目，其實是一個可于是，人們開始認識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。與費馬猜想相媲美的難題。 構(gòu)形構(gòu)形：他：他證證明了在每一明了在每一張張正正規(guī)規(guī)地地圖圖中至少有一中至少有一

7、國國具有具有兩兩個個、三、三個個、四、四個個或五或五個鄰國個鄰國，不存在每，不存在每個國個國家都有六家都有六個個或更多或更多個個鄰國鄰國的正的正規(guī)規(guī)地地圖圖，也就是，也就是說說，由，由兩個鄰國兩個鄰國，三，三個鄰國個鄰國、四、四個個或五或五個鄰國組個鄰國組成的一成的一組組“構(gòu)構(gòu)形形”是不可避免的，每是不可避免的，每張張地地圖圖至少含有至少含有這這四四種構(gòu)種構(gòu)形中的一形中的一個個。 “可約可約”性性: :“可可約約”這個詞這個詞的使用是的使用是來來自肯普的自肯普的論證論證。他他證證明了只要五色地明了只要五色地圖圖中有一中有一國國具有四具有四個鄰國個鄰國，就，就會會有有國數(shù)減國數(shù)減少少的五色地的五

8、色地圖圖。 自自從從引入引入“構(gòu)構(gòu)形形”，“可可約約”概概念后，逐步念后，逐步發(fā)發(fā)展了展了檢查構(gòu)檢查構(gòu)形以形以決決定是否可定是否可約約的一些的一些標標準方法，能準方法，能夠?qū)驅(qū)で罂汕罂杉s構(gòu)約構(gòu)形的不可避形的不可避免免組組，是，是證證明明“四色四色問題問題”的重要依據(jù)。但要的重要依據(jù)。但要證證明大的明大的構(gòu)構(gòu)形可形可約約，需要需要檢查檢查大量的大量的細節(jié)細節(jié)，這這是相是相當復(fù)雜當復(fù)雜的。的。 進入進入2020世紀以來，科學(xué)家們對四色猜想的證明基本世紀以來，科學(xué)家們對四色猜想的證明基本上是按照肯普的想法在進行：上是按照肯普的想法在進行：19131913年美年美國國伯克霍夫：肯普的想法伯克霍夫：肯

9、普的想法+ +新的新的設(shè)設(shè)想想證證明了某些大的明了某些大的構(gòu)構(gòu)形可形可約約19391939年美年美國數(shù)學(xué)國數(shù)學(xué)家富家富蘭蘭克林克林證證明了明了2222國國以下的地以下的地圖圖都可以用四色著色都可以用四色著色 19501950年年 ，有人，有人從從2222國國推推進進到到3535國國19601960年，有人又年，有人又證證明了明了3939國國以下的地以下的地圖圖可以只用四可以只用四種顏種顏色著色色著色隨隨后又推后又推進進到了到了5050國國這種推進仍然十分緩慢。這種推進仍然十分緩慢。 高速數(shù)字計算機的發(fā)明高速數(shù)字計算機的發(fā)明，促使更多促使更多數(shù)學(xué)數(shù)學(xué)家家對對“四色四色問問題題”的的研研究。究。從

10、從19361936年就年就開開始始研研究四色猜想的究四色猜想的海克?？?，公，公開開宣宣稱稱四色猜想可用四色猜想可用尋尋找可找可約圖約圖形的不可避免形的不可避免組來證組來證明明。：把每：把每個國個國家的首都家的首都標標出出來來，然后把相，然后把相鄰國鄰國家的首都家的首都用一用一條條越越過邊過邊界的界的鐵鐵路路連連接起接起來來，除首都，除首都( (稱為頂稱為頂點點) )及及鐵鐵路路( (稱為稱為弧或弧或邊邊) )外，擦掉其他所有的外，擦掉其他所有的線線，剩下的，剩下的稱為稱為原原圖圖的的對對偶偶圖圖。 到了六十年代后期，?？艘搅肆甏笃?，?？艘M進一一個類個類似于在似于在電網(wǎng)絡(luò)電網(wǎng)絡(luò)中移中移

11、動電動電荷的荷的方法方法來來求求構(gòu)構(gòu)形的不可避免形的不可避免組組。在?？说?。在?？说难醒芯恐械谝淮我跃恐械谝淮我灶H頗不成熟的形不成熟的形式出式出現(xiàn)現(xiàn)的的“ “放放電電法法” ”，這對這對以后以后關(guān)關(guān)于不可避免于不可避免組組的的研研究是究是個關(guān)鍵個關(guān)鍵，也是，也是證證明四色定理的中心要素。明四色定理的中心要素。 電電子子計計算機算機問問世以后，由于演算速度迅速提高，加之人機世以后，由于演算速度迅速提高，加之人機對話對話的的出出現(xiàn)現(xiàn)，大大加快了，大大加快了對對四色猜想四色猜想證證明的明的進進程。美程。美國國伊利伊利諾諾大大學(xué)學(xué)哈肯在哈肯在19701970年著手改年著手改進進“ “放放電過電過程程”

12、 ”，后，后與與阿佩爾合作阿佩爾合作編編制一制一個個很好的程序。很好的程序。 19761976年年6 6月，他們在美國伊利諾斯大學(xué)月，他們在美國伊利諾斯大學(xué)的兩臺不同的電子計算機上，用了的兩臺不同的電子計算機上，用了12001200個小時，作了個小時，作了100100億判斷，終于完成了億判斷，終于完成了四色定理的證明，轟動了世界。四色定理的證明，轟動了世界。幾何證明：幾何證明： 在平面地圖中，為了區(qū)分相鄰的圖形，相鄰圖形需要使用不同的顏色來上色，與這兩個相鄰圖形都有鄰邊的圖形需要使用第三種顏色 我們先假設(shè)四色定理成立，根據(jù)四色定理得出在一個平面內(nèi)最多有四個互有鄰邊的圖形，而因為第四個與三三個互

13、有鄰邊的圖形都會包圍一個圖形，所以一個平面內(nèi)互有鄰邊的圖形最多有四個，所以四色定理成立（互有鄰邊，舉例： 三個互有鄰邊的圖形A和B有鄰邊 C和AB都有鄰邊） 雖然任何平面地圖可以只用四個顏色著色，但是這個定理的應(yīng)用是有限的 現(xiàn)實中的地圖常會出現(xiàn)飛地，即兩個不連通的區(qū)域?qū)儆谕粋€國家的情況（例如美國的阿拉斯加州），而制作地圖時我們?nèi)詴筮@兩個區(qū)域被涂上同樣的顏色，在這種情況下，只用四種顏色將會造成諸多不便。 實際中用四種顏色著色的地圖是不多見的，而且這些地圖往往最少只需要三種顏色來染色。此外，即便地圖能夠只用四種顏色染色，為了區(qū)分起見，也會采用更多的顏色，以提示不同地區(qū)的差別。 在“四色問題”的研究過程中，不少新的數(shù)學(xué)理論隨之產(chǎn)生，也發(fā)展了很多數(shù)學(xué)計算技巧。如將地圖的著色問題