多項式怎麼染上了顏色?-科學人雜誌
不可勝數

多項式怎麼染上了顏色?

2012-02-01 李國偉
從地圖著色問題發展出的多項式,已經超出圖論,跨入代數幾何領域!
翻翻英文字典,凡是以chrom起首的字,絕大部份跟「顏色」有關,因此,看到chromatic polynomial這樣的名詞,豈不令人好奇:怎麼多項式也會有顏色呢?一提到顏色,就讓人聯想起「四色定理」。四色定理雖然起源於地圖的著色問題,但是更適合用現代圖論的術語來描述。平面上給定有限個稱為「結點」的點,在某些相異結點之間用「邊線」連起來,將結點與邊線看做整體,就構成了「圖」。除了開始給定的結點,邊線之間如果還產生其他的交點,並不當做是圖的結點。定義一個圖的關鍵在於哪些結點間有邊線相連,至於具體的畫法卻有無窮多種選擇。如果至少有一種畫法展現出邊線只在結點處相交,則稱該圖為「平面圖」。對於任何給定的圖,如果將結點塗上顏色,並且要求相鄰的(即有邊線連接的)結點塗以不同的顏色,顯然只要顏色數量夠多,這種所謂的「正當著色」一定存在。一個圖的「著色數」就是可以正當著色該圖的最少色數。1976年才獲得證明的「四色定理」,保證任何平面圖的著色數不會超過四。1912年美國數學家伯克霍夫(George David Birkhoff)引進了「著色多項式」的概念,就是想用來解決四色問題,但是他沒有成功。如果圖...

登入會員以閱讀更多精彩內容

# 關鍵字:名家專欄不可勝數
更多文章
活動推薦更多
追蹤科學人