数学选修23涂色问题.docx

精品文档

涂色问题解题通法

定理1(直线型结构)：用m(m?2)种颜色给如图所示的由n(n?2)个区域组成的直线型结

构图涂色，则总的不同涂法有Lm

n

?m?m?1?n?1种.

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

定理2(星型结构)：用m(m?2)种颜色给如图所示的由n(n?2)个区

域组成的星型结构图涂色，则总的不同涂法有Sm

n

?m?m?1?n?1种.

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

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

Rm??m?1?n??m?1???1?n种.

n

证明：Rm?Rm ?Lm(Lm中头尾不同的涂法数为Rm，头尾相同时,

nn n?1 n n

n

? ?n?1

头尾看作一个区域，涂法数为Rm

)，即Rm?Rm

?mm?1 ，

n?1 n n?1

∴Rm

??m?1?n

???Rm

??m?1?n?1?，求通项即可

n ? n?1 ?

或Rm

n

??m?2?Rm

n?1

??m?1?Rm

n?2

定理4(全连通型结构)：用m(m?n)种颜色给由n个区域组成的全连通型结构图(任何两个

区域都连通，如图)涂色，则总的不同涂法有Tm

n

?An种.

m

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

方法应用

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

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

5

L2

5

?3??3?1?5?1?C2?2??2?1?5?1?48?6?42

3

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

精品文档

精品文档

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

? ?

5

?4???3?1?5??3?1???1?5??120(先涂中间)

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

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

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

答：结构抽象如右图，

(Ⅰ)涂法数为：Tn??6?2??A3?4?480，(先涂三角形结构)

3 ? 6 ?? ?? ?

(Ⅱ)涂法数为：Tn

4

?A4?n

n

n?1

n?2

n?3

?120，∴n?5

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

色，共有多少种不同的方法？

答：结构抽象如右图，

先涂A,A,A

的三角形，再涂A

，最后涂A

，共有A3?4?5多少种不同的方法

1 2 4 3 5 6

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

色，共有多少种不同的方法？

A3 A

A

4

2A3 5 6

2

A

4 2 A

5

A

1

1

A

6

答：结构抽象如右图，m?m?1??m?2?4(先涂A，再涂线型结构A

?A?A

?A?A).

1 2 3 4 5 6

例6.(2008重庆)某人有4种颜色的灯泡(每种颜色的灯泡足够多)，要 C

1

1在如题(16)图所示的6个点A,B,C,A,B,C上各装一个灯泡，要求 A B

1

1 1 1 1

同一条线段两端的灯泡不同色，则每种颜色的灯泡都至少用一个的安

装方法共有 种(用数字作答). C

答：A3?3?(2?2?1) A B

4

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

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

n n

精品文档

精品文档

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

? ?

下、上层有且只有两组对应点颜色相同，则可以把同色的两点看成一点，则几何体为四面体，

抽象图如下右，不同的涂法有A4种；

n

下、上层三组对应点颜色都相同，则可以把同