染色问题的计数方法

《染色问题的计数方法》由会员分享，可在线阅读，更多相关《染色问题的计数方法（9页珍藏版）》请在装配图网上搜索。

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

2、法共有4X3X2X2=48种2. 根据共用了多少种颜色分类讨论，分别计算出各种情形的种数，再用加法原理求出不同年拾方法种数。例2 （2003年全国高考题）如图2，一个地区分为5个行 政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有多少种?分析依题意至少要(1)选用3种颜色。当选用三种颜色时，区域2与4必须同色，区域3与5必须同色，有3种。(2)4当用四种颜色时，若区域2与4同色，则区域3与5不同色，有A4种；若区域3与5同色，则区域2与44不同色，有A4种，故用四种颜色时共有2A4种。44由加法原理可知满足题意的着色方法共有A3 +2 A 4 =2

3、4 +442X24=72 种。根据某两个不相邻区域是否同色分类讨论，从某两个不相邻区域同色与不同色入手，分别计算出两种情形 的种数，再用加法原理求出不同染色方法数。例3用红、黄、蓝、白、黑五种颜色涂在“田”字形的四 个小方格内（图3），每格涂一种颜色，相邻的两格涂不同的 颜色，如果颜色可以反复使用，共有多少种不同的涂色方法?2134图3（1）四格涂不同的颜色，方法数为& ；5(2) 有且仅有两格涂相同的颜色，即只有一组对角小方格涂相同颜色，涂法种数为2Ci A2；(3) 两组对角小方格涂相同颜色，涂法种数为A2。因此，所求的涂法种数为A2 +2Ci A2 + A2 =260种3. 根据相间区域

4、使用颜色的种类分类讨论例4如图4, 一个六边形的6个区域A、B、C、D、E、F,现给这6个区域着色，要求同一区域染同一种颜色，相邻的两个区域不得使用同一颜色，现有4种不同的颜色可供选择，则有多少种不同的着色方法。解：(1)当相间区域A、C、E着同一种颜色时，有4 种着色方法，此时，B、D、F各有3种着色方法故有4X3X 3X3 = 108种方法(2) 当相间区域A、C、E着两种不同颜色时，有C2A2种34着色方法，此时B、D、F有3X2X2种着色方法，故共有C2A234X3X2X2=432种着色方法。(4) 当相间区域A、C、E着三种不同颜色时，有A3种着色方法，此时B、D、F各有2种着色方法

5、，此时 4共有A3 X2X2X2=192种方法。4故总计有108+432+192=732种方法二点染色问题点染色问题，要注意对各点依次染色，主要方法有:(1)根 据共用了多少种颜色分类讨论；(2)根据相对顶点是否同色 分类讨论。例5将一个四棱锥S-ABCD的每个顶点染上一种颜色，并使同一条 棱的两端点异色，如果只有5种颜色可 供使用，那么不同的染色方法的总数是 多少？解法1满足题设条件的染色至少要 用三种颜色(1) 若恰用三种颜色，可先从五种颜色中任选一种 染顶点S，再从余下的四种颜色中任选两种染A、B、C、D 四点，此时只能A与C，B与D分别同色，故有CE2=60 种方法。(2) 若恰用四种

6、颜色，可先从五种颜色中任选一种 染顶点S，再从余下的四种颜色中任选两种染A与B，由于 A、B颜色可以交换，故有A2种染法；再从余下的两种颜色4种任选一种染D或C，而D与C中另一个只需染与其相对顶 点同色即可，故有CiAC C1 =240中方法。(3) 若恰用五种颜色，有A5 = 120种染法。综上，5满足题意的染色方法数为60+240+120=420种。方法唯一)，D与A、C、S不同色，有3种选择；C与A不 同色时，C有2种选择的颜色，D有2种颜色可供选择，从 而对C、D染色有1X3 + 2X2=7种染色方法。由乘法原理，总的染色方法数是60X7=420种评注 图中的连接状况是本质条件，而是否

7、空间图形则无关 紧要，试看下面的两个问题，尽管与例5表述方式不同，但 具有相同的数学模型，所以都可以转化为例5来解决。您不 妨一试。(1) 用五种颜色给图中的5个车 站的候车牌A、B、C、D、E染色， 要求相邻两个车站间的候车牌的颜 色不同，有多少种不同的染色方法(图6)(2) 如图7所示为一张有5个行政区划的地图，今要用5 种颜色给地图着色，要求相邻的区域不同色，共有多少种方 案？三、线段染色问题，要注意对各条线段依次讨论，主要方法有:（1）根据共用了多少种颜色分类讨论；（2）根据相对的线段是否同色分类讨论。例6用红、黄、蓝、白、四种颜色染矩形ABCD的四条边，每条边只染一种颜色，且使相邻两

8、边染不同的颜色， 如果颜色可能反复使用，共有多少种不同的染色方法（图8）解法1 （1）使用四种颜色有&种； 4（2）使用三种颜色染色，则必须将一组对边染成同色，故有C i C i A 2种； 423（3）使用两种颜色时，则两组对边 必须分别同色，有A 2种。4因此，所求的染色方法数为A4 + C1C1A2 + A2=84种解法2染色按AB-BC-CD-DA的顺序进行，对AB、BC染 色有4X3 = 12种染色方法。由于CD的颜色可能与AB同色或不同色，这影响到DA颜 色的选取方法数，故分类讨论：当CD与AB同色时，这时CD对颜色的选取方法唯一，则 DA有3种颜色可供选择；当CD与AB不同色时，

9、CD有2 种可供选择的颜色，DA有2种可供选择的颜色，从而对CD、 DA染色有1X3 + 2X2 = 7种染色方法。由乘法原理，总的染色方法数为12X7 = 84种。利用相同的 方法可解决例7例7中央电视台“正大综艺”节目的现场观众来自4个单位，分别在图9中4个区域内坐定。有4种不同的颜 色服装，每个区域的观众必须穿同种颜色的服装，且相邻两 个区域的颜色不同，不相邻区域颜色相同与否不受限制，那 么不同的着色方法0*共有多少种？例8用六种颜色给正四面体A-BCD的每条棱染色，要求每条棱只能染一种颜色且共顶点的棱染不同的颜色，问有多少种不同的染色方法（图10）分析 正四面体有三组对棱AB与CD、A

10、C与BD、AD与BC。满足题设条件的染色至少要用三种颜色。解 （1）若恰用三种颜色染色，则每组对棱必须染同一颜 色，而这三组间的颜色不同，故有A 3种方法。6（2）若恰用四种颜色染色，则三组对棱中有两组对棱的组内对棱同色，但组与组之间不同色，故有C .A 4种方法。 36（3）若恰用五种颜色染色，则三组对棱中有一组对棱染同 一种颜色，故有C1A5种方法。36（4）若恰用六种颜色染色，则有A6C6 种不同的方法。综上，满足题意的总的染色方法数为A3 + C1A + A6 =4080 种6366四面染色问题例9 （1996年全国高中数学联赛题）从给定的六种不同颜 色中选用若干种颜色，将一个正方体的

11、6个面染色，每两个 具有公共棱的面染成不同的颜色，则不同的染色方案共有多 少种？（注：如果我们对两个相同的正方体染色后，可以通过适当 翻转，使得两个正方体的上、下、左、右、前、后6个面对 应面的染色都相同，那么，我们就说这两个正方体的染色方 案相同）分析 显然，至少需要三种颜色，由于有多种不同情况，仍 应考虑利用加法原理分类、乘法原理分步进行讨论。解 根据共用了多少种不同的颜色分类讨论。（1）用了六种颜色，确定某种颜色（例如红色）所染面为 下底（根据题注，对此处的两种不同染色方案，这里的“第 一面”总是相同的），则上底颜色可有5种选择，在上、下底 己染好后，再确定其余4种颜色中的某一种所染面为左侧面， 则其余3个面有3!种染色方案，根据乘法原理ni = 5X3! =30种（2）用了五种颜色，选定五种颜色有C5 =6种方法，必有6两面同色（必为相对面），确定为上、下底面，其颜色可有5 种选择，再确定一种颜色为左侧面，此时的方法数取决于右 侧面的颜色，有3种选择（前后面可通过翻转交换）n2= C5 X5X3 = 90(3) 用了四种颜色，仿上分析可得n3= CC2=90(4) 用了三种颜色，n4= C3=20故总的染色方案有n=n1+ n2 +n3 +n4 = 230种。