- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
染色问题的计数方法染色问题的计数方法
染色问题的计数方法
河北张家口市第三中学 王潇
与染色问题有关的试题新颖有趣,其中包含着丰富的数学思想,染色问题,解题方法技巧性强且灵活多变,故这类问题有利于培养学生的创新思维能力,分析问题与观察问题的能力,有利于开发学生的智力。
区域染色问题
根据乘法原理,对各个区域分步染色,这是处理这类问题的基本的方法。
要用四种颜色给四川、青藏、西藏、云南四省(区)的地图染色(图1)每一省(区)一种颜色,只要求相邻的省(区)不同色,则不同染色的方法有多少种?
分析 先给四川染色有4种方法,再给青海染色有3种方法,接着给西藏染色有2种方法,最后给云南染色有2种方法,根据乘法原理,不同的染色方法共有4×3×2×2=48种
根据共用了多少种颜色分类讨论,分别计算出各种情形的种数,再用加法原理求出不同年拾方法种数。
例2 (2003年全国高考题)如图2,一个地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,现有4种颜色可供选择,则不同的着色方法共有多少种?
分析 依题意至少要选用3种颜色。
当选用三种颜色时,区域2与4必须同色,区域3与5必须同色,有种。
当用四种颜色时,若区域2与4同色,则区域3与5不同色,有种;若区域3与5同色,则区域2与4不同色,有种,故用四种颜色时共有2种。
由加法原理可知满足题意的着色方法共有+2=24+2×24=72种。
根据某两个不相邻区域是否同色分类讨论,从某两个不相邻区域同色与不同色入手,分别计算出两种情形的种数,再用加法原理求出不同染色方法数。
例3 用红、黄、蓝、白、黑五种颜色涂在“田”字形的四个小方格内(图3),每格涂一种颜色,相邻的两格涂不同的颜色,如果颜色可以反复使用,共有多少种不同的涂色方法?
(1)四格涂不同的颜色,方法数为;
(2)有且仅有两格涂相同的颜色,即只有一组对角小方格涂相同颜色,涂法种数为2;
两组对角小方格涂相同颜色,涂法种数为。因此,所求的涂法种数为+2+=260种
根据相间区域使用颜色的种类分类讨论
例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种着色方法。
当相间区域A、C、E着三种不同颜色时,有种着色方法,此时B、D、F各有2种着色方法,此时共有×2×2×2=192种方法。
故总计有108+432+192=732种方法
二 点染色问题
点染色问题,要注意对各点依次染色,主要方法有:(1)根据共用了多少种颜色分类讨论;(2)根据相对顶点是否同色分类讨论。
将一个四棱锥S-ABCD的每个顶点染上一种颜色,并使同一条棱的两端点异色,如果只有5种颜色可供使用,那么不同的染色方法的总数是多少?
解法1 满足题设条件的染色至少要用三种颜色
若恰用三种颜色,可先从五种颜色中任选一种染顶点S,再从余下的四种颜色中任选两种染A、B、C、D四点,,此时只能A与C,B与D分别同色,故有=60种方法。
若恰用四种颜色,可先从五种颜色中任选一种染顶点S,再从余下的四种颜色中任选两种染A与B,由于A、B颜色可以交换,故有种染法;再从余下的两种颜色种任选一种染D或C,而D与C中另一个只需染与其相对顶点同色即可,故有=240中方法。
若恰用五种颜色,有=120种染法。综上,满足题意的染色方法数为60+240+120=420种。
解法2 设想染色按S-A-B-C-D的顺序进行,对S、A、B染色,有5×4×3=60种染色方法。由于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来解决。您不妨一试。
用五种颜色给图中的5个车站的候车牌A、B、C、D、E染色,要求相邻两个车站间的候车牌的颜色不同,有多少
您可能关注的文档
- 某挡墙加固工程施工方案.doc
- 某排水工程施工组织设计p.doc
- 某投资公司财务制度.doc
- 某支洞施工方案.doc
- 某文化产业园策划案.doc
- 某教学楼造价指标分析.doc
- 某机房防雷工程施工方案.doc
- 某文化传播公司商业计划书.doc
- 某教学楼施工组织设计.doc
- 某本科学院毕业设计课题二.doc
- 区委书记、市国资委党委领导班子2025年组织生活会对照“四个带头”含反面典型案例举一反三剖析方面检查材料【两篇文】.docx
- 局党组书记、市国资委党委领导班子2025年组织生活会对照“四个带头”含反面典型案例举一反三剖析方面个人检查材料2篇文.docx
- 市交通运输局局长2025年专题生活会对照“四个带头”含落实意识形态工作责任制方面个人对照检查发言提纲与检察院领导班子“四个带头”检查材料【2篇文】.docx
- 市投资促进局党支部书记2025年组织生活会对照“四个带头”个人对照检查发言材料与党组书记“四个带头”个人对照检查材料(内蒙古地区四个对照,反面典型案例检视剖析)【2篇文】.docx
- 市教育局党委副书记、市国资委党委领导班子2025年“四个带头”个人对照检查发言材料(上年度整改+个人事项+典型事例剖析)2篇文.docx
- 2025年专题生活会“四个带头”方面对照检视材料(问题+原因+措施+意识形态)与纪检委员专题生活会“四个带头”方面个人对照检查材料【2篇文】.docx
- 检察院领导班子2025年专题生活会对照“四个带头”检查材料与县司法局专题生活会党组书记个人对照“四个带头”对照检查材料(含反面典型案例全面剖析)2篇文.docx
- 市机关事务局党支部书记、局党组书记2025年组织生活会对照“四个带头”含反面典型案例举一反三剖析方面个人发言材料、检查材料【2篇文】.docx
- 2025年领导干部专题生活会“四个带头”对照检查材料与市审计局领导班子专题生活会“四个带头”含反面典型案例剖析对照检查材料2篇文.docx
- 2025年县司法局专题民主生活会班子围绕“4个带头”对照检查材料与反面典型案例回顾与剖析对照检查发言材料2篇文.docx
文档评论(0)