“捆绑法”巧解一类染色问题

王业和

【摘要】染色问题是高中数学排列组合中重要问题，散见于包括高考等在内的各类考试之中.染色问题基本规则要求是相邻区域不能同色，不相邻区域可以同色.常见的解法是分步考虑，按照区域顺序依次求出各区域染色种数，再相乘即可.但由于要考虑不相邻区域同色不同色，故解题过程中既要分类，又要分步，故而容易重复或遗漏，以至于许多学生感到迷惑.笔者在教学中采取“捆绑法”巧妙地解决这类问题，学生易懂易会，效果非常好.

【关键词】捆绑法；染色；分类

1“捆绑法”解决染色问题的关键点

一是总共有几种颜色，并根据题意准确地判断这些颜色是可以选用还是必须要全部使用.

二是在颜色可以选用的情况下，分析图形中有哪些区域可以同色，将可以同色的两区域“捆绑”一起；再分析出给图形染色最少需要几种颜色，从而按各种可能使用的颜色种数列出来.

三是按使用颜色种数依次分类，在可以同色情况中选择适当情况，计算出相应染色方法，再相加即可.

这种“捆绑法”染色其实只需要使用分类思想，比传统按区域分步解法条理清晰，简洁明了，下面举几例.

图1

2例题赏析

例1用6种不同颜色给如图1所示的六个区域染色，要求相邻区域不同色，则不同的染色方法有种.

解由题意可知有6种颜色可供选用.考虑到可同色区域有（3，5）、（3，6）、（4，5）、（4，6）.故最少可以用4种颜色，最多可以用6种颜色.也就是说染色方法有3类，分别用4，5，6种不同颜色染色.

若用6种颜色，则有A66=720；若用5种颜色，则必须有一对不相邻区域染同色，所以应在（3，5）、（3，6）、（4，5）、（4，6）中选一个染同色，故共有C56C14A55=2880;若用4种颜色，则必须有两对不相邻区域染同色，所以应先在（3，5）、（3，6）中选一种，而（4，5）、（4，6）中唯一选择一种染同色；或者应先在（4，5）、（4，6）中选一种，而（3，5）、（3，6）中唯一选择一种染同色，则有C46C12A44=720，故共有4320种.

图2

例2用5种不同颜色给图2中各区域染色，要求相邻区域不同色，则不同的染色方法有种.

解由题意有5种颜色可选用，其中可同色的区域有（D，F）、（C，E）、（B，E）、（B，F），至少用4种颜色，故可用4，5种不同颜色染色.若用4种颜色，则必有两对不相邻区域须染同色，即（C，E）、（D，F）或者（C，E）、（B，F）；或者（D，F）、（B，E）三種情况，则有C45A44×3=360.若用5种颜色，则相邻可染同色（D，F）、（C，E）、（B，E）、（B，F）中必有一对须染同色，则有C14A55=480，故共有840种不同的染色方法.

图3

例3如图3，给7条线段的5个端点涂色，要想同一线段两端点不能同色，现有4种颜色可供选择，则不同的涂色种数为种.

解由题意两端点可同色所以的两点有（A，D）、（A，C）、（B，D），故可用4种不同颜色或3种不同颜色进行涂色.若用4种不同颜色涂色，则必有两个可涂同色点涂同色，有C13A44=72;若用3种不同颜色涂色，则（A，C）、（B，D）必须分别涂同色，有C34A33=24，故共有96种.

虽然使用“捆绑法”染色条理清晰，但是一定要先依据那些区域可以同色，准确地判断出可以使用颜色种数的各种情况，不能遗漏，否则可能导致错误.