图论27电子科大杨春

0.810.60.40.20xt00.511.5210.500.51n1Email:[e-mail]图论及其应用任课教师：杨春数学科学学院0.810.60.40.20xt00.511.5210.500.51n2本次课主要内容(一)、色多项式概念(二)、色多项式的两种求法着色的计数与色多项式(三)、色多项式的性质0.810.60.40.20xt00.511.5210.500.51n3所谓色计数，就是给定标定图G和颜色数k,求出正常顶点着色的方式数。方式数用Pk(G)表示。()min()1kGkPG(一)、色多项式概念可以证明：Pk(G)是k的多项式，称为图G的色多项式。由点色数和色多项式Pk(G)的定义可得：()G(1)若，则Pk(G)=0;()kG(2)若G为空图，则Pk(G)=kn。(3)Pk(Kn)=k(k-1)…(k-n+1)。0.810.60.40.20xt00.511.5210.500.51n41、递推计数法(二)、色多项式的两种求法定理1设G为简单图，则对任意有：()eEG()()()kkkPGPGePGe证明：设e=uv。则对G-e的着色方式数可以分为两部分：(1)u与v着不同颜色。此时，等于G的着色方式数；(2)u与v着同色。此时，等于G·e的着色方式数；所以，得：()()()kkkPGPGePGe0.810.60.40.20xt00.511.5210.500.51n5推论：设G是单图，e=uv是G的一条边，且d(u)=1,则：证明：因为G是单图，e=uv,d(u)=1,所以G·e=G-u。另一方面，Pk(G-e)=kPk(G-u)所以，注：对递推公式的使用分析：()()kkPGPGu(k-1)()()()kkkPGPGePGe()()kkkPGuPGu()kPGu(k-1)0.810.60.40.20xt00.511.5210.500.51n6(1)当图G的边数较少时，使用减边递推法：()()()kkkPGPGePGe(2)当图G的边数较多时，使用加边递推法：()()()kkkPGePGPGe例1求出下面各图的色多项式。G1G3G20.810.60.40.20xt00.511.5210.500.51n7(1)G1321()(1)(2)(1)2kPGkkkkkkkk也可由推论：G12(1)()kkPK322kkk0.810.60.40.20xt00.511.5210.500.51n8(2)G222()(1)(2)(3)2(1)(2)(1)(1)(33)kPGkkkkkkkkkkkkk0.810.60.40.20xt00.511.5210.500.51n9(3)G3——323()(1)(5107)kPGkkkkk0.810.60.40.20xt00.511.5210.500.51n10注：递推计数法的计算复杂度是指数型的。2、理想子图计数法(1)预备知识定义1：设H是图G的生成子图。若H的每个分支均为完全图，则称H是G的一个理想子图。用Nr(G)表示G的具有r个分支的理想子图的个数。例2求N4(G),N5(G)。G0.810.60.40.20xt00.511.5210.500.51n11解：通过观察枚举求Nr(G)G1)N4(G):G0.810.60.40.20xt00.511.5210.500.51n12N4(G)=62)N5(G):GN5(G)=50.810.60.40.20xt00.511.5210.500.51n13定理2设qr(G)表示将单图G的顶点集合V划分为r个不同色组的色划分个数，则：()().....(1)rrqGNGrV证明：一方面，设G的任一r色划分为：｛V1,V2,…,Vr｝。于是，对于1≦i≦r,是的完全子图。iGVG因为Vi∩Vj=Φ(i≠j),所以是的理想子图。1[]riiGVG这说明：G的任一r色划分必然对应的一个理想子图。容易知道，这种对应是唯一的；G另一方面，对于的任一具有r个分支的理想子图，显然它唯一对应G中一个r色组。G0.810.60.40.20xt00.511.5210.500.51n14所以，我们得到：上面定理2实际上给出了色多项式的求法：用k种颜色对单图G正常着色，可以这样来计算着色方式数：色组为1的方式数+色组为2的方式数+…+色组为n的方式数。即有如下计数公式：()().....(1)rrqGNGrV1()()[],[](1)(2)...(1)nkiiiiPGNGkkkkkki其中，(2)色多项式求法----理想子图法0.810.60.40.20xt00.511.5210.500.51n15定义2：设G是单图，令Ni(G)=ri,[k]i=xi。称1(,)niiihGxrx为图G的伴随多项式。于是，求Pk(G)就转化为求的伴随多项式。G用理想子图法求Pk(G)的步骤如下：(1)画出G的补图G(2)求出关于补图的(),(1)iirNGin(3)写出关于补图的伴随多项式1(,)niiihGxrx0.810.60.40.20xt00.511.5210.500.51n16(4)将代入伴随多项式中得到Pk(G)。[]iixk例3求下图G的色多项式Pk(G)。G解：(1)G的补图为：G(2)求出关于补图的伴随多项式系数ri(1≦i≦6)0.810.60.40.20xt00.511.5210.500.51n171)r=666()1rNGG2)r=555()5rNG3)r=40.810.60.40.20xt00.511.5210.500.51n18G4)r=344()6rNG5)r=233()2rNG22()0rNG6)r=111()0rNG(3)写出关于补图的伴随多项式1(,)niiihGxrx3456265xxxx0.810.60.40.20xt00.511.5210.500.51n193456()2[]6[]5[][]kPGkkkk(4)将代入伴随多项式中得到Pk(G)。[]iixk2(1)(2)6(1)(2)(3)5(1)(2)(3)(4)(1)(2)(3)(4)(5)kkkkkkkkkkkkkkkkkk可以作如下计算：12()()0PGPG3()12PG由此可以断定：。最优着色方式数有12种。()3G0.810.60.40.20xt00.511.5210.500.51n20使用理想子图法求色多项式，还可以通过如下定理进行改进。定理3若G有t个分支H1,H2,…Ht,且Hi的伴随多项式为h(Hi,x),i=1,2,…,t,则：1(,)(,)tiihGxhHx该定理说明，在求的伴随多项式时，可以分别求出它的每个分支的伴随多项式，然后将它们作乘积。G例4求下图G的色多项式Pk(G)。0.810.60.40.20xt00.511.5210.500.51n21解:(1)画出G的补图G21543G51432H3H2H1(2)求出补图中个分支的伴随多项式1(,)hHxx22(,)hHxxx23(,)hHxxx(3)求出补图的伴随多项式22345(,)()2hGxxxxxxx0.810.60.40.20xt00.511.5210.500.51n22(4)求出G的色多项式()(1)(2)2(1)(2)(3)(1)(2)(3)(4)kPGkkkkkkkkkkkk2(1)(2)(57)kkkkk注：在例4中，k=3时，P3(G)=6,由此可以推出G的点色数为3.求出了色多项式，可以由多项式推出点色数。但是，求色多项式的计算量是很大的。递推方法是指数类计算量，而理想子图法中主要计算量是找出所有理想子图，这也不是多项式时间算法。0.810.60.40.20xt00.511.5210.500.51n23下面，我们对定理3作证明。定理3若G有t个分支H1,H2,…Ht,且Hi的伴随多项式为h(Hi,x),i=1,2,…,t,则：1(,)(,)tiihGxhHx分析：由伴随多项式定义：所以，我们只需要证明等于的k次项系数即可。1(,)()nkkkhGxNGx()kNG1(,)tiihHx设()VGn()iiVHn1(,),1,2,...,injiijjhHxaxit0.810.60.40.20xt00.511.5210.500.51n24一方面：1tiinn1(,)tiihHx11intjijjiax该多项式中xk的系数rk为：121212ttkiitiiiikraaa另一方面：设Mj是Hj中具有ij个分支的Hj的理想子图。当i1+i2+…+it=k时，M1∪M2∪…∪Mt必是G的具有k个分支的理想子图。0.810.60.40.20xt00.511.5210.500.51n25在给定的i1,i2,…,it且i1+i2+…+it=k情形下，对应的G的具有k个分支的理想子图个数为：1212()()()tiiitNHNHNH所以，G的具有k个分支的理想子图的总个数为：121212()()()()ttkiiitiiikNGNHNHNH121212ttiitiiiikaaa所以得：1(,)(,)tiihGxhHx0.810.60.40.20xt00.511.5210.500.51n26(三)、色多项式的性质定理4n阶单图G的色多项式Pk(G)是常数项为0的首1整系数多项式，且各项系数符号正负相间。证明：对G的边数进行数学归纳证明。当m=0时，Pk(G)=kn,命题结论成立。设m=k时，命题结论成立。考虑m=k+1的单图G。(m≥1)取单图G的任意一条边e,考虑G-e与G·e。对于G-e来说，由归纳假设，可设其色多项式为：0.810.60.40.20xt00.511.5210.500.51n27同样，可设G·e的色多项式为：121121()...(1),0nnnnkniPGekakakaka1232122()...(1),0nnnnkniPGekbkbkbkb由色多项式递推公式得：()()()kkkPGPGePGe12112212(1)()...(1)()nnnnnnkakabkabk注:(1)定理的逆不成立!0.810.60.40.20xt00.511.5210.500.51n28例5(1)用递推公式证明：设G=(n,m)是单图，则在其色多项式Pk(G)中kn-1的系数是-m。(2)不存在以k4-3k3+3k2为其色多项式的单图。证明：(1)采用对边数进行数学归纳证明。当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;0.810.60.40.20xt00.511.5210.500.51n29所以：Pk(G)=kn+(a1+1)kn-1+(a2+b1)kn-2+…+bn-2kn-2所以，a1+1=-m。(2)不存在以k4-3k3+3k2为其色多项式的单图。事实上，一方面，如果它是某单图的色多项式，则由多项式本身可以得到点色数为1；另一方面，由(1)和多项式本身，如果多项式是某单图的色多项式，则m(G)=3,于是点色数至少为2.上面推导导出了矛盾！注: