圖論第二十六節(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)容(一一)、色多項(xiàng)式概念、色多項(xiàng)式概念(二二)、色多項(xiàng)式的兩種求法、色多項(xiàng)式的兩種求法著色的計(jì)數(shù)與色多項(xiàng)式著色的計(jì)數(shù)與色多項(xiàng)式(三三)、色多項(xiàng)式的性質(zhì)、色多項(xiàng)式的性質(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 所謂色計(jì)數(shù)，就是給定標(biāo)定圖所謂色計(jì)數(shù)，就是給定標(biāo)定圖G和顏色數(shù)和顏色數(shù)k,求出正常求出正常頂點(diǎn)著色的方式數(shù)。方式數(shù)用頂點(diǎn)著色的方式數(shù)。方式數(shù)用Pk(G)表示。表示。( )min( )

2、1kGk P G(一一)、色多項(xiàng)式概念、色多項(xiàng)式概念 可以證明：可以證明：Pk(G)是是k的多項(xiàng)式，稱(chēng)為圖的多項(xiàng)式，稱(chēng)為圖G的色多項(xiàng)式。的色多項(xiàng)式。知道圖的色多項(xiàng)式，就可以求出色數(shù)為知道圖的色多項(xiàng)式，就可以求出色數(shù)為k時(shí)的著色方式數(shù)。時(shí)的著色方式數(shù)。 由點(diǎn)色數(shù)由點(diǎn)色數(shù) 和色多項(xiàng)式和色多項(xiàng)式Pk(G)的定義可得：的定義可得：( )G (1) 若若 ，則，則Pk(G)=0 ;( )kG (2) 若若G為空?qǐng)D，則為空?qǐng)D，則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、遞推計(jì)數(shù)法、遞推計(jì)數(shù)法(二二)、色多項(xiàng)式的兩種求法、色多項(xiàng)式的兩種求法 定理定理1 設(shè)設(shè)G為簡(jiǎn)單圖，則對(duì)任意為簡(jiǎn)單圖，則對(duì)任意 有：有：( )eE G( )()()kkkP GP G eP G e 證明：設(shè)證明：設(shè)e=uv。則對(duì)。則對(duì)G-e的著色方式數(shù)可以分為兩部分：的著色方式數(shù)可以分為兩部分： (1) u與與v著不同顏色。此時(shí)，等于著不同顏色。此時(shí)，等于G的著色方式數(shù)；的著色方式數(shù)； (2) u與與v著同色。此時(shí)，等于著同色。此時(shí)，等于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,則：則： 證明：因?yàn)樽C明：因?yàn)镚是單圖，是單圖，e=uv, d(u)=1,所以所以Ge = G-u。 另一方面，另一方面，Pk(G-e)=kPk(G-u) 所以，所以， 注：對(duì)遞推公式的使用分析：注：對(duì)遞推公式的使用分析：( )()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) 當(dāng)圖當(dāng)圖G的邊數(shù)較少時(shí)，使用減邊遞推法：的邊數(shù)較少時(shí)，使用減邊遞推法：( )()()kkkP GP G eP G e (2) 當(dāng)圖當(dāng)圖G的邊數(shù)較多時(shí)，使用加邊遞推法：的邊數(shù)較多時(shí)，使用加邊遞推法：()( )()kkkP G eP GP G e 例例1 求出下面各圖的色多項(xiàng)式。求出下面各圖的色多項(xiàng)式。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 注：遞推計(jì)數(shù)法的計(jì)算復(fù)雜度是指數(shù)型的。注：遞推計(jì)數(shù)法的計(jì)算復(fù)雜度是指數(shù)型的。 2、理

7、想子圖計(jì)數(shù)法、理想子圖計(jì)數(shù)法 (1) 預(yù)備知識(shí)預(yù)備知識(shí) 定義定義1：設(shè)：設(shè)H是圖是圖G的生成子圖。若的生成子圖。若H的每個(gè)分支均為的每個(gè)分支均為完全圖，則稱(chēng)完全圖，則稱(chēng)H是是G的一個(gè)理想子圖。用的一個(gè)理想子圖。用Nr(G)表示表示G的具的具有有r個(gè)分支的理想子圖的個(gè)數(shù)。個(gè)分支的理想子圖的個(gè)數(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 解：通過(guò)觀(guān)察枚舉求解：通過(guò)觀(guān)察枚舉求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的頂點(diǎn)集合的頂點(diǎn)集合V劃分為劃分為r個(gè)不個(gè)不同色組的色劃分個(gè)數(shù)，則：同色組的色劃分個(gè)數(shù)，則：( )( ).(1)rrq GN GrV 證明：一方面，設(shè)證明：一方面，設(shè)G的任一的任一r色劃分為：色劃分為：V1,V2,Vr。于是，對(duì)于于是，對(duì)于1ir, ir, 是是 的完全子圖。的完全子圖。iG VG 因?yàn)橐驗(yàn)閂iVj=(ij),(ij),所以所以

9、 是是 的理想子圖。的理想子圖。1riiG VG 這說(shuō)明：這說(shuō)明：G的任一的任一r色劃分必然對(duì)應(yīng)色劃分必然對(duì)應(yīng) 的一個(gè)理想子圖。的一個(gè)理想子圖。容易知道，這種對(duì)應(yīng)是唯一的；容易知道，這種對(duì)應(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 另一方面，對(duì)于另一方面，對(duì)于 的任一具有的任一具有r個(gè)分支的理想子圖，個(gè)分支的理想子圖，顯然它唯一對(duì)應(yīng)顯然它唯一對(duì)應(yīng)G中一個(gè)中一個(gè)r色組。色組。 所以，我們得到：所以，我們得到： 上面定理上面定理2實(shí)際上給我們提供了色多項(xiàng)式的求法：用實(shí)際上給我們提供了色多項(xiàng)式的求法：用k種顏種顏色

10、對(duì)單圖色對(duì)單圖G正常著色，可以這樣來(lái)計(jì)算著色方式數(shù)：色組為正常著色，可以這樣來(lái)計(jì)算著色方式數(shù)：色組為1的方式數(shù)的方式數(shù)+色組為色組為2的方式數(shù)的方式數(shù)+色則為色則為n的方式數(shù)。即有如下的方式數(shù)。即有如下計(jì)數(shù)公式：計(jì)數(shù)公式：G( )( ).(1)rrq GN GrV 1( )( ) , (1)(2).(1)nkiiiiP GN G kkk kkki 其中， (2) 色多項(xiàng)式求法色多項(xiàng)式求法-理想子圖法理想子圖法 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 。稱(chēng)。稱(chēng)1(,)niiih G xr x 為圖為圖G的伴隨多項(xiàng)式。的伴隨多項(xiàng)式。 于是，求于是，求Pk(G)就是要求出就是要求出 的伴隨多項(xiàng)式。的伴隨多項(xiàng)式。G 用理想子圖法求用理想子圖法求Pk(G)的步驟如下：的步驟如下： (1) 畫(huà)出畫(huà)出G的補(bǔ)圖的補(bǔ)圖G (2) 求出關(guān)于補(bǔ)圖的求出關(guān)于補(bǔ)圖的(), (1)iirNGin (3) 寫(xiě)出關(guān)于補(bǔ)圖的伴隨多項(xiàng)式寫(xiě)出關(guān)于補(bǔ)圖的伴隨多項(xiàng)式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) 將將 代入伴隨多項(xiàng)式中得到代入伴隨多項(xiàng)式中得到Pk(G)。

12、 iixk 例例3 求下圖求下圖G的色多項(xiàng)式的色多項(xiàng)式Pk(G)。G 解：解：(1) G的補(bǔ)圖為：的補(bǔ)圖為：G (2) 求出關(guān)于補(bǔ)圖的伴隨多項(xiàng)式系數(shù)求出關(guān)于補(bǔ)圖的伴隨多項(xiàng)式系數(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) 寫(xiě)出關(guān)于補(bǔ)圖的伴隨多項(xiàng)式寫(xiě)出關(guān)于補(bǔ)圖的伴隨多項(xiàng)式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) 將將 代入伴隨多項(xiàng)式中得到代入伴隨多項(xiàng)式中得到Pk(G)。 iixk2 (1)(2)6 (1)(2)(3)5 (1)(2)(3)(4)(1)(2)(3)(4)(5)k kkk kkkk kkkkk kkkkk 可以作如下計(jì)算：可以作如下計(jì)算：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 使用理想子圖法求色多項(xiàng)式，還可以通過(guò)如下定理進(jìn)使用理想子圖法求色多項(xiàng)式，還可以通過(guò)如下定理進(jìn)行改進(jìn)。行改進(jìn)。 定理定理3 若若G有有t個(gè)分支個(gè)分支H1,H2,Ht,且且Hi的伴隨多項(xiàng)式為的伴隨多項(xiàng)式為h (Hi, x), i=1,2,t, 則：則：1(,)(,)tiih G xh Hx 該定理說(shuō)明，在求該定理說(shuō)明，在求 的伴隨多項(xiàng)式時(shí)，可以分別求的伴隨多項(xiàng)式時(shí)，可以分別求出它的每個(gè)分支的伴隨多項(xiàng)式，然后將它們作

15、乘積。出它的每個(gè)分支的伴隨多項(xiàng)式，然后將它們作乘積。G 例例4 求下圖求下圖G的色多項(xiàng)式的色多項(xiàng)式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) 畫(huà)出畫(huà)出G的補(bǔ)圖的補(bǔ)圖G21543G51432H3H2H1 (2) 求出補(bǔ)圖中個(gè)分支的伴隨多項(xiàng)式求出補(bǔ)圖中個(gè)分支的伴隨多項(xiàng)式1(,)h Hxx22(,)h Hxxx23(,)h Hxxx (3) 求出補(bǔ)圖的伴隨多項(xiàng)式求出補(bǔ)圖的伴隨多項(xiàng)式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的色多項(xiàng)式的色多項(xiàng)式()(1)(2)2 (1)(2)(3)(1)(2)(3)(4)kPGk kkk kkkk kkkk2(1)(2)(57)k kkkk 注：在例注：在例4中，中，k=3時(shí)，時(shí)，P3(G)=6, 由此可以推出由此可以推出G的點(diǎn)的點(diǎn)色數(shù)為色數(shù)為3. 求出了色多項(xiàng)式，可以由多項(xiàng)式推出點(diǎn)色數(shù)。但是，求出了色多項(xiàng)式，可以由多項(xiàng)式推出點(diǎn)色數(shù)。但是，求色多項(xiàng)式的計(jì)算量是很大的。遞推方法是指數(shù)類(lèi)計(jì)算求色多項(xiàng)式的計(jì)算量是很大的。遞推方法是指數(shù)類(lèi)計(jì)算量，而理想子圖法中主要計(jì)算量是找出所有理想子圖，量，而理想子圖法中主要計(jì)算量是找出所有理想

17、子圖，這也不是多項(xiàng)式時(shí)間算法。這也不是多項(xiàng)式時(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 22 下面，我們對(duì)定理下面，我們對(duì)定理3作證明。作證明。 定理定理3 若若G有有t個(gè)分支個(gè)分支H1,H2,Ht,且且Hi的伴隨多項(xiàng)式為的伴隨多項(xiàng)式為h (Hi, x), i=1,2,t, 則：則：1(,)(,)tiih G xh Hx 分析：由伴隨多項(xiàng)式定義：分析：由伴隨多項(xiàng)式定義： 所以，我們只需要證明所以，我們只需要證明 等于等于 的的k次項(xiàng)系數(shù)即可。次項(xiàng)系數(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 該多項(xiàng)式中該多項(xiàng)式中 xk 的系數(shù)的系數(shù)rk為：為：121212ttkiitiiiikra aa 另一方面：設(shè)另一方面：設(shè)Mj是是Hj中具有中具有ij個(gè)分支的個(gè)分支的Hj的理想子圖。的理想子圖。當(dāng)當(dāng)i1+i2+it=k時(shí)，時(shí)，M1 M2 Mt必是必是G的具有的具有k個(gè)個(gè)分支的理想子圖。分支的理想子圖。 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情形下，對(duì)應(yīng)的情形下，對(duì)應(yīng)的G的的具有具有k個(gè)分支的理想子圖個(gè)數(shù)為：個(gè)分支的理想子圖個(gè)數(shù)為：1212()()()tiiitNHNHNH 所以，所以，G的具有的具有k個(gè)分支的理想子圖的總個(gè)數(shù)為：個(gè)分支的理想子圖的總個(gè)數(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(三三)、色多項(xiàng)式的性質(zhì)、色多項(xiàng)式的性質(zhì) 定理定理4 n階單圖階單圖G的色多項(xiàng)式的色多項(xiàng)式Pk(G)是常數(shù)項(xiàng)為是常數(shù)項(xiàng)為0的首的首1整系數(shù)多項(xiàng)式，且各項(xiàng)系數(shù)符號(hào)正負(fù)相間。整系數(shù)多項(xiàng)式，且各項(xiàng)系數(shù)符號(hào)正負(fù)相間。 證明：對(duì)證明：對(duì)G的邊數(shù)進(jìn)行數(shù)學(xué)歸納證明。的邊數(shù)進(jìn)行數(shù)學(xué)歸納證明。 當(dāng)當(dāng)m=0時(shí)，時(shí)，Pk(G)=kn, 命題結(jié)論成立。命題結(jié)論成立。 設(shè)設(shè)m=k時(shí)，命題結(jié)論成立。時(shí)，命題結(jié)論成立。 考慮考慮m=k+1的單圖的單圖G。(m1) 取單圖取單圖G的任意一條邊的任意一條邊e, 考慮考慮G-e與與Ge。 對(duì)于對(duì)于G-e來(lái)說(shuō)，由歸納假設(shè)，可設(shè)

21、其色多項(xiàng)式為：來(lái)說(shuō)，由歸納假設(shè)，可設(shè)其色多項(xiàng)式為： 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的色多項(xiàng)式為：的色多項(xiàng)式為：121121().( 1),0nnnnkniPGeka ka kak a 1232122().( 1),0nnnnkniPG ekb kb kak b 由色多項(xiàng)式遞推公式得：由色多項(xiàng)式遞推公式得：()()()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)是單圖，則在其是單圖，則在其色多項(xiàng)式色多項(xiàng)式Pk(G)中中kn-1的系數(shù)是的系數(shù)是-m。 (2) 不存在以不存在以k4-3k3+3k2為其色多項(xiàng)式的單圖。為其色多項(xiàng)式的單圖。 證明：證明： (1) 采用對(duì)邊數(shù)進(jìn)行數(shù)學(xué)歸納證明。采用對(duì)邊數(shù)進(jìn)行數(shù)學(xué)歸納證明。 當(dāng)當(dāng)m=1時(shí)，時(shí)，Pk(G)= Pk(G-e)- Pk(Ge)= kn-kn-1.顯然，結(jié)顯然，結(jié)論成立。論成立。 設(shè)命題對(duì)少于設(shè)命題對(duì)少于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