- 專欄
文章專區
2014-04-01塗塗抹抹
532 期
Author 作者
游森棚／任教於臺灣師範大學數學系。
任何一本高中的數學講義或參考書一定有這個可愛的哈哈笑著色問題：用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期】