数学选修2-3-涂色问题

涂色问题解题通法定理1(直线型结构)：用种颜色给如图所示的由个区域组成的直线型结构图涂色，则总的不同涂法有种.证明：由分步计数原理按序号逐个涂色即可。定理2(星型结构)：用种颜色给如图所示的由个区域组成的星型结构图涂色，则总的不同涂法有种.证明：由分步计数原理按序号逐个涂色即可。定理3(环形结构)：用种颜色给如图所示的由个区域组成的环形结构图涂色，则总的不同涂法有种.证明：(中头尾不同的涂法数为，头尾相同时,头尾看作一个区域，涂法数为)，即，求通项即可或定理4(全连通型结构)：用种颜色给由个区域组成的全连通型结构图(任何两个区域都连通，如图)涂色，则总的不同涂法有种.证明：任何两个区域都连通，所以颜色各不相同。方法应用例1.将三种作物种植在如图所示的5块试验田里，每块种植一种作物且相邻的试验田不能种植一种作物，不同的种植方法有 种.(以数字作答)答：结构抽象如右图，涂法数为：例2.某城市在中心广场建造一个花圃，花圃分为6个部分(如图).现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有 种.(以数字作答)答：结构抽象如右图，涂法数为：(先涂中间)例3.用种不同的颜色为下列两块广告牌着色，要求在1,2,3,4四个区域中相邻(有公共边界)的区域用不同的颜色，()若，为左图着色时共有多少种不同的方法？()若为右图着色时，共有120种不同的方法，求的值. 答：结构抽象如右图，()涂法数为：，(先涂三角形结构)()涂法数为：，例4. 用种不同的颜色为下图中的5个区域着色，要求相邻(有公共边界)的区域用不同的颜色，共有多少种不同的方法？ 答：结构抽象如右图，先涂的三角形，再涂，最后涂，共有多少种不同的方法136245例5.用种不同的颜色为下列两块广告牌着色，要求相邻(有公共边界)的区域用不同的颜色，共有多少种不同的方法？答：结构抽象如右图，(先涂，再涂线型结构).例6.(2008重庆)某人有4种颜色的灯泡(每种颜色的灯泡足够多)，要在如题(16)图所示的6个点上各装一个灯泡，要求同一条线段两端的灯泡不同色，则每种颜色的灯泡都至少用一个的安装方法共有 种(用数字作答). 答：引申：若有种颜色的灯泡，则不同的安装方法共有 种。若下、上层对应点灯泡颜色允许相同，则共有种涂法；下、上层有且只有一组对应点颜色相同，则可以把同色的两点看成一点，则几何体为四棱锥，抽象图如下左，不同的涂法有种；下、上层有且只有两组对应点颜色相同，则可以把同色的两点看成一点，则几何体为四面体，抽象图如下右，不同的涂法有种；下、上层三组对应点颜色都相同，则可以把同色的两点看成一点，则几何体退化为三角形，不同的涂法有种。由容斥原理知，不同的涂法有简单的组合结构练习1.如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有 种（以数字作答）21534答：结构抽象如右图，涂法数为：(先涂中间)2.用M种颜色去涂上图所示的各个结构图，共有多少种不同的