图论第二十六节课

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本次课主要内容本次课主要内容(一一)、色多项式概念、色多项式概念(二二)、色多项式的两种求法、色多项式的两种求法着色的计数与色多项式着色的计数与色多项式(三三)、色多项式的性质、色多项式的性质 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 所谓色计数，就是给定标定图所谓色计数，就是给定标定图G和颜色数和颜色数k,求出正常求出正常顶点着色的方式数。方式数用顶点着色的方式数。方式数用Pk(G)表示。表示。( )min( )

2、1kGk P G(一一)、色多项式概念、色多项式概念 可以证明：可以证明：Pk(G)是是k的多项式，称为图的多项式，称为图G的色多项式。的色多项式。知道图的色多项式，就可以求出色数为知道图的色多项式，就可以求出色数为k时的着色方式数。时的着色方式数。 由点色数由点色数 和色多项式和色多项式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、递推计数法、递推计数法(二二)、色多项式的两种求法、色多项式的两种求法 定理定理1 设设G为简单图，则对任意为简单图，则对任意 有：有：( )eE G( )()()kkkP GP G eP G e 证明：设证明：设e=uv。则对。则对G-e的着色方式数可以分为两部分：的着色方式数可以分为两部分： (1) u与与v着不同颜色。此时，等于着不同颜色。此时，等于G的着色方式数；的着色方式数； (2) u与与v着同色。此时，等于着同色。此时，等于Ge 的着色方式数；的着色方式数； 所以，得：所以，得：( )()()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 推论：设推论：设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的边数较少时，使用减边递推法：的边数较少时，使用减边递推法：( )()()kkkP GP G eP G e (2) 当图当图G的边数较多时，使用加边递推法：的边数较多时，使用加边递推法：()( )()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 注：递推计数法的计算复杂度是指数型的。注：递推计数法的计算复杂度是指数型的。 2、理

7、想子图计数法、理想子图计数法 (1) 预备知识预备知识 定义定义1：设：设H是图是图G的生成子图。若的生成子图。若H的每个分支均为的每个分支均为完全图，则称完全图，则称H是是G的一个理想子图。用的一个理想子图。用Nr(G)表示表示G的具的具有有r个分支的理想子图的个数。个分支的理想子图的个数。 例例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 设设qr(G)表示将单图表示将单图G的顶点集合的顶点集合V划分为划分为r个不个不同色组的色划分个数，则：同色组的色划分个数，则：( )( ).(1)rrq GN GrV 证明：一方面，设证明：一方面，设G的任一的任一r色划分为：色划分为：V1,V2,Vr。于是，对于于是，对于1ir, ir, 是是 的完全子图。的完全子图。iG VG 因为因为ViVj=(ij),(ij),所以所以

9、 是是 的理想子图。的理想子图。1riiG VG 这说明：这说明：G的任一的任一r色划分必然对应色划分必然对应 的一个理想子图。的一个理想子图。容易知道，这种对应是唯一的；容易知道，这种对应是唯一的；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个分支的理想子图，个分支的理想子图，显然它唯一对应显然它唯一对应G中一个中一个r色组。色组。 所以，我们得到：所以，我们得到： 上面定理上面定理2实际上给我们提供了色多项式的求法：用实际上给我们提供了色多项式的求法：用k种颜种颜色

10、对单图色对单图G正常着色，可以这样来计算着色方式数：色组为正常着色，可以这样来计算着色方式数：色组为1的方式数的方式数+色组为色组为2的方式数的方式数+色则为色则为n的方式数。即有如下的方式数。即有如下计数公式：计数公式：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 ：设：设G是单图，令是单图，令Ni(G)=ri , ki=x

11、i 。称。称1(,)niiih G xr x 为图为图G的伴随多项式。的伴随多项式。 于是，求于是，求Pk(G)就是要求出就是要求出 的伴随多项式。的伴随多项式。G 用理想子图法求用理想子图法求Pk(G)的步骤如下：的步骤如下： (1) 画出画出G的补图的补图G (2) 求出关于补图的求出关于补图的(), (1)iirNGin (3) 写出关于补图的伴随多项式写出关于补图的伴随多项式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) 求出关于补图的伴随多项式系数求出关于补图的伴随多项式系数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) 写出关于补图的伴随多项式写出关于补图的伴随多项式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、此可以断定： 。最优着色方式数有。最优着色方式数有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的点的点色数为色数为3. 求出了色多项式，可以由多项式推出点色数。但是，求出了色多项式，可以由多项式推出点色数。但是，求色多项式的计算量是很大的。递推方法是指数类计算求色多项式的计算量是很大的。递推方法是指数类计算量，而理想子图法中主要计算量是找出所有理想子图，量，而理想子图法中主要计算量是找出所有理想

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次项系数即可。次项系数即可。1(,)()nkkkh G xNG x()kNG1(,)tiih

18、 Hx 设设()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 的系数的系数rk为：为：121212ttkiitiiiikra aa 另一方面：设另一方面：设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情形下，对应的情形下，对应的G的的具有具有k个分支的理想子图个数为：个分支的理想子图个数为：1212()()()tiiitNHNHNH 所以，所以，G的具有的具有k个分支的理想子图的总个数为：个分支的理想子图的总个数为：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(三三)、色多项式的性质、色多项式的性质 定理定理4 n阶单图阶单图G的色多项式的色多项式Pk(G)是常数项为是常数项为0的首的首1整系数多项式，且各项系数符号正负相间。整系数多项式，且各项系数符号正负相间。 证明：对证明：对G的边数进行数学归纳证明。的边数进行数学归纳证明。 当当m=0时，时，Pk(G)=kn, 命题结论成立。命题结论成立。 设设m=k时，命题结论成立。时，命题结论成立。 考虑考虑m=k+1的单图的单图G。(m1) 取单图取单图G的任意一条边的任意一条边e, 考虑考虑G-e与与Ge。 对于对于G-e来说，由归纳假设，可设

21、其色多项式为：来说，由归纳假设，可设其色多项式为： 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 同样，可设同样，可设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) 用递推公式证明：设用递推公式证明：设G=(n ,m)是单图，则在其是单图，则在其色多项式色多项式Pk(G)中中kn-1的系数是的系数是-m。 (2) 不存在以不存在以k4-3k3+3k2为其色多项式的单图。为其色多项式的单图。 证明：证明： (1) 采用对边数进行数学归纳证明。采用对边数进行数学归纳证明。 当当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 ，且，且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