《图论及其应用》课程教学课件（PPT讲稿）第七章 图的着色 7-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 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

P(G)=k(k-1k-2)+k(k-1)=k3-2k2+k 也可由推论： (k-1)P(K2) =k3-22+k

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) G1  3 2 1 ( ) ( 1)( 2) ( 1) 2 P G k k k k k k k k k = − − + − = − + 也可由推论： G1 = 2 ( 1) ( ) k k P K − 3 2 = − + k k k 2

44 P(G2)=k(k-1)k-2k-3)+2k(k-1k-2)+k(k-1) =k(k-1)k2-3k+3)

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.50 0.51 n 7 (2) G 2 2 2 ( ) ( 1)( 2)( 3) 2 ( 1)( 2) ( 1) ( 1)( 3 3) P G k k k k k k k k k k k k k k = − − − + − − + − = − − +

P(G)=k(k-1k3-5k2+10k-7)

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) G3 — — 3 2 3 ( ) ( 1)( 5 10 7) P G k k k k k k = − − + −

注：递推计数法的计算复杂度是指数型的。 2、理想子图计数法 (1)预备知识 定义1：设H是图G的生成子图。若H的每个分支均为 完全图，则称H是G的一个理想子图。用N,(G)表示G的 具有r个分支的理想子图的个数。 例2求N(G),Ns(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 9 注：递推计数法的计算复杂度是指数型的。 2、理想子图计数法 (1) 预备知识 定义1：设H是图G的生成子图。若H的每个分支均为 完全图，则称H是G的一个理想子图。用N r (G)表示G的 具有 r 个分支的理想子图的个数。 例2 求N4 (G), N5 (G)。 G

解：通过观察枚举求N(G S 1)N(G: 10

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 