染色问题的解题策略

染色问题的解题策略

染色问题来源于"四色定理"，由于染色问题试题新颖，包含丰富的数学思想方法，解题方法灵活多变.本文拟从四个方面总结染色问题的解决策略.

1.按颜色个数分类解决

例1 如图1所示将一个侧棱互不相等的四棱锥S-ABCD的每个顶点染上一种颜色并使同一条棱的两端点异色,如果只有5种颜色可供使用,那么不同的染色方法总数是多少?

解：满足题设条件的染色最少要用3种颜色.

若恰用3种颜色,可先从5种颜色中任选一种染顶点S;再从余下的4种颜色中任选两种染A、B、C、D的两对顶点,共有C51A42=60种方法.

若恰用4种颜色,可先从5种颜色中任选一种染顶点S;再从余下的4种颜色中任选两种染A与B,注意A与B的颜色可以交换;再从余下的两种颜色中任选一种染C或D;最后剩下的一个顶点只需与其相对顶点同色即可,故有C51A42C21C21种方法.

若恰用5种颜色,则有A55=120种方法.

故由分类计数原理可知,共有60+240+120=420种染色方法.

2.按区域着色分步解决

例2：某城市在中心广场建造一个花圃，花圃分为6个部分（如图2），现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有 种（以数字作答）（2003年全国新课程卷）.

解：第一步先对中心区域1着色,有4种选择,第二步,对环形的5个区域2,3,4,5,6着色,如图所示,先对2着色,有三种选择,然后对4或5着色,分三类:2,4同色;2,5同色;2,4,5不同色.2,4同色时,3有两种选择,5有两种选择,6只有一种选择.共有4种选择;2,5同色时同样有4种选择;2,4,5不同色时,4,5可对调有两种,3和6都只能有一种选择.所以共有4×3×(4+4+ 2)=120种不同的方法.

3.通过变换，简化图形解决

对于例2，我们也可以先排区域1，有4种排法，然后把其余的5个区域视为一个圆环（如图3），沿圆环的一个边界将圆环展开，可以得到拉伸的5个空格（如右图4），本题等价于在5个空格中放入3种不同颜色的小球，相同颜色的小球不相邻，两端的两个空格所放两个小球颜色不同。这时题目变成了相对比较简单的问题，可以得到有30种不同的放法.

所以共有4×30＝120种不同的方法.

类似的方法还有很多,但如果提供的颜色和区域多一点,那么上面的办法就比较麻烦了.对于环形的区域染色问题.我们有没有更为简单化,更为系统的解决方法呢?

4.根据相互关系递推解决

上面图形通过变形为如图3所示.第一步染1区4种选择,第二步染2,3,4,5,6区.这是典型的环形区域染色问题，等价于用3种颜色染5个环形区域的问题（如图5）.现在我们运用递推关系来解决这类问题：设把m色染3区的染法数表示为a3,m色染4区的染法数表示为a4,,m色染n区的染法数表示为an,把它们看成一个数列，.先染1区,有3种选择,然后染2区,有2种选择,到了5区,有两种选择:5与1不同色和5与1同色,我们这样对待:如果不同色,则为a5,如果同色,则可以认为1,5同区, 我们把它当成只染了4个区域,就是a4,(如图6所示),所以

3×24=a5+a4，同理 3×23=a4+a3，而a3=A33=6

由上述三式得：a5=3×(24-23)+A33=30种.

所以所求方法种数＝4×30＝120种。

一般地，m色要染环形n个区域，相邻区域不同色，有an=(m-1)n+(-1)n[(m-1)3-Am3]种方法.

练习：同室四个人各写一张贺年卡，先集中起来，然后每人从中拿出一张贺年卡，恰好都不是自己的贺年卡，有多少种不同的拿法？