什么是染色问题.doc

《什么是染色问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、什么是染色问题来源：本站原创文章作者：奥数网教研组2009-09-1820:30:28[标签：逻辑推理答案数学报考技巧竞赛答案]奥数精华资讯免费订阅　　这里的染色问题不是要求如何染色，然后问有多少种染色方法的那类题目，它指的是一种解题方法。染色方法是一种将题目研究对象分类的形象化方法，通过将问题中的对象适当染色，我们可以更形象地观察分析出其中所蕴含的关系，再经过一定的逻辑推理，便能得出问题的答案。这类问题不需要太多的数学知识，但技巧性、逻辑性较强，要注意学会几种典型的染色方法。染色问题是数奥解题中的难点，这类问

2、题初看起来好像无从着手，其实只要认真思考问题也很容易解决，下面就染色问题的解题思路说一下。下图是由14个大小相同的方格组成的图形。试问能不能剪裁成7个由相邻两方格组成的长方形？    分析：将这14个小方格黑白相间染色（见下图），有8个黑格，6个白格。相邻两个方格必然是一黑一白，如果能剪裁成7个小长方形，那么14个格应当是黑、白各7个，与实际情况不符，所以不能剪裁成7个由相邻两个方格组成的长方形。下图是学校素质教育成果展览会的展室，每两个相邻的展室之间都有门相通。有一个人打算从A室开始依次而入，不重复地看过各室

3、展览之后，仍回到A室，问他的目的能否达到，为什么？    分析：采用染色法。如右下图，共有9个展览室，对这9个展览室，黑白相间地进行染色，从白室A出发走过第1扇门必至黑室，再由黑室走过第2扇门至白室，由于不重复地走遍每一间展览室，因此将走过黑白相间的8个展览室，再回到白室A，共走过9扇门。由于走过奇数次门至黑室，走过偶数次门至白室。现在，走过9扇门，必至黑室，所以无法回到原来的白室A。下图是由40个小正方形组成的图形，能否将它剪裁成20个相同的长方形？    　　分析：将40个小正方形剪裁成20个相同的长方形，

4、就是将图形分割成20个1×2的小长方形，将图形黑白相间染色后，发现有21黑，19白，黑、白格数目不等，而1×2的小长方形覆盖的总是黑白格各一个，所以不可能做到。　　图一　　首先，拿到一道题先认真观察，看这个题的突破点。什么是染色问题的突破点呢？那就是找染色区域中的一个最多，这个最多是指一个区域，其他区域与它连接的最多。例如图一中A区域A与B、C、D、E、F连接最广所以A为特殊区域。找到这个区域问题就容易解决了。这个区域可以任意添色就是染最多的颜色。本题中有4种颜色那么A可以染4种颜色了。完成这个事件需要A、B、

5、C、D、E、F6步所以用乘法原理。这道题找到了最特殊的A区域第二特殊区域和第三区域的确定也就容易了，C区域是与A相连，连接区域的数量仅次于A区域图一中的C和E区域都可以做第二个特殊区域了，但只能选一个，我们把C当成第二特殊的区域，则C可以染3种颜色。区域B跟A、C相连那么B可以染2种。D与A、C、E相连则只能选1种，对吗？我们仔细观察，按顺序说A----4，C------3，B-------2，D则连接A、C当A选色后C有3种可能，D在A、C选色后只有2种可能。E连接A、D也有两种可能。F也是连接着A、E有两种

6、可能。这道题就解出来了。有4×3×2×2×2=96种可能。这道题跟以下一道题有异曲同工之效，大家不妨一起看下图二。　　图二　　图中A与B、C相连有4种染色方式，为第一特殊区域。而B是与A相连的第二特殊区域（切记，此时选第二特殊区域，乃是跟第一特殊区域相连的一个区域）B有3种可能，C连接A、B则有2种可能，D连接B、C则有2种可能，同理E也有2种可能。所以此题有4×3×2×2×2=96种可能的染色。再来看一个稍微复杂点的问题如图三　　图三　　图中A有5种染色方式C------4，B-----3，D-----3，E

7、------3，F------3，G------3。这道题首先应当注意染色的顺序，先选第一特殊区域，再看跟A相连的区域中的第二特殊区域。还有一道更复杂的题，　　图四　　有5种颜色，图中个区域染不同的颜色，问有几种染色方式。还依照前面的思路过程解，首先看哪个区域是图中与其他区域相连最多的当成第一特殊区域，A为这个区域，其次为B，C和D为对称的哪个为第三特殊区域都可以，我们把D看成第三特殊区域，最后为C、E、F。分好各个区域就开始解题，A有5种颜色可以用，B则有4种，D有3种，C则有2种，F就复杂了，它的颜色受制于

8、E、C，则E跟C相同的有2种颜色可以选（因为C有2种颜色选择），跟C不同的有4种颜色选择（因为A、D的颜色确定了，E有5-2=3种，则E与C的搭配有2×3=6种颜色可以选择，E不考虑与C相同则有6-2=4种颜色可以选择），。所以E和C的颜色确定了，最后考虑F，若E和C同色，则F有5-2=3种颜色可以选择，若E和C异色则F有5-3=2种颜色选择。那么当E和C同色时F有2×3=6种可以选择