染色问题的求解方法

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

1、染色问题的求解方法某伞厂所生产的伞品种齐全，其中品牌为"太阳伞"的伞的伞蓬都由太阳光的七种颜色组成，这七种颜色分别涂在伞蓬的八个区域内，且恰有一种颜色涂在相对的区域内，则不同颜色图案的此类太阳伞至多有（　）种（A）40320　　（B）5040　　（C）20160　　（D）2520答案：B一、区域染色问题对区域的染色问题一般是（1）直接根据两个基本原理求解；（2）根据所用的颜色的种数分类；（3）根据某两个区域同色或不同色分类；（4）根据相间区域使用的种类分类。西藏四川青海云南用四种颜色给四川、青海、西藏、云南四省（区）的地图染色

2、，每一省（区）一种颜色，只要求相邻的省（区）不同色，则不同的染色方法有多少种？分析：给四川染色有4种方法，给青海染色有3种方法，给西藏染色有2种方法，给云南染色有2种方法，根据分步计数原理共有种方法。点评：本例是直接利用两个基本原理来解决。21534（2003全国）16．如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有________种。（以数字作答）答案：72解法一:合并单元格法分析：颜色相同的区域可能是②④，③⑤。下面分情况讨论：（ⅰ）当②④颜色相同且③

3、⑤颜色不同时，将②④合并成一个单元格，此时不同的着色方法相当于四个元素②④、①、③、⑤的全排列数。（ⅱ）当②④颜色不同且③⑤颜色相同时同情形（ⅰ）有种着色方法。（ⅲ）当②④及③⑤分别同色时，分别将②④及③⑤合并，这样仅有三个单元格，即②④、③⑤、①，从4种颜色中选3种来着色这三个单元格，即有种方法。由分类计数原理知，不同的着色方法共有（种）。解法二：由题意可知至少要选三种颜色，依着色的种数分类：（ⅰ）当选用三种颜色时，区域②与④必须同色，区域③与⑤必须同色，故有种。（ⅱ）当用四种颜色时，若区域仅②与④同色有种，若区域仅③与⑤同

4、色有种，故用四种颜色时共有种。由分类计数原理知，不同的着色方法共有（种）。解法三：依某两个不相邻的区域同色与不同色分类：（ⅰ）当区域②与④同色时，区域①有4种着色方法，区域②有3种着色方法，区域③有2种着色方法，区域④有1种着色方法，区域⑤有2种着色方法，故有种。第4页共4页（ⅱ）当区域②与④不同色时，区域①有4种着色方法，区域②有3种着色方法，区域③有2种着色方法，区域④有1种着色方法，区域⑤有种着色方法，故有种。综上可知，满足题意的着色方法共有种。点评：解法一：合并单元格法；解法二：依使用颜色的种数进行分类；解法三：是根据

5、某两个不相邻的区域是否同色进行讨论的。12345（2003新课程文）将3种作物种植在如图的5块试验田里，每块种植一种作物且相邻的试验田不能种植同一作物，不同的种植方法共有___________种。（以数字作答）答案：42分析：种植同种作物的试验田可能是：①③，①④，①⑤，②④，②⑤，③⑤，①③⑤。注意到：5=2+2+1或5=3+1+1，所以必有两对区域的颜色分别相同或有且仅有三个区域同色的不同搭配方式有：①③、②④、⑤，①③、②⑤、④，①④、②⑤、③，①④、③⑤、②，①⑤、②④、③，②④、③⑤、①，①③⑤、②、④。所以不同的种

6、植方法共有（种）点评：本例是先合并单元格，然后再重新组合涂色。523416（2003新课程）某城市在中心广场建造一个花圃，花圃分为6个部分（如图）。现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有________种。（以数字作答）答案：120分析：颜色相同的部分可能有：⑥③、⑥④、⑤②、⑤③、④②。经分析至少用四种颜色且不可能出现三个区域同色的情形，注意到6=2+2+1+1，所以必有两对区域同色，不同的搭配情形有：⑥③、⑤②、①、④；⑥③、④②、①、⑤；⑥④、⑤②、①、③；⑥④、⑤③、①

7、、②；⑤③、④②、①、⑥。∴共有种栽种方法。点评：本例也是先合并单元格，然后再重新组合涂色。2134用红、黄、蓝、白、黑5种颜色涂在“田”字形的4个小方格内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种涂色方法？解析：如图，把问题分成三类：（ⅰ）四格涂不同的颜色，方法有种；（ⅱ）有且仅有两格涂相同的颜色，即一组对角小方格涂相同的颜色涂法种数为；（ⅲ）两组对角小方格分别涂相同的颜色，涂法种数为。因此，所求得涂法种数为：。点评：本例是根据某两个不相邻的区域是否同色进行讨论的。②①③④⑤⑥如图一个正六边形

8、的6个区域①②③④⑤⑥，现给这六个区域着色，要求同一区域染同一种颜色，相邻的两个区域不得使用同一种颜色，现有4种颜色可供选择，则有多少种不同的着色方法？解：（ⅰ）当相间区域①③⑤着同一颜色时，有4种着色方法，此时②④⑥各有三种着色方法，故有种方法。（ⅱ）当相间区域①③⑤着两种