本次课主要内容 着色的计数与色多项式 (一)、色多项式概念 (二)、色多项式的两种求法 (三)、色多项式的性质
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 本次课主要内容 (一)、色多项式概念 (二)、色多项式的两种求法 着色的计数与色多项式 (三)、色多项式的性质
(一)、色多项式概念 所谓色计数，就是给定标定图G和颜色数k,求出正常顶 点着色的方式数。方式数用P(G)表示。 可以证明：P(G是k的多项式，称为图G的色多项式。 由点色数可和色多项式P(G)的定义可得： (1)若 k<©，则P(G)=0; z(G)=min{kP(G)≥1 (2)若G为空图，则P(G)=k"。 (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 2 所谓色计数，就是给定标定图G和颜色数k,求出正常顶 点着色的方式数。方式数用Pk (G)表示。 ( ) min ( ) 1 G k P G = k (一)、色多项式概念 可以证明：Pk (G)是k的多项式，称为图G的色多项式。 由点色数 和色多项式Pk ( ) G (G)的定义可得： (1) 若 ，则Pk k G ( ) (G)=0 ; (2) 若G为空图，则Pk (G)=kn 。 (3) Pk (Kn )=k(k-1).(k-n+1)
(二)、色多项式的两种求法 1、递推计数法 定理1设G为简单图，则对任意e∈E(G)有： P(G)=P(G-e)-P(G-e) 证明：设e=uv。则对Ge的着色方式数可以分为两部分： (1)u与v着不同颜色。此时，等于G的着色方式数； (2)u与v着同色。此时，等于Ge的着色方式数； 所以，得：P(G)=P(G-e)-P(Ge)
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 1、递推计数法 (二)、色多项式的两种求法 定理1 设G为简单图，则对任意 e E G ( ) 有： ( ) ( ) ( ) P G P G e P G e k k k = − − 证明：设e=uv。则对G-e的着色方式数可以分为两部分： (1) u与v着不同颜色。此时，等于G的着色方式数； (2) u与v着同色。此时，等于G·e 的着色方式数； 所以，得： ( ) ( ) ( ) P G P G e P G e k k k = − −
推论：设G是单图，e=v是G的一条边，且d(u)=1,则： P.(G)=(k-1)P(G-) 证明：因为G是单图，e=uy,d(u=l,所以Ge=G-u。 另一方面，P(G-e)=kP(G-u) 所以，P(G)=P(G-e)-P(Ge) =k(G-w)-P(G-) =(k-1)P(G-W) 注：对递推公式的使用分析：
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 4 推论：设G是单图，e=uv是G的一条边，且d(u)=1,则： 证明：因为G是单图，e=uv, d(u)=1,所以G·e = G-u。 另一方面，Pk (G-e)=kPk (G-u) 所以， 注：对递推公式的使用分析： ( ) ( ) P G P G u k k = − (k-1) ( ) ( ) ( ) P G P G e P G e k k k = − − ( ) ( ) k k = − − − kP G u P G u ( ) = − P G u k (k-1)
(1)当图G的边数较少时，使用减边递推法： P(G)=P(G-e)-P.(G-e) (2)当图G的边数较多时，使用加边递推法： P.(G-e)=P(G)+P(G-e) 例1求出下面各图的色多项式。 G G2
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 5 (1) 当图G的边数较少时，使用减边递推法： ( ) ( ) ( ) P G P G e P G e k k k = − − (2) 当图G的边数较多时，使用加边递推法： ( ) ( ) ( ) P G e P G P G e k k k − = + 例1 求出下面各图的色多项式。 G1 G2 G3