圖論課件著色的計數(shù)與色多項式1第一頁，共三十二頁，2022年，8月28日本次課主要內容(一)、色多項式概念(二)、色多項式的兩種求法著色的計數(shù)與色多項式(三)、色多項式的性質2第二頁，共三十二頁，2022年，8月28日所謂色計數(shù)，就是給定標定圖G和顏色數(shù)k,求出正常頂點著色的方式數(shù)。方式數(shù)用Pk(G)表示。(一)、色多項式概念可以證明：Pk(G)是k的多項式，稱為圖G的色多項式。知道圖的色多項式，就可以求出色數(shù)為k時的著色方式數(shù)。由點色數(shù)和色多項式Pk(G)的定義可得：

(1)若，則Pk(G)=0;

(2)若G為空圖，則Pk(G)=kn。

(3)Pk(Kn)=k(k-1)…(k-n+1)。3第三頁，共三十二頁，2022年，8月28日

1、遞推計數(shù)法(二)、色多項式的兩種求法定理1設G為簡單圖，則對任意有：證明：設e=uv。則對G-e的著色方式數(shù)可以分為兩部分：

(1)u與v著不同顏色。此時，等于G的著色方式數(shù)；

(2)u與v著同色。此時，等于G·e的著色方式數(shù)；所以，得：4第四頁，共三十二頁，2022年，8月28日推論：設G是單圖，e=uv是G的一條邊，且d(u)=1,則：證明：因為G是單圖，e=uv,d(u)=1,所以G·e=G-u。另一方面，Pk(G-e)=kPk(G-u)所以，注：對遞推公式的使用分析：5第五頁，共三十二頁，2022年，8月28日

(1)當圖G的邊數(shù)較少時，使用減邊遞推法：

(2)當圖G的邊數(shù)較多時，使用加邊遞推法：例1求出下面各圖的色多項式。G1G3G26第六頁，共三十二頁，2022年，8月28日

(1)G1也可由推論：G17第七頁，共三十二頁，2022年，8月28日

(2)G28第八頁，共三十二頁，2022年，8月28日

(3)G3——9第九頁，共三十二頁，2022年，8月28日注：遞推計數(shù)法的計算復雜度是指數(shù)型的。

2、理想子圖計數(shù)法

(1)預備知識定義1：設H是圖G的生成子圖。若H的每個分支均為完全圖，則稱H是G的一個理想子圖。用Nr(G)表示G的具有r個分支的理想子圖的個數(shù)。例2求N4(G),N5(G)。G10第十頁，共三十二頁，2022年，8月28日解：通過觀察枚舉求Nr(G)G

1)N4(G):G11第十一頁，共三十二頁，2022年，8月28日N4(G)=6

2)N5(G):GN5(G)=512第十二頁，共三十二頁，2022年，8月28日

定理2設qr(G)表示將單圖G的頂點集合V劃分為r個不同色組的色劃分個數(shù)，則：

證明：一方面，設G的任一r色劃分為：｛V1,V2,…,Vr｝。于是，對于1≦i≦r,是的完全子圖。

因為Vi∩Vj=Φ(i≠j),所以是的理想子圖。

這說明：G的任一r色劃分必然對應的一個理想子圖。容易知道，這種對應是唯一的；13第十三頁，共三十二頁，2022年，8月28日

另一方面，對于的任一具有r個分支的理想子圖，顯然它唯一對應G中一個r色組。

所以，我們得到：

上面定理2實際上給我們提供了色多項式的求法：用k種顏色對單圖G正常著色，可以這樣來計算著色方式數(shù)：色組為1的方式數(shù)+色組為2的方式數(shù)+…+色則為n的方式數(shù)。即有如下計數(shù)公式：

(2)色多項式求法----理想子圖法14第十四頁，共三十二頁，2022年，8月28日

定義2：設G是單圖，令Ni(G)=ri,[k]i=xi。稱

為圖G的伴隨多項式。

于是，求Pk(G)就是要求出的伴隨多項式。

用理想子圖法求Pk(G)的步驟如下：(1)畫出G的補圖(2)求出關于補圖的(3)寫出關于補圖的伴隨多項式15第十五頁，共三十二頁，2022年，8月28日(4)將代入伴隨多項式中得到Pk(G)。

例3求下圖G的色多項式Pk(G)。G

解：(1)G的補圖為：(2)求出關于補圖的伴隨多項式系數(shù)ri(1≦i≦6)16第十六頁，共三十二頁，2022年，8月28日1)r=62)r=53)r=417第十七頁，共三十二頁，2022年，8月28日4)r=35)r=26)r=1(3)寫出關于補圖的伴隨多項式18第十八頁，共三十二頁，2022年，8月28日(4)將代入伴隨多項式中得到Pk(G)。

可以作如下計算：

由此可以斷定：。最優(yōu)著色方式數(shù)有12種。19第十九頁，共三十二頁，2022年，8月28日

使用理想子圖法求色多項式，還可以通過如下定理進行改進。

定理3若G有t個分支H1,H2,…Ht,且Hi的伴隨多項式為h(Hi,x),i=1,2,…,t,則：

該定理說明，在求的伴隨多項式時，可以分別求出它的每個分支的伴隨多項式，然后將它們作乘積。

例4求下圖G的色多項式Pk(G)。20第二十頁，共三十二頁，2022年，8月28日

解:(1)畫出G的補圖G2154351432H3H2H1

(2)求出補圖中個分支的伴隨多項式

(3)求出補圖的伴隨多項式21第二十一頁，共三十二頁，2022年，8月28日

(4)求出G的色多項式

注：在例4中，k=3時，P3(G)=6,由此可以推出G的點色數(shù)為3.

求出了色多項式，可以由多項式推出點色數(shù)。但是，求色多項式的計算量是很大的。遞推方法是指數(shù)類計算量，而理想子圖法中主要計算量是找出所有理想子圖，這也不是多項式時間算法。22第二十二頁，共三十二頁，2022年，8月28日

下面，我們對定理3作證明。

定理3若G有t個分支H1,H2,…Ht,且Hi的伴隨多項式為h(Hi,x),i=1,2,…,t,則：

分析：由伴隨多項式定義：

所以，我們只需要證明等于的k次項系數(shù)即可。

設23第二十三頁，共三十二頁，2022年，8月28日

一方面：

該多項式中xk的系數(shù)rk為：

另一方面：設Mj是Hj中具有ij個分支的Hj的理想子圖。當i1+i2+…+it=k時，M1∪M2∪…∪Mt必是G的具有k個分支的理想子圖。24第二十四頁，共三十二頁，2022年，8月28日

在給定的i1,i2,…,it且i1+i2+…+it=k情形下，對應的G的具有k個分支的理想子圖個數(shù)為：

所以，G的具有k個分支的理想子圖的總個數(shù)為：

所以得：25第二十五頁，共三十二頁，2022年，8月28日(三)、色多項式的性質

定理4n階單圖G的色多項式Pk(G)是常數(shù)項為0的首1整系數(shù)多項式，且各項系數(shù)符號正負相間。

證明：對G的邊數(shù)進行數(shù)學歸納證明。

當m=0時，Pk(G)=kn,命題結論成立。

設m=k時，命題結論成立。

考慮m=k+1的單圖G。(m≥1)

取單圖G的任意一條邊e,考慮G-e與G·e。

對于G-e來說，由歸納假設，可設其色多項式為：26第二十六頁，共三十二頁，2022年，8月28日同樣，可設G·e的色多項式為：由色多項式遞推公式得：注:(1)定理的逆不成立!27第二十七頁，共三十二頁，2022年，8月28日例5(1)用遞推公式證明：設G=(n,m)是單圖，則在其色多項式Pk(G)中kn-1的系數(shù)是-m。

(2)不存在以k4-3k3+3k2為其色多項式的單圖。證明：(1)采用對邊數(shù)進行數(shù)學歸納證明。當m=1時，Pk(G)=Pk(G-e)-Pk(G·e)=kn-kn-1.顯然，結論成立。設命題對少于m條邊的n階單圖成立?？紤]單圖G=(n,m).由遞推公式：Pk(G)=Pk(G-e)-Pk(G·e).由假設可令:Pk(G-e)=kn+a1kn-1+…+an-1kn-1

，且a1=-m+1;Pk(G·e)=kn-1+b1kn-2+…+bn-2kn-2

，且b1=-m+1;28第二十八頁，共三十二頁，2022年，8月28日所以：Pk(G)=kn+(a1+1)kn-1+(a2+b1)kn-2+…+bn-2kn-2所以，a1+1=-m。

(2)不存在以k4-3k3+3k2為其色多項式的單圖。事實上，一方面，如果它是某單圖的色多項式，則由多項式本身可以得到點色數(shù)為1；另一方面，由(1)和多項式本身，如果多項式是某單圖的色多項式，則m(G)=3,于是點色數(shù)至少為2.上面推導導出了矛盾！注:(2)同構的圖具有相同的色多項式，但逆不真。29第二十九頁，共三十二頁，2022年，8月28日例6求證：下面圖G1與G2非同構但具有相同的色多項式。G1G2u1v1證明：因為G1和G2中分別有一個唯一的4度頂點：u1與v1。但是它們鄰點狀況不相同:u1有4個2度鄰點。而v1只有兩個2度鄰點。所以G1與G2