四色問題與五色定理

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

1、四色問題與五色定理（趣味力學(xué)），謝建華，非線性動(dòng)力學(xué)討論班，2009.12.11四色問題與五色定理摘要：1852年一位倫敦的大學(xué)生替他的哥哥向數(shù)學(xué)家DeMorgan提出了一個(gè)問題：任何一張地圖是否僅需要四種顏色即可將所國家著色，并且所有相鄰的國家具不同的顏色？這就是著名的四色問題或四色猜想。時(shí)隔一百多年后的1976年，美國伊利諾斯大學(xué)的兩位教授Appel和Haken利用計(jì)算機(jī)肯定了四色猜想的正確性，但是數(shù)學(xué)家尋求“人工”證明至今未果，這真是對人類智慧的考驗(yàn)。本報(bào)告將用十分鐘的時(shí)間介紹四色問題的歷史和圖論方面的一些基本知識(shí)，以及五色定理的證明過程。希望

2、大家在討論班上度過一個(gè)愉快的周五下午。本報(bào)告的內(nèi)容主要根據(jù)文獻(xiàn)[1]編寫。1.四色問題的歷史1852年10月23日英國數(shù)學(xué)家AugustusdeMorgan寫信給三一學(xué)院的友人數(shù)學(xué)家WilliamRowanHamilton，信中寫道：“我的一個(gè)學(xué)生今天要我為他提供一個(gè)充分的理由，來說明一件我自己還無法判明究竟是對還是錯(cuò)的事實(shí)。他說，如果畫一張圖，圖上任意分成許多部分，凡是有共同邊界線的兩個(gè)部分都要涂上不同的顏色，那么，大概需要四種顏色，而不需要更多的顏色就可以了。請問：難道不能夠構(gòu)造出一個(gè)需要五種或者更多種顏色的圖嗎？”這就是所謂的四色問題，可惜Ha

3、milton并沒有重視這個(gè)問題。二十六年之后，在1878年6月13日的倫敦?cái)?shù)學(xué)會(huì)上，數(shù)學(xué)家Cayley正式提出了四色問題。這個(gè)問題引起了很多人的興趣，包括很多業(yè)余愛好者，其中有師律出身的Kempe和法國文學(xué)教授Mayer等。Kempe曾聲稱自己已經(jīng)解決四色問題。后來不久，就被當(dāng)時(shí)才二十多歲的Heawood指出其證明中的漏洞。Heawood一生研究四色問題共六十年，發(fā)表過幾篇重要的論文，雖然沒有最后解決四色問題，卻證明了五色定理(1890)，又稱Heawood定理。1913年美國數(shù)學(xué)家伯克霍夫發(fā)現(xiàn)一些新的可約構(gòu)形。1968年挪威數(shù)學(xué)家奧雷等人證明了用四

4、種顏色一定可以把不超過四十個(gè)國家的地圖著色，推進(jìn)了四色問題的研究。70年代初人們努力尋找可約構(gòu)形中的不可免完備集，因?yàn)橛盟梢酝ㄟ^數(shù)學(xué)歸納法證明四色問題。1976年美國伊利諾斯大學(xué)的兩位教授Appel和Haken采用Kampe在1879建立的一種思想，利用計(jì)算機(jī)肯定了四色猜想的正確性。Appel和Haken花了1200多小時(shí)的電子計(jì)算器工作時(shí)間，找到一個(gè)由1936個(gè)可約構(gòu)形所組成的不可免完備集，因而在美國數(shù)學(xué)會(huì)通報(bào)上宣稱證明了四色猜想。后來他們又將組成不可免完備集的可約構(gòu)形減至1834個(gè)。四色問題的研究對平面圖理論、代數(shù)拓?fù)?、有限射影幾何和?jì)算器編碼

5、程序設(shè)計(jì)等理論的發(fā)展起了推動(dòng)作用。2.平面圖與歐拉公式一個(gè)圖是由一些點(diǎn)和線構(gòu)成，這些點(diǎn)稱為頂點(diǎn)，線稱為邊，如圖1。7四色問題與五色定理（趣味力學(xué)），謝建華，非線性動(dòng)力學(xué)討論班，2009.12.11圖1平面圖如果一個(gè)圖能畫在平面上，而各邊不相交，這樣的圖稱為平面圖，否則稱為非平面圖。圖1(a)是平面圖，實(shí)際上，圖1(b)也是平面圖，因?yàn)樗鼈兪峭瑯?gòu)的。任何一個(gè)凸多面體都可以用一個(gè)平面圖來表示，如圖2(a)是正六面體和其在平面上表示，圖2(b)是正十二面體和其在平面上表示。圖2(a)正六面體；(b)正十二面體對凸多面體有著名的歐拉公式(1)其中、、分別是凸

6、多面體的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)。例如，對正六面體：、、；正十二面體：、、，(1)式都是成立的。如果一個(gè)圖，對圖的任何兩個(gè)頂點(diǎn)都有由邊構(gòu)成的路將它們連接(關(guān)聯(lián))，此圖稱為連通的，否則稱為不連通的。如圖1和2中的圖都是連通的，而圖3是不連通的。顯然一個(gè)不連通圖是由若干個(gè)連通分支組成，如圖3中的圖有兩個(gè)連通分支。7四色問題與五色定理（趣味力學(xué)），謝建華，非線性動(dòng)力學(xué)討論班，2009.12.11圖3不連通圖定理1對任何一個(gè)連通的平面圖，歐拉公式(2)成立。證：對邊數(shù)用數(shù)學(xué)歸納法。當(dāng)時(shí)，連通圖有一個(gè)頂點(diǎn)和一面，即和，故(2)式成立。設(shè)對任意具有條邊的平面連通圖，(

7、2)式成立。一個(gè)具有條邊的平面連通圖可由一個(gè)具有條邊的平面連通圖(圖4(a))添加一條邊而形成，如圖4(b),(c)所示。由歸納假設(shè)，對圖4(a)，(2)式成立。對圖4(b)中的增加邊方式，圖的頂點(diǎn)數(shù)未變，而邊數(shù)和面數(shù)與圖4(a)相比，各增加1，(2)式仍然成立；對圖4(c)中的增加邊的方式，圖的面數(shù)未變，而頂點(diǎn)數(shù)和邊數(shù)各增加1，(2)式仍然成立。由歸納法，(2)式對任意的平面連通圖成立。圖4(a)條邊的平面連通圖；(b)和(c)條邊的平面連通圖現(xiàn)在來談地圖著色問題了。地圖著色問題中，我們假定任何一個(gè)國家是由7四色問題與五色定理（趣味力學(xué)），謝建華，

8、非線性動(dòng)力學(xué)討論班，2009.12.11一個(gè)單連通的區(qū)域組成，任意兩個(gè)相鄰國家之間的邊界只有一條。如圖5(a