图论电子科大杨春2

Email:yc517922@126.com

图论及其应用任课教师：杨春数学科学学院1本次课主要内容(一)、色多项式概念(二)、色多项式的两种求法着色的计数与色多项式(三)、色多项式的性质2所谓色计数，就是给定标定图G和颜色数k,求出正常顶点着色的方式数。方式数用Pk(G)表示。(一)、色多项式概念可以证明：Pk(G)是k的多项式，称为图G的色多项式。由点色数和色多项式Pk(G)的定义可得：

(1)若，则Pk(G)=0;

(2)若G为空图，则Pk(G)=kn。

(3)Pk(Kn)=k(k-1)…(k-n+1)。3

1、递推计数法(二)、色多项式的两种求法定理1设G为简单图，则对任意有：证明：设e=uv。则对G-e的着色方式数可以分为两部分：

(1)u与v着不同颜色。此时，等于G的着色方式数；

(2)u与v着同色。此时，等于G·e的着色方式数；所以，得：4推论：设G是单图，e=uv是G的一条边，且d(u)=1,则：证明：因为G是单图，e=uv,d(u)=1,所以G·e=G-u。另一方面，Pk(G-e)=kPk(G-u)所以，注：对递推公式的使用分析：5

(1)当图G的边数较少时，使用减边递推法：

(2)当图G的边数较多时，使用加边递推法：例1求出下面各图的色多项式。G1G3G26

(1)G1也可由推论：G17

(2)G28

(3)G3——9注：递推计数法的计算复杂度是指数型的。

2、理想子图计数法

(1)预备知识定义1：设H是图G的生成子图。若H的每个分支均为完全图，则称H是G的一个理想子图。用Nr(G)表示G的具有r个分支的理想子图的个数。例2求N4(G),N5(G)。G10解：通过观观察枚举求求Nr(G)G1)N4(G):G11N4(G)=62)N5(G):GN5(G)=512定理2设qr(G)表示将单图图G的顶点集合合V划分为r个不同色组组的色划分分个数，则则：证明：一方方面，设G的任一r色划分为：：｛V1,V2,…,Vr｝。于是，，对于1≦i≦r,是的的完全子图图。因为Vi∩Vj=Φ(i≠j),所以是是的的理理想子图。。这说明：G的任一r色划分必然对对应的的一个个理想子图。。容易知道，，这种对应是是唯一的；另一方面，对对于的的任一一具有r个分支的理想想子图，显然然它唯一对应应G中一个r色组。13所以，我们得得到：上面定理2实际上给出了了色多项式的的求法：用k种颜色对单图图G正常着色，可可以这样来计计算着色方式式数：色组为为1的方式数+色组为2的方式数+…+色组为n的方式数。即即有如下计数数公式：(2)色多项式求法法----理想子图法14定义2：设G是单图，令Ni(G)=ri,[k]i=xi。称为图G的伴随多项式式。于是，求Pk(G)就转化为求的的伴随多项项式。用理想子图法法求Pk(G)的步骤如下：：(1)画出G的补图(2)求出关于补图图的(3)写出关于补图图的伴随多项项式15(4)将代代入伴随多项项式中得到Pk(G)。例3求下图G的色多项式Pk(G)。G解：(1)G的补图为：(2)求出关于补图图的伴随多项项式系数ri(1≦i≦6)161)r=62)r=53)r=4174)r=35)r=26)r=1(3)写出关于补图图的伴随多项项式18(4)将代代入伴随多项项式中得到Pk(G)。可以作如下计计算：由此可以断定定：。。最优着色方方式数有12种。19使用理想子图图法求色多项项式，还可以以通过如下定定理进行改进进。定理3若G有t个分支H1,H2,…Ht,且Hi的伴随多项式式为h(Hi,x),i=1,2,…,t,则：该定理说明，，在求的的伴随多项项式时，可以以分别求出它它的每个分支支的伴随多项项式，然后将将它们作乘积积。例4求下图G的色多项式Pk(G)。20解:(1)画出G的补图G2154351432H3H2H1(2)求出补图中个个分支的伴随随多项式(3)求出补图的伴伴随多项式21(4)求出G的色多项式注：在例4中，k=3时，P3(G)=6,由此可以推出出G的点色数为3.求出了色多项项式，可以由由多项式推出出点色数。但但是，求色多多项式的计算算量是很大的的。递推方法法是指数类计计算量，而理理想子图法中中主要计算量量是找出所有有理想子图，，这也不是多多项式时间算算法。22下面，我们对对定理3作证明。定理3若G有t个分支H1,H2,…Ht,且Hi的伴随多项式式为h(Hi,x),i=1,2,…,t,则：分析：由伴随随多项式定义义：所以，我们只只需要证明等等于的的k次项系数即可可。设23一方面：该多项式中xk的系数rk为：另一方面：设设Mj是Hj中具有ij个分支的Hj的理想子图。。当i1+i2+…+it=k时，M1∪M2∪…∪Mt必是G的具有k个分支的理想想子图。24在给定的i1,i2,…,it且i1+i2+…+it=k情形下，对应应的G的具有k个分支的理想想子图个数为为：所以，G的具有k个分支的理想想子图的总个个数为：所以得：25(三)、色多项式的的性质定理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来说，由归纳纳假设，可设设其色多项式式为：26同样，可设G·e的色多项式为为：由色多项式递递推公式得：：注:(1)定理的逆不成成立!27例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;28所以：：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)同构的的图具具有相相同的的色多多项式式，但但逆不不真。。29例6求证：：下面面图G1与G2非同构构但具具有相相同的的色多多项式式。G1G2u1v1证明：：因为为G1和G2中分别别有一一个唯唯一的的4度顶点点：u1与v1。但是是它们们邻点点状况况不相相同:u1有4个2度邻点点。而而v1只有两两个2度邻点点。所所以G1与G2不同构构。通过直直接计计算得得：Pk(G1)=Pk(G2)=10[k]3+5[k]4+[k]5对于图图的色色多项项式，，还有有许多多结论论和进进一步步研究究的问问题。。例如如：教