不可勝數

多項式怎麼染上了顏色?

從地圖著色問題發展出的多項式,已經超出圖論,跨入代數幾何領域!

撰文/李國偉

不可勝數

多項式怎麼染上了顏色?

從地圖著色問題發展出的多項式,已經超出圖論,跨入代數幾何領域!

撰文/李國偉


翻翻英文字典,凡是以chrom起首的字,絕大部份跟「顏色」有關,因此,看到chromatic polynomial這樣的名詞,豈不令人好奇:怎麼多項式也會有顏色呢?


一提到顏色,就讓人聯想起「四色定理」。四色定理雖然起源於地圖的著色問題,但是更適合用現代圖論的術語來描述。平面上給定有限個稱為「結點」的點,在某些相異結點之間用「邊線」連起來,將結點與邊線看做整體,就構成了「圖」。除了開始給定的結點,邊線之間如果還產生其他的交點,並不當做是圖的結點。定義一個圖的關鍵在於哪些結點間有邊線相連,至於具體的畫法卻有無窮多種選擇。如果至少有一種畫法展現出邊線只在結點處相交,則稱該圖為「平面圖」。


對於任何給定的圖,如果將結點塗上顏色,並且要求相鄰的(即有邊線連接的)結點塗以不同的顏色,顯然只要顏色數量夠多,這種所謂的「正當著色」一定存在。一個圖的「著色數」就是可以正當著色該圖的最少色數。1976年才獲得證明的「四色定理」,保證任何平面圖的著色數不會超過四。1912年美國數學家伯克霍夫(George David Birkhoff)引進了「著色多項式」的概念,就是想用來解決四色問題,但是他沒有成功。


如果圖G有n個結點,令C(G, k)表示最多用k種顏色把G正當著色的方法數(兩種著色法只要在某個結點上顏色相異,就看成不同的方法)。有一種化繁為簡的手法可用來計算C(G, k):令e是G的一條邊線,從G裡刪掉e就得到一個邊線數較少的圖,記做G\e。也可以把e收縮起來,使得兩個端點融合成一個結點。如果此時產生將結點連接到自己的邊線,就把這種迴圈刪掉。如此也得到一個邊線數較少的圖,記做G‧e。圖G\e的正當著色分成兩類,一類是把e的端點塗以相異顏色,另一類是把端點塗以相同顏色,後者的數量恰好等於圖G‧e的正當著色數。把後者除去,剩下的又正好等於G的正當著色數。從而導出一條重要的遞迴公式:C(G, k)=C(G\e, k)-C(G‧e, k)。


反覆使用這條公式,圖的邊線就越來越少,當最後只剩下沒有邊線相連的n個孤立點,此時的相異著色總數恰為 k n ,也正好是多項式 x n 在整數k處取的值。由前面這段敘述經歸納法,便能得到唯一的n次多項式P(G, x),滿足同樣的遞迴公式P(G, x)=P(G\e, x)-P(G‧e, x)。P(G, x)的常數項為0,最高次項 x n 的係數為1,各項係數正負相間,並且對於所有非負整數k都滿足P(G, k)=C(G, k),這個P(G, x)就稱為G的著色多項式。


著色多項式P(G, x)=a n x n-a n-1 x n-1+......+(-1) n a 0中的每個ai都是非負整數。對於一些特定的圖類,著色多項式可以明確地計算出來,它們所展現的數列a 0, a 1, ... , a n都有一個特徵,就是依序先由小變大再由大變小,這樣的數列稱為單峰(unimodal)數列。加拿大數學家瑞德(Ronald C. Read)在1968年提出「著色多項式係數的絕對值都是單峰數列」的猜想,因為進展極端困難,成為圖論中相當有名的猜想。


2011年6月美國密西根大學韓裔研究生許(June Huh)終於解決了瑞德的猜想,他的證明方法遠超出圖論的範圍,需要用到代數幾何學處理奇異點的理論,這又展現了數學理論之間出人意表的關聯性。其實著色多項式還有一項驚人的應用,就是它會與統計力學裡的波茲模型(Potts model)發生關聯,也就是要把著色多項式的變數x當做是複變數,然後考慮所有複數根的分佈狀況。想不到伯克霍夫當年失敗的嘗試,卻引發後來精采的研究,數學世界裡真不能完全以成敗論英雄啊!


更多相關文章

2018年7月197期恐龍崛起純屬僥倖? 雜誌訂閱

本期最新文章