“捆綁法”巧解一類染色問題

王業和

【摘要】染色問題是高中數學排列組合中重要問題，散見于包括高考等在內的各類考試之中.染色問題基本規則要求是相鄰區域不能同色，不相鄰區域可以同色.常見的解法是分步考慮，按照區域順序依次求出各區域染色種數，再相乘即可.但由于要考慮不相鄰區域同色不同色，故解題過程中既要分類，又要分步，故而容易重復或遺漏，以至于許多學生感到迷惑.筆者在教學中采取“捆綁法”巧妙地解決這類問題，學生易懂易會，效果非常好.

【關鍵詞】捆綁法；染色；分類

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種.

雖然使用“捆綁法”染色條理清晰，但是一定要先依據那些區域可以同色，準確地判斷出可以使用顏色種數的各種情況，不能遺漏，否則可能導致錯誤.