圖書序言
第15章 地圖著色
西洋棋盤隻需要兩種顔色,就能塗滿整個盤麵,方法是讓緊鄰(共用一條邊綫)的兩個小方格各塗上不同顔色。有些地圖也是一樣,隻需兩種顔色就可以塗滿,使相鄰的國傢有不同的顔色,但是有些地圖就做不到瞭。
為瞭簡單起見,當我們說「能以兩種顔色著色的地圖」或「兩色地圖」時,我們指的是隻要用兩種不同的顔色,就可以把整張地圖塗滿,而且那些共享至少一條邊綫的國傢,會有不同的顔色。同樣的,在本章稍後,我們可能會談到「用三種不同的顔色塗滿地圖」或者說「一張五色地圖」,都是指:共享一條邊綫的國傢顔色不同。
我們假設前麵兩張地圖,畫的都是一個有很多國傢的大島。我們稱那些國界的交叉點為「頂點」,而不在海岸綫上的頂點則稱為「內陸頂點」。而「頂點的次數」是指交會在這個頂點的邊綫數目。這種觀念已經在第7章扮演過關鍵性的角色。
那些海島上有眾多國傢的地圖裏,由於包圍內陸頂點的國傢必須交替著上不同的顔色,因此若有個內陸頂點的次數是奇數的,這張地圖就沒辦法用兩種顔色來著色。我們因此得到下列定理:
定理1:如果一個海島上有許多國傢的地圖能用兩種顔色來著色,則每個內陸頂點的次數都是偶數。
至於四色地圖的問題,可以迴溯到1852年的10月23日,是梅氏(K. O. May)提齣的。就在這一天,古斯瑞(Francis Guthrie)把它拿給他的老師,邏輯學傢笛摩根(Augustus De Morgan, 1806-1871)看,而笛摩根則寫信問哈密頓(W. R. Hamilton, 1805-1865):
我的學生今天就一件事問我原因何在。他認為這件事是一項事實,但我不那麼確定,以前也沒注意到。他說如果把一個圖形隨意分割,並且把每塊區域塗上不同的顔色,使得同一條邊綫的兩邊顔色不同,則隻需要四種顔色就一定夠瞭,甚至更少些……
你認為如何?如果真的是這樣,你以前知道嗎?我的學生說他曾以英格蘭的地圖來做實驗。這件事,我愈想愈覺得它是真確的。