圖論著色的計數(shù)與色多項式PPT教案

1、圖論著色的計數(shù)與色多項式圖論著色的計數(shù)與色多項式本次課主要內(nèi)容(一)、色多項式概念(二)、色多項式的兩種求法著色的計數(shù)與色多項式(三)、色多項式的性質第1頁/共32頁 所謂色計數(shù)，就是給定標定圖G和顏色數(shù)k,求出正常頂點著色的方式數(shù)。方式數(shù)用Pk(G)表示。( )min( )1kGk P G(一)、色多項式概念 可以證明：Pk(G)是k的多項式，稱為圖G的色多項式。知道圖的色多項式，就可以求出色數(shù)為k時的著色方式數(shù)。 由點色數(shù) 和色多項式Pk(G)的定義可得：( )G (1) 若 ，則Pk(G)=0 ;( )kG (2) 若G為空圖，則Pk(G)=kn。 (3) Pk(Kn)=k(k-1)(k

2、-n+1)。第2頁/共32頁 1、遞推計數(shù)法(二)、色多項式的兩種求法 定理1 設G為簡單圖，則對任意 有：( )eE G( )()()kkkP GP G eP G e 證明：設e=uv。則對G-e的著色方式數(shù)可以分為兩部分： (1) u與v著不同顏色。此時，等于G的著色方式數(shù)； (2) u與v著同色。此時，等于Ge 的著色方式數(shù)； 所以，得：( )()()kkkP GP G eP G e第3頁/共32頁 推論：設G是單圖，e=uv是G的一條邊，且d(u)=1,則： 證明：因為G是單圖，e=uv, d(u)=1,所以Ge = G-u。 另一方面，Pk(G-e)=kPk(G-u) 所以， 注：對

3、遞推公式的使用分析：( )()kkP GP G u(k-1)( )()()kkkP GP G eP G e()()kkkP G uP G u()kP G u(k-1)第4頁/共32頁 (1) 當圖G的邊數(shù)較少時，使用減邊遞推法：( )()()kkkP GP G eP G e (2) 當圖G的邊數(shù)較多時，使用加邊遞推法：()( )()kkkP G eP GP G e 例1 求出下面各圖的色多項式。G1G3G2第5頁/共32頁 (1)G1321()(1)(2)(1)2kP Gk kkk kkkk 也可由推論：G12(1)()kkP K322kkk第6頁/共32頁 (2)G222()(1)(2)(3

4、) 2 (1)(2)(1)(1)(33)kP Gk kkkk kkk kk kkk第7頁/共32頁 (3)G3323()(1)(5107)kP Gk kkkk第8頁/共32頁 注：遞推計數(shù)法的計算復雜度是指數(shù)型的。 2、理想子圖計數(shù)法 (1) 預備知識 定義1：設H是圖G的生成子圖。若H的每個分支均為完全圖，則稱H是G的一個理想子圖。用Nr(G)表示G的具有r個分支的理想子圖的個數(shù)。 例2 求N4(G), N5(G)。G第9頁/共32頁 解：通過觀察枚舉求Nr(G)G 1) N4(G):G第10頁/共32頁 N4(G)=6 2) N5(G):G N5(G)=5第11頁/共32頁 定理2 設qr

5、(G)表示將單圖G的頂點集合V劃分為r個不同色組的色劃分個數(shù)，則：( )( ).(1)rrq GN GrV 證明：一方面，設G的任一r色劃分為：V1,V2,Vr。于是，對于1ir, 是 的完全子圖。iG VG 因為ViVj=(ij),所以 是 的理想子圖。1riiG VG 這說明：G的任一r色劃分必然對應 的一個理想子圖。容易知道，這種對應是唯一的；G第12頁/共32頁 另一方面，對于 的任一具有r個分支的理想子圖，顯然它唯一對應G中一個r色組。 所以，我們得到： 上面定理2實際上給我們提供了色多項式的求法：用k種顏色對單圖G正常著色，可以這樣來計算著色方式數(shù)：色組為1的方式數(shù)+色組為2的方式

6、數(shù)+色則為n的方式數(shù)。即有如下計數(shù)公式：G( )( ).(1)rrq GN GrV 1( )( ) , (1)(2).(1)nkiiiiP GN G kkk kkki 其中， (2) 色多項式求法-理想子圖法第13頁/共32頁 定義2 ：設G是單圖，令Ni(G)=ri , ki=xi 。稱1(,)niiih G xr x 為圖G的伴隨多項式。 于是，求Pk(G)就是要求出 的伴隨多項式。G 用理想子圖法求Pk(G)的步驟如下： (1) 畫出G的補圖G (2) 求出關于補圖的(), (1)iirNGin (3) 寫出關于補圖的伴隨多項式1(,)niiih G xr x第14頁/共32頁 (4)

7、將 代入伴隨多項式中得到Pk(G)。 iixk 例3 求下圖G的色多項式Pk(G)。G 解：(1) G的補圖為：G (2) 求出關于補圖的伴隨多項式系數(shù)ri (1i6)第15頁/共32頁 1) r = 666()1rNGG 2) r = 555()5rNG 3) r =4第16頁/共32頁G 4) r = 344()6rNG 5) r =233()2rNG22()0rNG 6) r =111()0rNG (3) 寫出關于補圖的伴隨多項式1(,)niiih G xr x3456265xxxx第17頁/共32頁3456()2 6 5 kPGkkkk (4) 將 代入伴隨多項式中得到Pk(G)。 i

8、ixk2(1)(2)6(1)(2)(3)5 (1)(2)(3)(4)(1)(2)(3)(4)(5)k kkk kkkk kkkkk kkkkk 可以作如下計算：12()()0P GPG3()12PG 由此可以斷定： 。最優(yōu)著色方式數(shù)有12種。()3G第18頁/共32頁 使用理想子圖法求色多項式，還可以通過如下定理進行改進。 定理3 若G有t個分支H1,H2,Ht,且Hi的伴隨多項式為h (Hi, x), i=1,2,t, 則：1(,)(,)tiih G xh Hx 該定理說明，在求 的伴隨多項式時，可以分別求出它的每個分支的伴隨多項式，然后將它們作乘積。G 例4 求下圖G的色多項式Pk(G)。

9、第19頁/共32頁 解: (1) 畫出G的補圖G21543G51432H3H2H1 (2) 求出補圖中個分支的伴隨多項式1(,)h Hxx22(,)h Hxxx23(,)h Hxxx (3) 求出補圖的伴隨多項式22345(,)()2h G xx xxxxx第20頁/共32頁 (4) 求出G的色多項式()(1)(2)2(1)(2)(3)(1)(2)(3)(4)kPGk kkk kkkk kkkk2(1)(2)(57)k kkkk 注：在例4中，k=3時，P3(G)=6, 由此可以推出G的點色數(shù)為3. 求出了色多項式，可以由多項式推出點色數(shù)。但是，求色多項式的計算量是很大的。遞推方法是指數(shù)類計算

10、量，而理想子圖法中主要計算量是找出所有理想子圖，這也不是多項式時間算法。第21頁/共32頁 下面，我們對定理3作證明。 定理3 若G有t個分支H1,H2,Ht,且Hi的伴隨多項式為h (Hi, x), i=1,2,t, 則：1(,)(,)tiih G xh Hx 分析：由伴隨多項式定義： 所以，我們只需要證明 等于 的k次項系數(shù)即可。1(,)()nkkkh G xNG x()kNG1(,)tiih Hx 設()V Gn()iiVHn1(,),1, 2,.,injiijjh Hxa xjt第22頁/共32頁 一方面：1tijnn1(,)tiih Hx11intjijjia x 該多項式中 xk

11、的系數(shù)rk為：121212ttkiitiiiikra aa 另一方面：設Mj是Hj中具有ij個分支的Hj的理想子圖。當i1+i2+it=k時，M1 M2 Mt必是G的具有k個分支的理想子圖。第23頁/共32頁 在給定的i1,i2,it且i1+i2+it=k情形下，對應的G的具有k個分支的理想子圖個數(shù)為：1212()()()tiiitNHNHNH 所以，G的具有k個分支的理想子圖的總個數(shù)為：121212()()()()ttkiiitiiikNGNHNHNH121212ttiitiiiikaaa 所以得：1(,)(,)tiih G xh Hx第24頁/共32頁(三)、色多項式的性質 定理4 n階單

12、圖G的色多項式Pk(G)是常數(shù)項為0的首1整系數(shù)多項式，且各項系數(shù)符號正負相間。 證明：對G的邊數(shù)進行數(shù)學歸納證明。 當m=0時，Pk(G)=kn, 命題結論成立。 設m=k時，命題結論成立。 考慮m=k+1的單圖G。(m1) 取單圖G的任意一條邊e, 考慮G-e與Ge。 對于G-e來說，由歸納假設，可設其色多項式為：第25頁/共32頁 同樣，可設Ge的色多項式為：121121().( 1),0nnnnkniPGeka ka kak a 1232122().( 1),0nnnnkniPG ekb kb kak b 由色多項式遞推公式得：()()()kkkPGPGePG e12112212(1)

13、().( 1)()nnnnnnkakabkabk 注: (1) 定理的逆不成立!第26頁/共32頁 例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(Ge)= kn-kn-1.顯然，結論成立。 設命題對少于m條邊的n階單圖成立。考慮單圖G=(n ,m). 由遞推公式： Pk(G)= Pk(G-e)- Pk(Ge). 由假設可令: Pk(G-e)=kn+a1kn-1+an-1kn-1 ，且

14、a1=-m+1; Pk(Ge)=kn-1+b1kn-2+bn-2kn-2 ，且b1=-m+1;第27頁/共32頁 所以： 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) 同構的圖具有相同的色多項式，但逆不真。第28頁/共32頁 例6 求證：下面圖G1與G2非同構但具有相同的色多項式。G1G2u1v1 證明：因為G1