涂色问题的解题思路2.docVIP

涂色问题的解题思路 我们在解排列、组合问题时，会经常遇到一类有n种颜色给m个区域涂色问题。解这类问题，容易产生错误，现介绍求解决这类问题的一般思路。 直线型 例1，用四种不同的颜色，给图1中的四个区域涂色，每个区域涂一种颜色，相邻区域不同颜色，共有多少种不同的涂色方法？ 图1 图2 分析：如果把每个区域分开，相邻的区域用线段连接，便得如图2的直线型。 思路一：直接给各个区域涂色，涂区域1有种方法，涂区域2时，由于要与区域1不同色，故只有种方法，同理涂区域3和4均有种方法，所以共有涂色方法 108（种）。 思路二：按选取颜色多少来分类：用四种颜色有种方法；用三种颜色，则必有两个区域同色，只可能是区域1与3，1与4，2与4同色，同色“捆绑”有种方法，而四色选三色有种方法，故有种方法；同理用两种颜色有种方法；由于至少要用两种颜色，故共有涂色方法种。 小结：比较这两种思路，对于直线型，思路一会较容易一些。 环型 例2，用四种不同的颜色，给图3中的四个区域涂色，每个区域涂一种颜色，相邻区域不同颜色，共有多少种不同的涂色方法？ 图3 图 4 分析：将图3分拆，即得图4的环型，此类题若按例1直线型中思路1来解得（种），这个结论是错误的。事实上区域4与2、3均相邻，这是与例1的区别所在，故在给区域4涂色时，需考虑区域2、3的色同与不同，因此对于环型，应分类研究。 思路一：按区域2、3的颜色同与不同可分两类：若区域2、3同色，则有 36（种）；若区域2、3不同色则有 48（种），故共有+ 84（种）。 思路二：按所选取的颜色多少来分类：选4种颜色时，有种涂法；选3种颜色时，有种涂法；选2种颜色时，有种涂法，因为至少需用两种颜色，故共有涂色方法（种）。 环绕型 例3，（2003年高考题）如图5，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有 种。 图5 图6 分析：将图5分拆，可得图6的环绕型。 思路一：涂区域1时，有种方法；涂区域2时，有种方法；涂区域3时，有种方法；涂区域4时，可考虑与区域2颜色同或不同，若区域4与2不同色，则涂区域4时只有1种涂法，此时涂区域5也只有1种涂法；若区域4与2同色，此时涂区域5有种涂法，故共有 72（种）。 思路二：按所用的颜色多少来分类，用4种颜色时，有种涂法；用3种颜色时，有，因为至少要用3种颜色，所以完成五个区域的涂色共 72种。 小结：对于复杂的涂色问题，按所选取的颜色的多少来分类的方法较为简捷。 混合型 例4，用四种不同的颜色，给图7中的四个区域涂色，每个区域涂一种颜色，相邻区域不同颜色，共有多少种不同的涂色方法？ 图7 图8 分析：将图7分拆，便得图8的混合型， 解决这类问题的思路，通常是按选多少种颜色来分类，选用4种颜色时，有种涂法；选3种颜色时，有种涂法；因为至少要用3色，故共有（种）。 通过对上述四种类型的涂色问题的分析可知：无论图形如何繁简，按所选颜色的多少进行分类，便能迅速、准确地求解涂色问题。 第 2 页 共 2 页 1 2 3 4 3 4 2 1 1 2 3 4 4 3 2 1 1 4 5 2 3 1 2 5 32 4 1 3 2 4 1 2 3 4