圖論第二十六節(jié)課

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1本次課主要內(nèi)容本次課主要內(nèi)容(一一)、色多項式概念、色多項式概念(二二)、色多項式的兩種求法、色多項式的兩種求法著色的計數(shù)與色多項式著色的計數(shù)與色多項式(三三)、色多項式的性質(zhì)、色多項式的性質(zhì) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 所謂色計數(shù)，就是給定標定圖所謂色計數(shù)，就是給定標定圖G和顏色數(shù)和顏色數(shù)k,求出正常求出正常頂點著色的方式數(shù)。方式數(shù)用頂點著色的方式數(shù)。方式數(shù)用Pk(G)表示。表示。( )min( )

2、1kGk P G(一一)、色多項式概念、色多項式概念 可以證明：可以證明：Pk(G)是是k的多項式，稱為圖的多項式，稱為圖G的色多項式。的色多項式。知道圖的色多項式，就可以求出色數(shù)為知道圖的色多項式，就可以求出色數(shù)為k時的著色方式數(shù)。時的著色方式數(shù)。 由點色數(shù)由點色數(shù) 和色多項式和色多項式Pk(G)的定義可得：的定義可得：( )G (1) 若若 ，則，則Pk(G)=0 ;( )kG (2) 若若G為空圖，則為空圖，則Pk(G)=kn。 (3) Pk(Kn)=k(k-1)(k-n+1)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n

3、3 1、遞推計數(shù)法、遞推計數(shù)法(二二)、色多項式的兩種求法、色多項式的兩種求法 定理定理1 設(shè)設(shè)G為簡單圖，則對任意為簡單圖，則對任意 有：有：( )eE G( )()()kkkP GP G eP G e 證明：設(shè)證明：設(shè)e=uv。則對。則對G-e的著色方式數(shù)可以分為兩部分：的著色方式數(shù)可以分為兩部分： (1) u與與v著不同顏色。此時，等于著不同顏色。此時，等于G的著色方式數(shù)；的著色方式數(shù)； (2) u與與v著同色。此時，等于著同色。此時，等于Ge 的著色方式數(shù)；的著色方式數(shù)； 所以，得：所以，得：( )()()kkkP GP G eP G e 0.8 1 0.6 0.4 0.2 0 x t

4、 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 推論：設(shè)推論：設(shè)G是單圖，是單圖，e=uv是是G的一條邊，且的一條邊，且d(u)=1,則：則： 證明：因為證明：因為G是單圖，是單圖，e=uv, d(u)=1,所以所以Ge = G-u。 另一方面，另一方面，Pk(G-e)=kPk(G-u) 所以，所以， 注：對遞推公式的使用分析：注：對遞推公式的使用分析：( )()kkP GP G u(k-1)( )()()kkkP GP G eP G e()()kkkP G uP G u()kP G u(k-1) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1

5、 0.5 0 0.5 1 n 5 (1) 當圖當圖G的邊數(shù)較少時，使用減邊遞推法：的邊數(shù)較少時，使用減邊遞推法：( )()()kkkP GP G eP G e (2) 當圖當圖G的邊數(shù)較多時，使用加邊遞推法：的邊數(shù)較多時，使用加邊遞推法：()( )()kkkP G eP GP G e 例例1 求出下面各圖的色多項式。求出下面各圖的色多項式。G1G3G2 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 (1)G1321()(1)(2)(1)2kP Gk kkk kkkk 也可由推論：也可由推論：G12(1)()kkP K322kkk

6、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 (2)G222()(1)(2)(3) 2 (1)(2)(1)(1)(33)kP Gk kkkk kkk kk kkk 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 (3)G3323()(1)(5107)kP Gk kkkk 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 注：遞推計數(shù)法的計算復(fù)雜度是指數(shù)型的。注：遞推計數(shù)法的計算復(fù)雜度是指數(shù)型的。 2、理

7、想子圖計數(shù)法、理想子圖計數(shù)法 (1) 預(yù)備知識預(yù)備知識 定義定義1：設(shè)：設(shè)H是圖是圖G的生成子圖。若的生成子圖。若H的每個分支均為的每個分支均為完全圖，則稱完全圖，則稱H是是G的一個理想子圖。用的一個理想子圖。用Nr(G)表示表示G的具的具有有r個分支的理想子圖的個數(shù)。個分支的理想子圖的個數(shù)。 例例2 求求N4(G), N5(G)。G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 解：通過觀察枚舉求解：通過觀察枚舉求Nr(G)G 1) N4(G):G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

8、1 0.5 0 0.5 1 n 11 N4(G)=6 2) N5(G):G N5(G)=5 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 定理定理2 設(shè)設(shè)qr(G)表示將單圖表示將單圖G的頂點集合的頂點集合V劃分為劃分為r個不個不同色組的色劃分個數(shù)，則：同色組的色劃分個數(shù)，則：( )( ).(1)rrq GN GrV 證明：一方面，設(shè)證明：一方面，設(shè)G的任一的任一r色劃分為：色劃分為：V1,V2,Vr。于是，對于于是，對于1ir, ir, 是是 的完全子圖。的完全子圖。iG VG 因為因為ViVj=(ij),(ij),所以所以

9、 是是 的理想子圖。的理想子圖。1riiG VG 這說明：這說明：G的任一的任一r色劃分必然對應(yīng)色劃分必然對應(yīng) 的一個理想子圖。的一個理想子圖。容易知道，這種對應(yīng)是唯一的；容易知道，這種對應(yīng)是唯一的；G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 另一方面，對于另一方面，對于 的任一具有的任一具有r個分支的理想子圖，個分支的理想子圖，顯然它唯一對應(yīng)顯然它唯一對應(yīng)G中一個中一個r色組。色組。 所以，我們得到：所以，我們得到： 上面定理上面定理2實際上給我們提供了色多項式的求法：用實際上給我們提供了色多項式的求法：用k種顏種顏色

10、對單圖色對單圖G正常著色，可以這樣來計算著色方式數(shù)：色組為正常著色，可以這樣來計算著色方式數(shù)：色組為1的方式數(shù)的方式數(shù)+色組為色組為2的方式數(shù)的方式數(shù)+色則為色則為n的方式數(shù)。即有如下的方式數(shù)。即有如下計數(shù)公式：計數(shù)公式：G( )( ).(1)rrq GN GrV 1( )( ) , (1)(2).(1)nkiiiiP GN G kkk kkki 其中， (2) 色多項式求法色多項式求法-理想子圖法理想子圖法 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 定義定義2 ：設(shè)：設(shè)G是單圖，令是單圖，令Ni(G)=ri , ki=x

11、i 。稱。稱1(,)niiih G xr x 為圖為圖G的伴隨多項式。的伴隨多項式。 于是，求于是，求Pk(G)就是要求出就是要求出 的伴隨多項式。的伴隨多項式。G 用理想子圖法求用理想子圖法求Pk(G)的步驟如下：的步驟如下： (1) 畫出畫出G的補圖的補圖G (2) 求出關(guān)于補圖的求出關(guān)于補圖的(), (1)iirNGin (3) 寫出關(guān)于補圖的伴隨多項式寫出關(guān)于補圖的伴隨多項式1(,)niiih G xr x 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 (4) 將將 代入伴隨多項式中得到代入伴隨多項式中得到Pk(G)。

12、 iixk 例例3 求下圖求下圖G的色多項式的色多項式Pk(G)。G 解：解：(1) G的補圖為：的補圖為：G (2) 求出關(guān)于補圖的伴隨多項式系數(shù)求出關(guān)于補圖的伴隨多項式系數(shù)ri (1i6)i6) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 1) r = 666()1rNGG 2) r = 555()5rNG 3) r =4 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17G 4) r = 344()6rNG 5) r =233()2rNG22()0rNG 6

13、) r =111()0rNG (3) 寫出關(guān)于補圖的伴隨多項式寫出關(guān)于補圖的伴隨多項式1(,)niiih G xr x3456265xxxx 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 183456()2 6 5 kPGkkkk (4) 將將 代入伴隨多項式中得到代入伴隨多項式中得到Pk(G)。 iixk2 (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 由此可以斷定：由

14、此可以斷定： 。最優(yōu)著色方式數(shù)有。最優(yōu)著色方式數(shù)有12種。種。()3G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 使用理想子圖法求色多項式，還可以通過如下定理進使用理想子圖法求色多項式，還可以通過如下定理進行改進。行改進。 定理定理3 若若G有有t個分支個分支H1,H2,Ht,且且Hi的伴隨多項式為的伴隨多項式為h (Hi, x), i=1,2,t, 則：則：1(,)(,)tiih G xh Hx 該定理說明，在求該定理說明，在求 的伴隨多項式時，可以分別求的伴隨多項式時，可以分別求出它的每個分支的伴隨多項式，然后將它們作

15、乘積。出它的每個分支的伴隨多項式，然后將它們作乘積。G 例例4 求下圖求下圖G的色多項式的色多項式Pk(G)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 解解: (1) 畫出畫出G的補圖的補圖G21543G51432H3H2H1 (2) 求出補圖中個分支的伴隨多項式求出補圖中個分支的伴隨多項式1(,)h Hxx22(,)h Hxxx23(,)h Hxxx (3) 求出補圖的伴隨多項式求出補圖的伴隨多項式22345(,)()2h G xx xxxxx 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

16、 1 0.5 0 0.5 1 n 21 (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ù)為色數(shù)為3. 求出了色多項式，可以由多項式推出點色數(shù)。但是，求出了色多項式，可以由多項式推出點色數(shù)。但是，求色多項式的計算量是很大的。遞推方法是指數(shù)類計算求色多項式的計算量是很大的。遞推方法是指數(shù)類計算量，而理想子圖法中主要計算量是找出所有理想子圖，量，而理想子圖法中主要計算量是找出所有理想

17、子圖，這也不是多項式時間算法。這也不是多項式時間算法。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 下面，我們對定理下面，我們對定理3作證明。作證明。 定理定理3 若若G有有t個分支個分支H1,H2,Ht,且且Hi的伴隨多項式為的伴隨多項式為h (Hi, x), i=1,2,t, 則：則：1(,)(,)tiih G xh Hx 分析：由伴隨多項式定義：分析：由伴隨多項式定義： 所以，我們只需要證明所以，我們只需要證明 等于等于 的的k次項系數(shù)即可。次項系數(shù)即可。1(,)()nkkkh G xNG x()kNG1(,)tiih

18、 Hx 設(shè)設(shè)()V Gn()iiVHn1(,),1, 2,.,injiijjh Hxa xjt 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 一方面：一方面：1tijnn1(,)tiih Hx11intjijjia x 該多項式中該多項式中 xk 的系數(shù)的系數(shù)rk為：為：121212ttkiitiiiikra aa 另一方面：設(shè)另一方面：設(shè)Mj是是Hj中具有中具有ij個分支的個分支的Hj的理想子圖。的理想子圖。當當i1+i2+it=k時，時，M1 M2 Mt必是必是G的具有的具有k個個分支的理想子圖。分支的理想子圖。 0.8

19、1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24 在給定的在給定的i1,i2,it且且i1+i2+it=k情形下，對應(yīng)的情形下，對應(yīng)的G的的具有具有k個分支的理想子圖個數(shù)為：個分支的理想子圖個數(shù)為：1212()()()tiiitNHNHNH 所以，所以，G的具有的具有k個分支的理想子圖的總個數(shù)為：個分支的理想子圖的總個數(shù)為：121212()()()()ttkiiitiiikNGNHNHNH121212ttiitiiiikaaa 所以得：所以得：1(,)(,)tiih G xh Hx 0.8 1 0.6 0.4 0.2 0 x t 0 0.

20、5 1 1.5 2 1 0.5 0 0.5 1 n 25(三三)、色多項式的性質(zhì)、色多項式的性質(zhì) 定理定理4 n階單圖階單圖G的色多項式的色多項式Pk(G)是常數(shù)項為是常數(shù)項為0的首的首1整系數(shù)多項式，且各項系數(shù)符號正負相間。整系數(shù)多項式，且各項系數(shù)符號正負相間。 證明：對證明：對G的邊數(shù)進行數(shù)學(xué)歸納證明。的邊數(shù)進行數(shù)學(xué)歸納證明。 當當m=0時，時，Pk(G)=kn, 命題結(jié)論成立。命題結(jié)論成立。 設(shè)設(shè)m=k時，命題結(jié)論成立。時，命題結(jié)論成立。 考慮考慮m=k+1的單圖的單圖G。(m1) 取單圖取單圖G的任意一條邊的任意一條邊e, 考慮考慮G-e與與Ge。 對于對于G-e來說，由歸納假設(shè)，可設(shè)

21、其色多項式為：來說，由歸納假設(shè)，可設(shè)其色多項式為： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26 同樣，可設(shè)同樣，可設(shè)Ge的色多項式為：的色多項式為：121121().( 1),0nnnnkniPGeka ka kak a 1232122().( 1),0nnnnkniPG ekb kb kak b 由色多項式遞推公式得：由色多項式遞推公式得：()()()kkkPGPGePG e12112212(1)().( 1)()nnnnnnkakabkabk 注注: (1) 定理的逆不成立定理的逆不成立! 0.8 1 0.6 0.4 0

22、.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27 例例5 (1) 用遞推公式證明：設(shè)用遞推公式證明：設(shè)G=(n ,m)是單圖，則在其是單圖，則在其色多項式色多項式Pk(G)中中kn-1的系數(shù)是的系數(shù)是-m。 (2) 不存在以不存在以k4-3k3+3k2為其色多項式的單圖。為其色多項式的單圖。 證明：證明： (1) 采用對邊數(shù)進行數(shù)學(xué)歸納證明。采用對邊數(shù)進行數(shù)學(xué)歸納證明。 當當m=1時，時，Pk(G)= Pk(G-e)- Pk(Ge)= kn-kn-1.顯然，結(jié)顯然，結(jié)論成立。論成立。 設(shè)命題對少于設(shè)命題對少于m條邊的條邊的n階單圖成立?？紤]單圖階單圖成立。考慮單圖G=(n ,m). 由遞推公式：由遞推公式： Pk(G)= Pk(G-e)- Pk(Ge). 由假設(shè)可令由假設(shè)可令: Pk(G-e)=kn+a1kn-1+an-1kn-1 ，且，且a1=-m+1; Pk(Ge)=kn-1+b1kn-2+bn-2kn-2 ，且，且b1=-m+1; 0.8 1 0.6 0.4 0.2 0 x t 0