地圖四色問題

《地圖四色問題》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。

1、地圖四色問題地圖四色問題地圖四色問題《人民日報》發(fā)表了一篇中國著名科學家錢學森所撰寫的文章：《現代科學技術》。這是一篇出色的文稿，對于了解中國科學技術現代化會往什么方向前進，該文作了不少的披露。數學愛好者都會注意到錢學森在文章中所提的一件事：“去年數學界哄動一時的一件事，是用電子計算機證明了數學上的四色定理。畫地圖要求相鄰兩國不用同一色，一幅地圖只需要四種顏色。要證明這個定理很難，數學家經過上百年的努力，證明不了。去年美國數學家用電子計算機證明了。他們看到這個問題要證明并不是不可能，而是證明的步驟、程序很復雜，人一輩子的時間也證不完

2、。他們把程序編好，交給高速的電子計算機去干。高速電子計算機也用了一千多個小時才證出來。美國數學家認為，他們的主要貢獻不是在證明了四色定理，而在運用電子計算機完成了這件人沒有能夠完成的事?！薄暗貓D四色問題”在錢學森的文章里已經清楚地解釋了。你大概會很驚奇，這甚至連懂得拿起彩筆涂鴉的小孩都會發(fā)覺到的問題，確是一個數學問題嗎？是的，這是一個數學上著名的難題，許多大數學家曾經嘗試想去解決它而不成功，可是這個問題看來又是那么容易明白，好像誰都可以很快解決它似的。我在這里要介紹這個問題的來源，以及美國數學家解決它的經過。害怕數學的讀者不必顧慮，

3、我的解釋都很淺白，相信你是會看懂的。問題的來源在1852年，英國有一個年青人叫法蘭西斯·古特里，他在畫英國地圖涂顏色時發(fā)現：如果相鄰兩國用不同顏色涂上，地圖只需要四種顏色就夠了。他把這發(fā)現告訴他念數學的哥哥費特里，并且畫了一個圖給他看。這個圖最少要四種顏色，才能把相鄰的兩部分分辨，顏色的數目再不能減少。他的哥哥相信弟弟的發(fā)現是對的，但是卻不能用數學方法加以證明，也解釋不出其中的道理?！　∵@年10月23日，費特里拿這個問題向倫敦大學的數學教授奧古斯都·德·摩根請教。德·摩根是當時英國著名的數學家，他也不能馬上解釋。他于當天寫一封信給在

4、三一學院的好朋友威廉·哈密爾頓。他相信像哈密爾頓這樣聰明的人——少時就已經會講八種以上外語，而且數學和物理都很好——是可以幫助他解決這問題的。在信中，他曾這樣寫道：“今天我的一個學生要我告訴他一個事實的理由，而我卻對于這個是否是事實，現在還是不知道。他說如果在面上畫一個圖，使兩個有共同邊緣的區(qū)域涂上不同顏色，那么或許四種顏色而不需要更多就足夠了。請問難道不能夠造出一個需要五種或更多顏色的圖形出來嗎？”很可惜哈密爾頓或許以為這個問題是太淺顯了，而不去注意它。過了8年了。1860年4月14日，德·摩根在一本雜志評價一部叫《發(fā)現的哲學》的

5、書時寫了這樣的話：“當一個人畫地圖——一個國家的地區(qū)圖，很明顯的他需要許多彩色筆使到每對相鄰區(qū)域涂上不同顏色。但涂顏色圖的工人卻很早便知道只用四種顏色就足夠了?！谝粋€鄰域我們不需要四個顏色，除非有四個區(qū)域，這四個區(qū)域每一個都和其他三個區(qū)域交界，而其中的一個區(qū)域一定會完全被其他的區(qū)域包圍起來?？墒沁@個原理：四個區(qū)域不可能在沒有一個被其他區(qū)域包圍的情況下，使到每一個區(qū)域都和其他的三個區(qū)域交界。我們深信是不足以證明這樣明顯這樣簡單的事實：這事實應該像一個公理那樣……?！敝钡?878年英國數學家凱利在英國數學學會以及皇家地理學會提出這個

6、“地圖四色問題”，這問題才受人注意。第二年有一個律師肯泊自稱發(fā)現了證明的方法?？墒窃?890年一位才29歲的年青人希渥特發(fā)現他的證法存有漏洞。希渥特在牛津大學受教育，他主要的研究是這個“地圖四色問題”，在以后60年漫長時間，他先后發(fā)表這方面七篇重要的論文。他78歲才退休，而在85歲時還向倫敦數學學會提呈他最后一篇關于這問題的研究論文。希渥特在世時沒有解決這問題，但他證明了“地圖五色問題”是對的。他那種老彌而堅，孜孜不倦，頑強攻關的精神是值得我們學習的。轉化成數學問題我們現在把這地圖著色問題轉化成數學問題來考慮。在特定的地圖上，每一個

7、區(qū)域當中畫一個小圈圈，我們稱為頂點。如果一對區(qū)域相鄰，我們就用一條弧，把其中的頂點連起來。這樣我們就得到數學上稱為圖的東西。例如由圖一我們得到底下的圖：一個圖G稱為k可染，如果它的每個頂點可以用k種不同的顏色之一來涂，使得相鄰頂點具有不同顏色。如果一個圖是k可染而不是可染，我們就說它的染色數是k。例如圖三中的圖的染色數是4。讀者試試驗證底下的圖分別具有染色數：2，3，2，5。從地圖轉變出來的數學圖，在數學上稱為平面圖，它是指那些頂點能畫在平面上，使到沒有兩條弧會相交。圖三及圖四的，，都是平面圖，但圖四的不是平面圖。比方說下面圖五是不

8、是平面圖呢？你會說不是！因為弧AC和弧BD是相交?？墒侨绻也灰獙D弧那樣畫，稍微移動一點，使它像圖五那樣，這時你得到的是平面圖了！　　怎么樣判斷一個圖是不是平面圖呢？在1930年波蘭數學家?guī)炖兴够l(fā)現一個簡單的判別法則，那就是：