動機
正常著色回答的是:相鄰頂點能否被賦予不同的顏色。若把所有這樣的賦值都數出來,則提出了一個更豐富的問題:當有名稱的調色板大小改變時,這個數目如何變化?令人驚訝的是,對每個非負整數的調色板大小,同一個多項式都給出答案。
這個多項式既可以透過禁止單色邊來構造,也可以按照被刪除的一條邊的兩個端點是否獲得相同顏色來拆分。這兩種方法給出同一個對象的不同證明。它們也揭示了一些有用的局限:對有名稱的顏色計數不同於對無名稱的顏色類計數,而且色多項式相等並不迫使兩個圖同構。
定義
定義 10.1.1
(正常著色與有名稱的調色板)
設 是有 個頂點、 條邊的有限簡單無向圖。對整數 ,正常 -著色是一個函數 ,它給相鄰頂點賦予不同的值。它不必用盡所有可用的顏色。調色板中不同的名稱給出不同的賦值。把正常著色的個數記為 。
沒有頂點的圖恰有一種著色,即空函數,即使調色板為空也是如此。非空圖在調色板為空時沒有著色。非空圖的色數是容許正常著色的最小正整數 ;對零頂點圖我們取零。
對 ,令 為生成圖 的連通分支個數,其中孤立頂點也計算在內。對一條邊 ,刪除 是去掉這條邊。收縮 是把它的兩個端點等同,去掉被收縮的邊,並把重複出現的邊合併為單條邊。因為原圖是簡單圖,不會出現其他自環。所得的簡單圖表示兩個端點顏色相等。
定理/命題
定理 10.1.2
(色多項式的存在性與最初幾項係數)
對每個非負整數 ,著色個數都等於下面這個整係數多項式的值:
它是首一的,次數為 。當 時,其常數項為零, 的係數為 。當 時, 的係數為 ,其中 是三角形的個數。零頂點圖的多項式為一。
定理 10.1.3
(刪除–收縮與乘積法則)
對每條邊 ,
不相交並滿足 。若 是兩個圖的並,這兩個圖的頂點交恰為一個頂點,且沒有其他連接邊,則
這是一個多項式恆等式,因此在零處也有意義,而無須在數值上除以零。
定理 10.1.4
(樹、森林與圈)
個頂點的樹的多項式為 。有 個頂點、 個連通分支的森林的多項式為 。當 時,圈 滿足
證明思路或證明
證明
(容斥原理與最初幾項係數)
從全部 種著色出發,讓每個禁止事件要求某一條邊的兩個端點顏色相同。要求由 所標記的全部事件同時發生,就迫使 的每個連通分支都是單色的。各分支獨立地選擇顏色,共得到 種賦值。由包含與排除原理即得該求和公式。對零頂點圖,對應的項是常數多項式 ,在零處也是如此。
只有空邊子集有 個連通分支,這證明了多項式是首一的。非空圖的每個生成子圖至少有一個連通分支,所以沒有常數項。要得到 個連通分支,簡單圖必須恰好選取一條邊,由此得係數 。要得到 個連通分支,每個兩條邊的子集都貢獻正項。唯一額外的可能是構成三角形的三條邊,它貢獻負項。事實上,連通分支總共減少二,允許的情形是兩個互不相連的二頂點分支,或一個三頂點分支;簡單的三頂點圖至多有三條邊。這就證明了三角形的係數公式。
證明
(按端點顏色作刪除–收縮)
對於刪除–收縮,把 的正常著色分為兩組:端點顏色不同的和端點顏色相同的。第一組恰好是 的正常著色。把顏色相同的端點等同起來,給出第二組到 的正常著色的雙射。等同所產生的多重相鄰約束是完全相同的,這就是合併平行邊無妨的原因。該等式對每個整數調色板大小都成立,因此是多項式恆等式。
證明透視
刪除–收縮中唯一的分類用到了甚麼
證明從 而不是從 出發:刪除 去掉了一個約束,所以 的著色包含 的全部著色。唯一的分類是看 與 是否同色。異色情形恰好恢復被刪除的約束,其餘不變,所以它計數的是 。收縮在同色情形中出場。把 合併為一個頂點 是可逆的,因為兩個端點顏色相同;而 必須與 或 的每個鄰點異色。若 與 有共同鄰點 ,則 與 之間得到的兩個約束完全相同,這就是合併平行邊不會損失任何資訊的原因。 的簡單性在這裏用到:合併唯一可能產生的自環來自 本身,而它已被移除。論證在每個整數 處證明了恆等式;由於在無窮多點上一致的兩個多項式相等,它成為多項式恆等式。
證明
(不相交並與單頂點並的乘積)
不相交的圖從同一個調色板獨立地選擇著色,這證明了乘積法則。對於僅共享一個頂點的並,設 為正整數,由顏色名稱的對稱性,每一塊在共享頂點被指定為某個給定顏色時恰有 種著色。該顏色有 種選法,再把兩塊組合起來,就證明了 。對無窮多個正整數相等,就證明了多項式恆等式。每一塊都有一個頂點,所以它的多項式含有因子 ;形式上除以一個因子得到的商是多項式,而不是在零處無定義的求值。
證明
(樹、森林與圈)
給樹選定根。根有 種選擇;在其父頂點著色之後,其他每個頂點有 種選擇,且沒有額外的邊約束。這證明了樹的公式,對各連通分支取乘積即得森林公式,空森林也包括在內。三角形的多項式為 ,與 時的圈公式一致。對 ,刪除圈的一條邊得到 個頂點上的路徑,收縮這條邊得到 。把歸納假設中的圈表達式代入刪除–收縮,即得所示公式。三角形是單獨的歸納基礎,因為收縮其一條邊得到一條簡單的邊,而不是簡單的二重圈。
例題詳解
例題 10.1.5
(用刪除與收縮計算四圈)
刪除 的一條邊得到四個頂點上的路徑,收縮這條邊得到三角形。因此
用兩種顏色時它的值是二,用三種顏色時是十八。係數記錄了四條邊以及 個三角形,與該圖相符。
例題 10.1.6
(帶一片葉子的三角形在兩塊之間共享一個頂點)
在三角形的一個頂點上接一片葉子。把三角形的多項式與一條邊的多項式結合,並形式上除以共享頂點的因子,得 。用三種顏色時有十二種著色。等價地,三角形有六種著色,葉子可以從與其鄰點不同的兩種顏色中任選一種。兩種計算都是在數有名稱的調色板賦值。
例題 10.1.7
(該多項式不是完全的圖不變量)
四個頂點上的路徑與有三片葉子的星圖不同構:它們的度序列分別為 和 。兩者都是樹,因此多項式都是 。它們的著色數對每個調色板大小都相同,而鄰接結構卻不同。計數多項式可以保留有用的統計量,卻無法編碼整個圖。
為何必須保留生成頂點集
在包含與排除公式中,刪除邊並不刪除它們的端點。孤立頂點仍然獨立地選擇顏色,並貢獻連通分支。特別地,空邊子集的連通分支數恰好等於原圖的頂點數。若只數含有邊的連通分支,就會抹去這些自由的顏色選擇,甚至破壞多項式的首項。
這些禁止事件並不互斥。單色三角形同時滿足三個邊相等事件,而其中只有兩個相等關係是獨立的約束。包含與排除原理保留了三重交,並修正了這一重疊。這解釋了第三項係數中的三角形修正:公式是按約束的連通效應來計數的,而不僅僅是按所選邊的條數。
圖是簡單圖,對係數的解釋很重要。平行邊施加的是同一個顏色不等約束,所以把它們當作不同的圖邊來數,不會得到係數為負的總重數。自環則會禁止所有著色。所述範圍排除了這兩種現象,而收縮明確地回到簡單圖的情形。
有名稱的顏色與無名稱的獨立類
正常著色把頂點集劃分為它的各個非空顏色類,每個顏色類都是獨立集。若一個劃分恰有 塊,給這些塊分配互不相同的調色板名稱,就得到 種著色。因此另一種展開是
其中 是把頂點集劃分成 個非空獨立塊的劃分個數。這由一個可逆的纖維分解得出,而不是把整個著色數除以某個固定的階乘。
對於無邊圖,每個塊都是獨立的,所以這些係數就是第二類 Stirling 數。該恆等式成為 按下降階乘的展開。對於有邊的圖,被禁止的同塊關係改變了塊劃分的計數。這種關係把圖的著色與帶標號集合的枚舉聯繫起來,同時保留了各對象不同的定義。
反例模式
一般情況下,除以調色板的階乘是無效的
兩個孤立頂點用三色調色板有九種著色。除以 得到一又二分之一,它不可能是無名稱劃分的個數。實際上有兩種顏色類劃分:一個塊包含兩個頂點,或兩個單點塊。它們分別有三種和六種有名稱的實現。未使用的顏色使纖維的大小依賴於非空類的個數。
計數、判定與計算成本
對於非空圖,使多項式取正值的最小正整數就是它的色數。這個等式由整數處的計數解釋得出。在任意實數或負數處的取值只是多項式的求值,並不是對非整數個或負數個顏色的調色板的計數。
刪除–收縮會終止,因為每個分支都透過刪除或收縮去掉了一條原來的邊,而合併平行邊可能去掉更多的邊。直接的遞歸計算仍可能有指數多個分支。關於調色板變量的多項式存在,並不意味著用這種方法能在圖的大小的多項式時間內算出它的係數。
特殊結構可以簡化計算。森林有直接的乘積公式;固定割點的顏色之後,割點把圖分成互相獨立的幾塊。這些簡化必須由實際的分解假設來證明。把任意子圖的多項式相乘,會重複計數,或忽略它們交集上的約束。
概念視角組合
同一個圖有幾種不同的計數描述
包含與排除原理數的是由所選相等關係迫使成為單色的連通分支。刪除–收縮區分端點顏色不同與相同兩種情形。下降階乘展開在給類命名之前先數獨立的頂點劃分。它們描述的是同樣的著色,但組織的中間對象不同,從而使不同的恆等式變得顯而易見。
常見錯誤
常見錯誤
(調色板大小不是所用顏色的數目)
正常著色不必用盡調色板中的所有名稱。對單一條邊,,而這六種著色沒有一種用到全部三種顏色。若把 讀作恰好使用 種顏色的著色數,這裏便會得到零。用盡全部 種調色板顏色的著色數是 ,其中 來自上文的下降階乘展開;它不是 。
常見錯誤
(刪除–收縮並不自動就是高效算法)
一連串較小圖的計算並不自動就是高效算法;遞歸的規模和算術運算必須分別分析。對有 條邊的森林,收縮從不產生平行邊,所以兩個分支都保留 條邊並仍是森林;一直遞歸到沒有邊為止,恰好產生 個無邊的葉,儘管乘積公式能立即給出答案。
收縮是把端點的顏色合併,而刪除一個頂點則會徹底去掉一個顏色選擇。
最初幾項係數揭示了頂點數、邊數和三角形數,但樹的例子證明它們並不決定同構。另外,不要在虛構的簡單二重圈上應用圈的收縮遞推;三圈這一基礎情形必須直接驗證。
總結
有名稱的調色板下的正常著色,透過包含與排除原理定義出一個整係數多項式。刪除–收縮與圖的分解提供了互補的計算方法。樹與圈的公式、係數統計量以及獨立類展開,既顯示了該多項式所含的結構資訊,也顯示了它的局限。
練習
快速檢查
(求有七個頂點、三個連通分支的森林的多項式。它有多少種正常二著色和三著色?)
若有孤立的分支,也要計算在內。
解答 · 答案
多項式為 。用兩種顏色時值為八;用三種顏色時為 。孤立頂點是只有一個根的選擇且沒有額外因子的連通分支,所以公式已經把它們包括在內。
快速檢查
(一個簡單的五頂點圖的最前幾項是 。求它的邊數和三角形數。)
題目給出了一種可能的係數模式;這兩個統計量的公式不同。
解答 · 答案
的係數是邊數的相反數,所以 。 的係數等於 ,因此 。這個模式是可以實現的,例如從四團中去掉一條邊,再接上一片新葉子:這個圖有六條邊和兩個三角形。由此並不能斷言存在唯一的圖。
快速檢查
(計算四個頂點的完全圖的多項式,並驗證關於邊數與三角形數的係數解釋。)
依次為互相鄰接的頂點選擇顏色。
解答 · 答案
多項式為 。它記錄了六條邊,其第三項係數給出 個三角形,恰好是四個三頂點子集。當調色板大小小於四時乘積為零,符合要求;在四時有 種賦值。