第7 章图着色.pdfVIP

2/18/2008 131 第 7 章 圖著色 老師教我們顏色是紅、橙、黃、綠…… 你用的顏色為什麼是 1 、2 、3 、4……？ – 鄰居小女孩 1850 年英國有一位學生 Francis Guthrie （後來成為南非大學數學教授）對於地圖著色很 感興趣。許多地圖上都將地域作不同的區域劃分，例如分割成國家、縣市等等。依此方式劃 分出來的區域示意圖本質上就是前一章提到的平面圖，其中各個區域就分別代表面，區域的 邊界即邊，而邊匯集處為頂點。由於地圖上除了區域分隔線之外還有河川等等各種的線條， 有時要清楚看出區域的分佈概況不是那麼方便，因此經常會將區域著色好讓人可以一眼看出 那些地方是屬於那個區域的範圍。 圖 7.1 ：一張歐洲的地圖，將每個國家的範圍各著上一種顏色。 以這種方式將地圖著色時，要領就是相鄰的區域（即有共用邊的面）必須是不同的顏色， 不然就會導致混淆。如果只是共用頂點倒還無所謂。為了達到這個目的，最簡單的方法當然 是乾脆每個國家都塗不一樣的顏色，但這未必是好方法；首先你需要調配非常多種顏色的顏 料（當然電腦發達的今天比較沒有這種問題），其次是地圖過份花花綠綠，看上去也不見得舒 服。事實上如圖 7.1 所示，即便像歐洲這麼多國家的地圖，也只要用五六個顏色就可以達到 我們的要求，而且實際上還可以用得更少。 132 第 7 章 圖著色 2/18/2008 根據他哥哥 Frederick Guthrie 的回憶 [7] ，Francis 發現最多只要用四種顏色就可以將任 何一張平面地圖的各區域著色、使得任兩個有共用邊界的區域都著不同顏色。並沒有清楚地 記載他是不是有一個證明，但顯然下面這個圖告訴我們，要達到上述的結果，四個顏色是不 能再減少的。 2 3 1 4 圖 7.2 ：必須使用四色的地圖。 在取得 Francis 的同意之下，哥哥把這個結果告訴他的老師、倫敦大學的數學教授 de Morgan ，老師很高興地宣稱這是個新結果。不過連 Francis 都沒有能讓自己滿意的證明， de Morgan 雖然感覺這個答案是對的，但也一直未能找到好的證明。他在 1852 年 10 月23 日 曾寫信給 Hamilton 尋求他的意見，而他在三天後回信，表示不會很快去思考這個問題。然 而 de Morgan 的好奇心促使他到處宣傳這個問題，1860 年4 月14 日他更寫了篇文章 [16] 討 論這個問題。 問題於是流傳開來。美國邏輯學家 Peirce 對此有了回應 [4] ，曾在哈佛的數學會發表一 個「可能的證明」。Cayley 於 1878 年6 月13 日倫敦數學會 [27][28] 時曾詢問四色定理是否 已經被證明，並且很快寫了一篇相關的短文，試著指出這個問題的困難度。真正的震撼是 Cayley 在劍橋的學生 Kempe 的證明 [11] ，這個證明後來雖然被發現是錯的，但其中給出的 Kempe 鍊的觀念至今仍是著色問題的一個基礎起手式。Kempe 的文章雖被找出漏洞，但他 很快地又加以修正 [12][13] ，爾後一段時間裡大家都相信這個修正後的證明是正確的，而 Kempe 更因此在 1879 年被選為英國皇家學院院士。 順便要提到的一個人是 Tait 。首先，Cayley 和 Kempe 都已經十分了解，證明四色定理 時，可以假設每一個頂點的度數都是3 ；因為，如下圖所示，假如有度數非3 的頂點，我們 可以將它擴張成一個圈、此時每個點的度數都是 3 ，等著完色之後再縮回原來的點。如果任 何一個3-正則的地圖都