定理1(直线型结构)：用种颜色给如图所示的由个区域组成的直线型结构图涂色，则总的不同涂法有种.

证明：由分步计数原理按序号逐个涂色即可。

定理2(星型结构)：用种颜色给如图所示的由个区域组成的星型结构图涂色，则总的不同涂法有种.

证明：由分步计数原理按序号逐个涂色即可。

定理3(环形结构)：用种颜色给如图所示的由个区域组成的环形结构图涂色，则总的不同涂法有种.

证明： (中头尾不同的涂法数为，头尾相同时,头尾看作一个区域，涂法数为)，即，

∴，求通项即可

或

定理4(全连通型结构)：用种颜色给由个区域组成的全连通型结构图(任何两个区域都连通，如图)涂色，则总的不同涂法有种.

证明：任何两个区域都连通，所以颜色各不相同。

方法应用

例1.将三种作物种植在如图所示的5块试验田里，每块种植一种作物且相邻的试验田不能种植一种作物，不同的种植方法有       种.(以数字作答)

答：结构抽象如右图，涂法数为： 

例2.某城市在中心广场建造一个花圃，花圃分为6个部分(如图).现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有       种.(以数字作答)

答：结构抽象如右图，涂法数为： (先涂中间)

例3.用种不同的颜色为下列两块广告牌着色，要求在1,2,3,4四个区域中相邻(有公共边界)的区域用不同的颜色，

(Ⅰ)若，为左图着色时共有多少种不同的方法？

(Ⅱ)若为右图着色时，共有120种不同的方法，求的值. 

答：结构抽象如右图，

(Ⅰ)涂法数为：，(先涂三角形结构)

(Ⅱ)涂法数为：，∴ 

例4. 用种不同的颜色为下图中的5个区域着色，要求相邻(有公共边界)的区域用不同的颜色，共有多少种不同的方法？

答：结构抽象如右图，

先涂的三角形，再涂，最后涂，共有多少种不同的方法

例5.用种不同的颜色为下列两块广告牌着色，要求相邻(有公共边界)的区域用不同的颜色，共有多少种不同的方法？

答：结构抽象如右图， (先涂，再涂线型结构).

例6.(2008重庆)某人有4种颜色的灯泡(每种颜色的灯泡足够多)，要在如题(16)图所示的6个点上各装一个灯泡，要求同一条线段两端的灯泡不同色，则每种颜色的灯泡都至少用一个的安装方法共有        种(用数字作答). 

答： 

引申：若有种颜色的灯泡，则不同的安装方法共有        种。

若下、上层对应点灯泡颜色允许相同，则共有种涂法；

下、上层有且只有一组对应点颜色相同，则可以把同色的两点看成一点，则几何体为四棱锥，抽象图如下左，不同的涂法有种；

下、上层有且只有两组对应点颜色相同，则可以把同色的两点看成一点，则几何体为四面体，抽象图如下右，不同的涂法有种；

下、上层三组对应点颜色都相同，则可以把同色的两点看成一点，则几何体退化为三角形，不同的涂法有种。

由容斥原理知，不同的涂法有

简单的组合结构练习

1.如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有           种（以数字作答）

答：结构抽象如右图，涂法数为： (先涂中间)

2.

用M种颜色去涂上图所示的各个结构图，共有多少种不同的涂法？

答：(1) (先涂三角形)；

(2) (先涂三角形)；

(3) (先涂三角形)；

(4) (先涂中间三角形)；

(5) (先涂，再涂线型结构).下载本文