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

数学选修2-3 - 涂色问题 涂色问题解题通法定理1(直线型构造)：用m(m?2)种颜色给如下图的由n(n?2)个区域组成的直线型结m构图涂色，那么总的不同涂法有Ln?m?m?1?n?1种.证明：由分步计数原理按序号逐个涂色即可定理2(星型构造)：用m(m?2)种颜色给如下图的由n(n?2)个区m域组成的星型构造图涂色，那么总的不同涂法有Sn?m?m?1?n?1种.证明：由分步计数原理按序号逐个涂色即可定理3(环形构造)：用m(m?2)种颜色给如下图的由n(n?3)个区域组成的环形构造图涂色，那么总的不同涂法有mRn??m?1???m?1???1?种.nnmmmmm证明：Rn(中头尾不同的涂法数为?Rn?LLR?1nnn，头尾一样时,mmRm?Rn头尾看作一个区域，涂法数为Rn?1?m?m?1??1)，即nn?1，∴Rn??m?1????Rn?1??m?1?mmnn?1??，求通项即可 ?或Rn??m?2?Rn?1??m?1?Rn?2mmm定理4(全连通型构造)：用m(m?n)种颜色给由n个区域组成的全连通型构造图(任何两个n区域都连通，如图)涂色，那么总的不同涂法有Tnm?Am种.证明：任何两个区域都连通，所以颜色各不一样。

方法应用例1.将三种作物种植在如下图的5块试验田里，每块种植一种作物且相邻的试验田不能种植一种作物，不同的种植方法有 种.(以数字作答)32答：构造抽象如右图，涂法数为：L5?L5?3??3?1?5?1?C32?2??2?1?5?1?48?6?42例2.某城市在中心广场建立一个花圃，花圃分为6个局部(如图).现要栽种4种不同颜色的花，每局部栽种一种且相邻局部不能栽种同样颜色的花，不同的栽种方法有 种.(以数字作答) 553答：构造抽象如右图，涂法数为：4?R5?4???3?1???3?1???1???120(先涂中间)例3.用n种不同的颜色为以下两块广告牌着色，要求在1,2,3,4四个区域中相邻(有公共边界)的区域用不同的颜色，(Ⅰ)假设n?6，为左图着色时共有多少种不同的方法？ (Ⅱ)假设为右图着色时，共有120种不同的方法，求n的值.答：构造抽象如右图，(Ⅰ)涂法数为：T3??6?2??A6?4?480，(先涂三角形构造)n3??(Ⅱ)涂法数为：T4?An?n?n?1??n?2??n?3??120，∴n?5n4例4. 用6种不同的颜色为下列图中的5个区域着色，要求相邻(有公共边界)的区域用不同的颜色，共有多少种不同的方法？答：构造抽象如右图，3先涂A1,A2,A4的三角形，再涂A3，最终涂A5，共有A6?4?5多少种不同的方法例5.用6种不同的颜色为以下两块广告牌着色，要求相邻(有公共边界)的区域用不同的颜色，共有多少种不同的方法？ 3 52 4 1 A3A4A5A1A646A2答：构造抽象如右图，m?m?1??m?2?(先涂A1，再涂线型构造A2?A3?A4?A5?A6). 例6.(2022重庆)某人有4种颜色的灯泡(每种颜色的灯泡足够多)，要在如题(16)图所示的6个点A,B,C,A1,B1,C1上各装一个灯泡，要求同一条线段两端的灯泡不同色，那么每种颜色的灯泡都至少用一个的安装方法共有 种(用数字作答).3答：A4?3?(2?2?1)A1C1B1CAB引申：假设有n(n?3)种颜色的灯泡，那么不同的安装方法共有 种。

33假设下、上层对应点灯泡颜色允许一样，那么共An有种涂法； ?An下、上层有且只有一组对应点颜色一样，那么可以把同色的两点看成一点，那么几何体为四棱锥，抽象图如下左，不同的涂法有n???n?1????1?44下、上层有且只有两组对应点颜色一样，那么可以把同色的两点看成一点，那么几何体为四面体，4抽象图如下右，不同的涂法有An种；?种； ?n?1???下、上层三组对应点颜色都一样，那么可以把同色的两点看成一点，那么几何体退化为三角形，3不同的涂法有An种331由容斥原理知，不同的涂法有An?An?C3?n???n?1????1? 简洁的组合构造练习44?43 ?C32?An?An?n?1???1.如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得运用同一颜色，现有4种颜色可供选择，那么不同的着色方法共有 种〔以数字作答〕 25 1 3444答：构造抽象如右图，涂法数为：4?R4?4???3?1???3?1???1???73(先涂中间)??2.用M种颜色去涂上图所示的各个构造图，共有多少种不同的涂法？3答：(1)(m?1)?Am(先涂三角形A1A2A3)；(2)(m?2)?Am(先涂三角形A1A2A3)； (3)(m?1)?Am(先涂三角形A1A2A3)； (4)(m?2)?Am(先涂中间三角形A1A2A3)；(5)m?m?1??m?2?(先涂A1，再涂线型构造A2?A3?A4?A5).333333本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第5页 共5页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页第 5 页 共 5 页。