Google chrome, Chromatic

Google最近推出自己的瀏覽器chrome, 不過我不討論這個產品的意義和什麼了不起的地方. 我有興趣的是這個產品的圖示. 就是左邊那個彩色的東西. 一般人看可能以為是個漂亮又經過設計的圖. 但是它其實是個數學物件. Google是很重視數學能力的一家公司, 把這個當作產品的圖騰也不奇怪.

chrome(絕對不是指鉻元素)來自希臘文chroma, 是顏色的意思. 念過圖論的人大概會知道有個探討著色數(Chromatic number)的topic. 就是節點(vertex)和邊(edge)組成的Graph需要要多少記號標記在節點上使得相鄰(有邊連著)的節點是不同的記號. 尤其是討論平面圖上(節點和節點的連接不會互相交錯的圖), 那個數字最少是多少.

這個問題的答案是4, 這就是有名的4色問題. 最生活化的例子就是只要4種顏料就能把各種地圖上相鄰區域用不同顏色隔開. 就像chrome這個圖示, 我把這個平面圖用節點(顏色區塊)和邊(相鄰關係)抽象化成旁邊那個Graph. 這"簡單"的平面圖卻是最複雜的情形, 4個節點需要4種顏色, 不過再多加節點也不會超過這個數字. 所有需要4個顏色的地圖都會包含跟這個同構的Graph.

通常一般人看到這樣的結論都會不信邪, 想要畫出需要5種顏色以上的平面圖(地圖), 當然都是徒勞無功.

4色問題解決了, 但卻是用計算機窮舉法將平面圖一一解開, 目前還欠缺純數學的證明. 如果有人提出只用紙筆的証明, 就會名留人類歷史, 但不一定上天堂.