2014年3月27日

塗塗抹抹

作者/游森棚(任教於臺灣師範大學數學系)

任何一本高中的數學講義或參考書一定有這個可愛的哈哈笑著色問題:用5 種顏色塗下列區域,但相鄰區域不同色,一共有幾種方法?
答案是簡單的:依序塗嘴巴、下巴、右臉、左臉、右眼、左眼,共有5×4×3×2×4×4=1920種方法。但這一類問題不單純是塗塗抹抹的樂趣,背後的學問可很有意思,最近教研究所的課又重溫了一次。這個月的專欄就來介紹一下塗塗抹抹的數學。

圖論(graph theory)中討論的是一般的圖,有t 個顏色可以使用。一個「圖」包含了一些點,其中某些點之間有連邊。著色要把顏色塗在頂點上,要使得相鄰的點不同色。哈哈笑問題基本上就相當於底下右圖(姑且稱為哈哈笑圖)的著色:
如果有t 種顏色可以用,同樣的想法可得到哈哈笑圖的著色共有
t(t - 1)(t - 1)(t - 1)(t -1)(t - 1) = t6 - 8t5 - 24t4 - 34t3 + 23t2 - 6t種方法。這個多項式稱為哈哈笑圖的「染色多項式」。

一般而言,給定任意有n 個頂點的圖G,可以證明用t 個顏色的著色法總數都會是一個t 的多項式,且次數恰為n。這個多項式稱為G 的染色多項式,記為XG(t)。比如G 取下圖,則讀者可以算出XG(t) = t4 - 5t3 + 8t2 - 4t 嗎?

XG(t) 是圖論中重要的研究對象。比如說,若G 是平面圖(planar graph,即邊不相交的圖)。則,要證明XG(4) > 0 可真是一個非常非常困難的問題——事實上這就是有名的四色定理:一張地圖用四個顏色塗色就可以讓相鄰區域不同色。......【更詳細的內容,請參閱第532期科學月刊】

1 則留言:

magiclass 提到...

第四段有點錯誤。

公式的等號前面應該是t(t-1)(t-2)(t-3)(t-1)(t-1)才對,等號後的式子無誤。