染色问题的计数方法

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

1、染色问题的计数方法河北张家口市第三中学王潇与染色问题有关的试题新颖有趣,其中包含着丰富的数学思想,染色问题,解题方法技巧性强且灵活多变,故这类问题有利于培养学生的创新思维能力,分析问题与观察问题的能力,有利于开发学生的智力。一、区域染色问题1.根据乘法原理，对各个区域分步染色，这是处理这类问题的基本的方法。例1要用四种颜色给四川、青藏、西藏、云南四省（区）的地图染色（图1）每一省（区）一种颜色，只要求相邻的省（区）不同色，则不同染色的方法有多少种？分析先给四川染色有4种方法，再给青海染色有3种方法，接着给西藏染色有2种方法，

2、最后给云南染色有2种方法，根据乘法原理，不同的染色方法共有4×3×2×2＝48种2.根据共用了多少种颜色分类讨论，分别计算出各种情形的种数，再用加法原理求出不同年拾方法种数。例2（2003年全国高考题）如图2，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有多少种？分析依题意至少要选用3种颜色。（1）当选用三种颜色时，区域2与4必须同色，区域3与5必须同色，有种。（2）当用四种颜色时，若区域2与4同色，则区域3与5不同色，有种；若区域3与5同色，则区域2与4不同

3、色，有种，故用四种颜色时共有2种。由加法原理可知满足题意的着色方法共有＋2＝24＋2×24＝72种。3根据某两个不相邻区域是否同色分类讨论，从某两个不相邻区域同色与不同色入手，分别计算出两种情形的种数，再用加法原理求出不同染色方法数。例3用红、黄、蓝、白、黑五种颜色涂在“田”字形的四个小方格内（图3），每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种不同的涂色方法？（1）四格涂不同的颜色，方法数为；（2）有且仅有两格涂相同的颜色，即只有一组对角小方格涂相同颜色，涂法种数为2；（1）两组对角小方格涂相同

4、颜色，涂法种数为。因此，所求的涂法种数为＋2＋＝260种1.根据相间区域使用颜色的种类分类讨论例4如图4，一个六边形的6个区域A、B、C、D、E、F，现给这6个区域着色，要求同一区域染同一种颜色，相邻的两个区域不得使用同一颜色，现有4种不同的颜色可供选择，则有多少种不同的着色方法。解：（1）当相间区域A、C、E着同一种颜色时，有4种着色方法，此时，B、D、F各有3种着色方法故有4×3×3×3＝108种方法（2）当相间区域A、C、E着两种不同颜色时，有种着色方法，此时B、D、F有3×2×2种着色方法，故共有×3×2×2＝432

5、种着色方法。（2）当相间区域A、C、E着三种不同颜色时，有种着色方法，此时B、D、F各有2种着色方法，此时共有×2×2×2＝192种方法。故总计有108＋432＋192＝732种方法二点染色问题点染色问题，要注意对各点依次染色，主要方法有:（1）根据共用了多少种颜色分类讨论；（2）根据相对顶点是否同色分类讨论。例5将一个四棱锥S－ABCD的每个顶点染上一种颜色，并使同一条棱的两端点异色，如果只有5种颜色可供使用，那么不同的染色方法的总数是多少？解法1满足题设条件的染色至少要用三种颜色（1）若恰用三种颜色，可先从五种颜色中任选

6、一种染顶点S，再从余下的四种颜色中任选两种染A、B、C、D四点，，此时只能A与C，B与D分别同色，故有＝60种方法。（2）若恰用四种颜色，可先从五种颜色中任选一种染顶点S，再从余下的四种颜色中任选两种染A与B，由于A、B颜色可以交换，故有种染法；再从余下的两种颜色种任选一种染D或C，而D与C中另一个只需染与其相对顶点同色即可，故有＝240中方法。（3）若恰用五种颜色，有＝120种染法。综上，满足题意的染色方法数为60＋240＋120＝420种。解法2设想染色按S－A－B－C－D的顺序进行，对S、A、B染色，有5×4×3＝60

7、种染色方法。由于C点的颜色可能与A同色或不同色，这影响到D点颜色的选取方法数，故分类讨论：C与A同色时（此时C对颜色的选取方法唯一），D与A、C、S不同色，有3种选择；C与A不同色时，C有2种选择的颜色，D有2种颜色可供选择，从而对C、D染色有1×3＋2×2＝7种染色方法。由乘法原理，总的染色方法数是60×7＝420种评注图中的连接状况是本质条件，而是否空间图形则无关紧要，试看下面的两个问题，尽管与例5表述方式不同，但具有相同的数学模型，所以都可以转化为例5来解决。您不妨一试。（1）用五种颜色给图中的5个车站的候车牌A、B、

8、C、D、E染色，要求相邻两个车站间的候车牌的颜色不同，有多少种不同的染色方法（图6）（2）如图7所示为一张有5个行政区划的地图，今要用5种颜色给地图着色，要求相邻的区域不同色，共有多少种方案？三、线段染色问题，要注意对各条线段依次讨论，主要方法有：（1）根据共用了多少种颜色分类讨论；（1）