四色問題

繪制地圖，除了要求保證其準(zhǔn)確性外，如何給地圖著色，從而能明顯地區(qū)分地圖上的各個(gè)區(qū)域，也是十分重要的. 很早以前，繪圖員就發(fā)現(xiàn)，只要配置幾種顏色就可以給任何地圖著色了. 究竟最少要用幾種顏色呢？這倒變成數(shù)學(xué)家們十分感興趣的問題了.

四色問題的提出

1852年，畢業(yè)于倫敦大學(xué)的英國(guó)青年數(shù)學(xué)家格思里來(lái)到一家科研單位搞地圖著色工作時(shí)，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來(lái)，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家都被著上不同的顏色. ”這個(gè)現(xiàn)象能不能從數(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年，英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題.

世界上許多數(shù)學(xué)家爭(zhēng)相進(jìn)行研究，其中有肯普、希伍德、閔可夫斯基等，結(jié)果仍然進(jìn)展甚微. 人們開始認(rèn)識(shí)到，這貌似簡(jiǎn)單的題目，其實(shí)是一道超級(jí)數(shù)學(xué)難題.

四色問題的證明

1878～1880兩年間，著名的律師兼數(shù)學(xué)家肯普和泰勒兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了. 誰(shuí)知到了1890年，在牛津大學(xué)就讀的年僅29歲的赫伍德以自己的精確計(jì)算指出了肯普在證明上的漏洞. 不久，泰勒的證明也被人們否定了. 人們發(fā)現(xiàn)他們實(shí)際上證明了一個(gè)較弱的命題——五色定理，就是說(shuō)對(duì)地圖著色，用五種顏色就夠了.

1913年，美國(guó)著名數(shù)學(xué)家、哈佛大學(xué)的伯克霍夫利用肯普的想法，結(jié)合自己新的設(shè)想，證明了某些大的構(gòu)形是可約的. 后來(lái)美國(guó)數(shù)學(xué)家富蘭克林于1939年證明了22國(guó)以下的地圖都可以用四色著色. 1950年，溫恩從22國(guó)推進(jìn)到35國(guó)，1968年，奧爾又證明了39國(guó)，隨后在1975年又有報(bào)道稱有人已證明到了50國(guó).

地圖與拓?fù)?/p>

對(duì)于地圖著色問題來(lái)說(shuō)，各個(gè)區(qū)域的實(shí)際形狀與大小都不重要，重要的僅僅是它們的相對(duì)位置. 右邊四幅圖，有地圖，有從地圖演變過來(lái)的圖，這些圖對(duì)于著色來(lái)說(shuō)都是等價(jià)的，每幅圖5個(gè)區(qū)域之間的相互位置是一樣的，按數(shù)學(xué)家的說(shuō)法，它們具有拓?fù)涞牡葍r(jià)性.

二色地圖

大多數(shù)地圖都需要用4種顏色來(lái)上色，但是有些特殊的情況不要用這么多的顏色，其中一種就是地圖中只有端點(diǎn)在整幅地圖邊界上的線段的情況. 在這種情況下只需要2種顏色. 將線一條一條地畫在一張紙上，每增加一條線時(shí)，將新增加的直線的一邊的地區(qū)全部換成另一種顏色，這使得在舊的鄰邊和新的鄰邊兩邊的顏色都不相同.

同樣的方法也可以推廣到穿過整個(gè)紙面的簡(jiǎn)單曲線或者閉合的圓圈的情況. 當(dāng)一張地圖中的所有交點(diǎn)均為偶點(diǎn)，即所有交點(diǎn)有且僅有偶數(shù)條鄰邊時(shí)，這張地圖就可以用2種顏色上色.

三色地圖

當(dāng)一張地圖中的交點(diǎn)出現(xiàn)奇點(diǎn)的情況（即交點(diǎn)有奇數(shù)條鄰邊），運(yùn)用2色就不可能了，必須用3種以上的顏色. 這里的三張地圖恰好都只需要3種顏色. 想想看，它們有什么特殊的地方？

我們還是回到大多數(shù)地圖的情況，這里是我們制作的3張“數(shù)學(xué)”地圖，看看它們是不是必須用四色才能完成著色任務(wù)，如果用二色、三色試一下，有沒有可能.

給點(diǎn)涂色

這里有一個(gè)圖形，上面有若干個(gè)頂點(diǎn)（交叉點(diǎn)）. 如果我們給這些點(diǎn)涂色，并要求任何一根線的兩個(gè)頂點(diǎn)的顏色不同，最少需要多少種顏色？

給線涂色

如果我們給這里的圖形中的曲線涂色，并要求相鄰的線段的顏色不同，最少需要多少種顏色？endprint