环形染色问题

《环形染色问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2011/10/25思路方法技巧高二年级15971660602Helen.wp@163.com环形区域染色计数问题王平宜昌市三峡高级中学443100在近几年的高考与各地模考中常见区域染色计数问题的试题，这类试题包含着丰富的数学思想，解题方法技巧性强且灵活多变，有利于培养学生的创新思维能力、分析问题与观察问题的能力．其中的条形区域染色问题学生容易掌握，但对于环形区域的染色问题往往不能灵活应对，甚至无从下手．针对环形区域染色计数问题的求解笔者做了一番尝试，总结出一种行之有效的方法．一、问题展示用A、B、C、

2、D、E五种颜色涂在“田”字形的四个小方格内（如右图），每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种不同的涂色方法？12434分析：解决这类环形区域计数问题的方法常常是分类讨论：（1）四个区域颜色均不相同，有种；（2）区域1、3同色而区域2、4不同色，有种；（3）区域2、4同色而区域1、3不同色，有种；（4）区域1、3同色且区域2、4同色，有种；所以共有：+++=260种．分类方式在区域较少的时候采用比较适合，但区域较多的情况难以进行．为了解决这个问题，不妨先将颜色和区域简化，

3、观察并归纳其中的规律，再来解决此类问题．二、问题分解123问题1：用A、B、C三种颜色涂在如图所示的的三个小方格内（如下图），每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种不同的涂色方法？并将所有可能的涂色方案分别列举出来解：所有可能的染色方案有：（按1、2、3的顺序写成排列）ABAABCACAACBBABBACBCABCBCABCACCBACBC共12个排列，即有12种染色方案．1234问题2：如果将问题1中的条形区域改为如右图所示的的四个区域，则应如何求解？解：可以在三个区

4、域的基础上进行添加，以区域1、2、3分别染ABA为例，第四个区域可以染除颜色A外的B、C两种色的任何一种，即有ABAB、ABAC2种．同理，其他所有排列都可以这样处理。如下图所示：123所以：共有12*2=24种染色方案问题3：如果将问题1中的条形区域改为如下图所示的的三个扇形区域，则应如何求解？解：问题3与问题1的区别在于问题3中区域1与区域3也相邻，故问题3的染色排列数可以在问题1的染色排列数中挑选首尾不同的排列数ABCACBBACBCACABCBA共6种不同的排列，即有6种不同的染色方案．1243

5、问题4：如果将问题2中的三个区域改为如右图所示的的四个区域，则应如何求解？解：同样区域4的处理方式可以仿照问题3，即从问题2中挑选首尾不同的排列数．1234A124B124C124三、归纳升华通过问题1到问题4我们可以发现，问题1、2、3、4中存在千丝万缕的联系。我们用右图中表格呈现他们之间的关系：（注：表格中的列3行A表示对条形问题中第3个区域染色时，以A结尾的排列数）按照问题1到问题2的思路，列4行A的排列数可以建立在区域3结尾为B或C的的基础上，故列4行A的排列数等于列3行B的排列数+列3行C的排

6、列数=8；同理可以得到列4行B、列4行C的值都是8．但是我们从中考查首尾不同的排列的排列数的时候发现了问题，列4行A（第4个区域染色A的排列数）中包含第1个区域为A，也包含第1个区域为B、C，即其中包含首尾相同的，也含首尾不同的．这样，我们就没有办法考查首尾不同的排列数了．仔细分析问题产生的原因，主要是区域1有A、B、C三种颜色，区域4也有三种颜色，无法分辨出首尾颜色相同和不同．为了解决这个问题，我们再回到问题3，为什么问题3中我们可以分辨出来呢？这是因为问题3中的区域1颜色已知．也就是说，在区域1颜色

7、已知的前提下，我们是可以分辨出来的．那么如果区域1颜色固定，就不存在上述问题．于是，我们可以按第一个区域染A、B、C三种不同类型分类解决这个问题。（按上表中产生排列数数据的方式，产生三个表格）1234A1022B0113C01131234A0113B0113C10221234A0113B1022C0113表1表2表3以区域1颜色为A为例（如表1），即区域1我们染A的排列数为1。染B、C的排列数为0．经过以上产生排列数的方法完成表格后，发现，在区域1染A的前提条件下，区域4染A、B、C的排列数分别为2、3

8、、3，又因为首尾不同，即区域4不能染A．则首尾不同的排列数为区域4染B、C的排列数有3+3=6个．而且通过上面的三个表格我们可以发现，区域1染A的排列数、区域1染B的排列数、区域1染C的排列数相同．因此，我们可以简化过程，只列出一个表1，得到相应的答案后乘以区域1染色的可能数．即对于本题来说，表1中我们得到在区域1染A的前提下有6种不同的排列，则总的排列数应为：6*3=18种．即有18种染色方案．四、总结方法回头我们再来看看这类问题的解决办