2  3   Contents

兩色地圖

Part I

        讓我們先看幾個比較簡單的圖形。你需要多少種顏色才能將下面這個圖形完成著色? 

        顯然是兩個顏色就夠了。塗法是在相鄰(共用同一邊線)的兩個小方格中塗上不同顏色。如下:

大家應該都看過西洋棋的棋盤,是不是和上圖很類似呢?

   

        讓我們再試試下面這張圖:

看起來有點複雜,但是別被它的外表嚇到了,它也只需要兩個顏色就能塗滿。

        當然不是所有的圖都可以這樣做,那麼是否有什麼簡單的方法可以幫助我們判斷一張圖是不是這種所謂的兩色地圖呢?

        若將上圖看成是一個海中的小島,各個區域是不同的國家,我們注意到它們的國界總會在某些點上交會,而那些不在海岸線上的交點就稱為「內點」。對於相交在同一內點的幾個國家而言,它們必定是要交替塗上不同的顏色,如下圖:

 

        觀察上圖,我們不難發現圖中每一個內點的秩都是偶數。讓我們再看看,若一個圖圖中存在某個內點的秩是奇數又如何呢?

以下圖為例:

我們若以兩種顏色從第一個區域開始,依逆時鐘方向交替塗完區域234之後,區域5就無再法用原本的兩個顏色來塗,也就是說區域5勢必要用到第三個顏色。

 

        一般而言,一個圖若圖中存在某個內點的秩是奇數,n,又如何呢?

        我們將環繞該點的區域,依逆時鐘方向填入數字12n。如上例,我們若以青、黄兩種顏色從區域1開始,依逆時鐘方向交替將各個區域塗色,則除了最後一個區域(也就是區域n)之外,所有奇數區域都將塗上青色,而有偶數區域都將塗上黄色,如下圖:

而區域n因為與區域1及區域n-1(偶數)相鄰,因此不能用原本的兩個顏色來塗,也就是說區域n勢必要用到第三個顏色。

        這意味著若某一內點四周有奇數個國家,則無法以兩色來著色。

        我們因此得到下面的結論:「如果一個海島上的國家能以兩種顏色來著色,則每個內點的秩一定是偶數。」

 

Previous   Next   Contents