图论着色的计数与色多项式.pptx

1 图论及其应用图论及其应用应用数学学院应用数学学院2本次课主要内容本次课主要内容(一一)、色多项式概念、色多项式概念(二二)、色多项式的两种求法、色多项式的两种求法着色的计数与色多项式着色的计数与色多项式(三三)、色多项式的性质、色多项式的性质3 所谓色计数，就是给定标定图所谓色计数，就是给定标定图G和颜色数和颜色数k,求出正常顶求出正常顶点着色的方式数。方式数用点着色的方式数。方式数用Pk(G)表示。表示。(一一)、色多项式概念、色多项式概念 可以证明：可以证明：Pk(G)是是k的多项式，称为图的多项式，称为图G的色多项式。的色多项式。知道图的色多项式，就可以求出色数为知道图的色多项式，就可以求出色数为k时的着色方式数。时的着色方式数。由点色数由点色数 和色多项式和色多项式Pk(G)的定义可得：的定义可得：(1)若若 ，则，则Pk(G)=0;(2)若若G为空图，则为空图，则Pk(G)=kn。(3)Pk(Kn)=k(k-1)(k-n+1)。4 1、递推计数法、递推计数法(二二)、色多项式的两种求法、色多项式的两种求法 定理定理1 设设G为简单图，则对任意为简单图，则对任意 有：有：证明：设证明：设e=uv。则对。则对G-e的着色方式数可以分为两部分：的着色方式数可以分为两部分：(1)u与与v着不同颜色。此时，等于着不同颜色。此时，等于G的着色方式数；的着色方式数；(2)u与与v着同色。此时，等于着同色。此时，等于Ge 的着色方式数；的着色方式数；所以，得：所以，得：5 推论：设推论：设G是单图，是单图，e=uv是是G的一条边，且的一条边，且d(u)=1,则：则：证明：因为证明：因为G是单图，是单图，e=uv,d(u)=1,所以所以Ge=G-u。另一方面，另一方面，Pk(G-e)=kPk(G-u)所以，所以，注：对递推公式的使用分析：注：对递推公式的使用分析：6 (1)当图当图G的边数较少时，使用减边递推法：的边数较少时，使用减边递推法：(2)当图当图G的边数较多时，使用加边递推法：的边数较多时，使用加边递推法：例例1 求出下面各图的色多项式。求出下面各图的色多项式。G1G3G27 (1)G1 也可由推论：也可由推论：G18 (2)G29 (3)G310 注：递推计数法的计算复杂度是指数型的。注：递推计数法的计算复杂度是指数型的。2、理想子图计数法、理想子图计数法 (1)预备知识预备知识 定义定义1：设：设H是图是图G的生成子图。若的生成子图。若H的每个分支均为的每个分支均为完全图，则称完全图，则称H是是G的一个理想子图。用的一个理想子图。用Nr(G)表示表示G的具的具有有r个分支的理想子图的个数。个分支的理想子图的个数。例例2 求求N4(G),N5(G)。G11 解：通过观察枚举求解：通过观察枚举求Nr(G)G 1)N4(G):G12 N4(G)=6 2)N5(G):G N5(G)=513 定理定理2 设设qr(G)表示将单图表示将单图G的顶点集合的顶点集合V划分为划分为r个不个不同色组的色划分个数，则：同色组的色划分个数，则：证明：一方面，设证明：一方面，设G的任一的任一r色划分为：色划分为：V1,V2,Vr。于是，对于于是，对于1ir,ir,是是 的完全子图。的完全子图。因为因为ViVj=(ij),(ij),所以所以 是是 的理想子图。的理想子图。这说明：这说明：G的任一的任一r色划分必然对应色划分必然对应 的一个理想子图。的一个理想子图。容易知道，这种对应是唯一的；容易知道，这种对应是唯一的；14 另一方面，对于另一方面，对于 的任一具有的任一具有r个分支的理想子图，个分支的理想子图，显然它唯一对应显然它唯一对应G中一个中一个r色组。色组。所以，我们得到：所以，我们得到：上面定理上面定理2实际上给我们提供了色多项式的求法：用实际上给我们提供了色多项式的求法：用k种颜种颜色对单图色对单图G正常着色，可以这样来计算着色方式数：色组为正常着色，可以这样来计算着色方式数：色组为1的方式数的方式数+色组为色组为2的方式数的方式数+色则为色则为n的方式数。即有如下的方式数。即有如下计数公式：计数公式：(2)色多项式求法色多项式求法-理想子图法理想子图法15 定义定义2：设：设G是单图，令是单图，令Ni(G)=ri,ki=xi 。称。称 为图为图G的伴随多项式。的伴随多项式。于是，求于是，求Pk(G)就是要求出就是要求出 的伴随多项式。的伴随多项式。用理想子图法求用理想子图法求Pk(G)的步骤如下：的步骤如下：(1)画出画出G的补图的补图 (2)求出关于补图的求出关于补图的 (3)写出关于补图的伴随多项式写出关于补图的伴随多项式16 (4)将将 代入伴随多项式中得到代入伴随多项式中得到Pk(G)。例例3 求下图求下图G的色多项式的色多项式Pk(G)。G 解：解：(1)G的补图为：的补图为：(2)求出关于补图的伴随多项式系数求出关于补图的伴随多项式系数ri(1i6)i6)17 1)r=6 2)r=5 3)r=418 4)r=3 5)r=2 6)r=1 (3)写出关于补图的伴随多项式写出关于补图的伴随多项式19 (4)将将 代入伴随多项式中得到代入伴随多项式中得到Pk(G)。可以作如下计算：可以作如下计算：由此可以断定：由此可以断定：。最优着色方式数有。最优着色方式数有12种。种。20 使用理想子图法求色多项式，还可以通过如下定理进使用理想子图法求色多项式，还可以通过如下定理进行改进。行改进。定理定理3 若若G有有t个分支个分支H1,H2,Ht,且且Hi的伴随多项式为的伴随多项式为h(Hi,x),i=1,2,t,则：则：该定理说明，在求该定理说明，在求 的伴随多项式时，可以分别求的伴随多项式时，可以分别求出它的每个分支的伴随多项式，然后将它们作乘积。出它的每个分支的伴随多项式，然后将它们作乘积。例例4 求下图求下图G的色多项式的色多项式Pk(G)。21 解解:(1)画出画出G的补图的补图G2154351432H3H2H1 (2)求出补图中个分支的伴随多项式求出补图中个分支的伴随多项式 (3)求出补图的伴随多项式求出补图的伴随多项式22 (4)求出求出G的色多项式的色多项式 注：在例注：在例4中，中，k=3时，时，P3(G)=6,由此可以推出由此可以推出G的点的点色数为色数为3.求出了色多项式，可以由多项式推出点色数。但是，求出了色多项式，可以由多项式推出点色数。但是，求色多项式的计算量是很大的。递推方法是指数类计算求色多项式的计算量是很大的。递推方法是指数类计算量，而理想子图法中主要计算量是找出所有理想子图，量，而理想子图法中主要计算量是找出所有理想子图，这也不是多项式时间算法。这也不是多项式时间算法。23 下面，我们对定理下面，我们对定理3作证明。作证明。定理定理3 若若G有有t个分支个分支H1,H2,Ht,且且Hi的伴随多项式为的伴随多项式为h(Hi,x),i=1,2,t,则：则：分析：由伴随多项式定义：分析：由伴随多项式定义：所以，我们只需要证明所以，我们只需要证明 等于等于 的的k次项系数即可。次项系数即可。设设24 一方面：一方面：该多项式中该多项式中 xk 的系数的系数rk为：为：另一方面：设另一方面：设Mj是是Hj中具有中具有ij个分支的个分支的Hj的理想子图。的理想子图。当当i1+i2+it=k时，时，M1 M2 Mt必是必是G的具有的具有k个个分支的理想子图。分支的理想子图。25 在给定的在给定的i1,i2,it且且i1+i2+it=k情形下，对应的情形下，对应的G的的具有具有k个分支的理想子图个数为：个分支的理想子图个数为：所以，所以，G的具有的具有k个分支的理想子图的总个数为：个分支的理想子图的总个数为：所以得：所以得：26(三三)、色多项式的性质、色多项式的性质 定理定理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来说，由归纳假设，可设其色多项式为：来说，由归纳假设，可设其色多项式为：27 同样，可设同样，可设Ge的色多项式为：的色多项式为：由色多项式递推公式得：由色多项式递推公式得：注注:(1)定理的逆不成立定理的逆不成立!28 例例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;29 所以：所以：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.上面推导导出了矛盾！上面推导导出了矛盾！注注:(2)同构的图具有相同的色多项式，但逆不真。同构的图具有相同的色多项式，但逆不真。30 例例6 求证：下面图求证：下面图G1与与G2非同构但具有相同的色多项式。非同构但具有相同的色多项式。G1G2u1v1 证明：因为证明：因为G1和和G2中分别有一个唯一的中分别有一个唯一的4度顶点：度顶点：u1与与v1。但是它们邻点状况不相同。但是它们邻点状况不相同:u1有有4个个2度邻点。而度邻点。而v1只有只有两个两个2度邻点。所以度邻点。所以G1与与G2不同构。不同构。通过直接计算得：通过直接计算得：Pk(G1)=Pk(G2)=10k3+5k4+k5 对于图的色多项式，还有许多结论和进一步研究的问题。对于图的色多项式，还有许多结论和进一步研究的问题。例如：教材上的例如：教材上的Read猜想就是一个待研究问题。猜想就是一个待研究问题。31 作业作业 P187-190 习题习题7：28，31，32，3332Thank You!