染色問題的解題思路
染色問題是數(shù)奧解題中的難點(diǎn)，這類問題初看起來好像無從著手，其實(shí)只要認(rèn)真思考問題也很容易解決，下面就染色問題的解題思路說一下。
圖一
首先，拿到一道題先認(rèn)真觀察，看這個(gè)題的突破點(diǎn)。什么是染色問題的突破點(diǎn)呢？那就是找染色區(qū)域中的一個(gè)最多，這個(gè)最多是指一個(gè)區(qū)域，其他區(qū)域與它連接 的最多。例如圖一中A區(qū)域A與B、C、D、E、 F連接最廣所以A為特殊區(qū)域。找到這個(gè)區(qū)域問題就容易解決了。這個(gè)區(qū)域可以任意添色就是染最多的顏色。本題中有4種顏色那么A可以染4種顏色了。完成這個(gè) 事件需要A、B、C、D、E、F6步所以用乘法原理。這道題找到了最特殊的A區(qū)域第二特殊區(qū)域和第三區(qū)域的確定也就容易了，C區(qū)域是與A相連，連接區(qū)域的 數(shù)量僅次于A區(qū)域圖一中的C和E區(qū)域都可以做第二個(gè)特殊區(qū)域了，但只能選一個(gè)，我們把C當(dāng)成第二特殊的區(qū)域，則C可以染3種顏色。區(qū)域B跟A、C相連那么 B可以染2種。D與A、C、E相連則只能選1種，對(duì)嗎？我們仔細(xì)觀察，按順序說A----4，C------3，B-------2，D則連接A、C當(dāng)A 選色后C有3種可能，D在A、C選色后只有2種可能。E連接A、D也有兩種可能。F也是連接著A、E有兩種可能。這道題就解出來了。有 4×3×2×2×2=96種可能。這道題跟以下一道題有異曲同工之效，大家不妨一起看下圖二。
圖二
圖中A與B、C相連有4種染色方式，為第一特殊區(qū)域。而B是與A相連的第二特殊區(qū)域（切記，此時(shí)選第二特殊區(qū)域，乃是跟第一特殊區(qū)域相連的一個(gè)區(qū) 域）B有3種可能，C連接A、B則有2種可能，D連接B、C則有2種可能，同理E也有2種可能。所以此題有4×3×2×2×2=96種可能的染色。再來看 一個(gè)稍微復(fù)雜點(diǎn)的問題如圖三
圖三
圖中A有5種染色方式C------ 4，B-----3，D-----3，E------3，F(xiàn)------3，G------3。這道題首先應(yīng)當(dāng)注意染色的順序，先選第一特殊區(qū)域，再看跟 A相連的區(qū)域中的第二特殊區(qū)域。還有一道更復(fù)雜的題，
圖四
有5種顏色，圖中個(gè)區(qū)域染不同的顏色，問有幾種染色方式。還依照前面的思路過程解，首先看哪個(gè)區(qū)域是圖中與其他區(qū)域相連最多的當(dāng)成第一特殊區(qū)域，A 為這個(gè)區(qū)域，其次為B，C和D為對(duì)稱的哪個(gè)為第三特殊區(qū)域都可以，我們把D看成第三特殊區(qū)域，最后為C、E、F。分好各個(gè)區(qū)域就開始解題，A有5種顏色可 以用，B則有4種，D有3種，C則有2種，F(xiàn)就復(fù)雜了，它的顏色受制于E、C，則E跟C相同的有2種顏色可以選（因?yàn)镃有2種顏色選擇），跟C不同的有4 種顏色選擇（因?yàn)锳、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種顏色選擇。那么當(dāng)E和C同 色時(shí)F有2×3=6種可以選擇，當(dāng)E和C異色是則F有4×2=8種可以選擇，那么這道題就出來了染色的方式有 5×4×3×2×3+5×4×3×4×2=840種方式。下面再簡略的看一道此類問題，如圖四，4種顏色相鄰的區(qū)域染不同的顏色，有幾種不同的染色方式。 還按照以前的思索方式，首先選第一特殊區(qū)域，則A為所選，A有4種染色方式，其次，C為第二特殊區(qū)域，我們可以按
圖五
A、C、B、E、D的方式解。則C有3種染色方式。則B有2種染色方式，E跟B對(duì)稱則E跟B相同則有2種染色方式，E和B不同則有則有2種染色方式。 則E的染色方式為2×2=4。則D的染色依靠B、E，那么B、E同色B、E有2種方式，不同色B、E有4-2=2種方式，D的染色依靠B、E的染色，若 B、E同色則D有4-2=2種染色方式，若B、E不同則D有4-3=1種方式，那么在B、E同色時(shí)D染色方式有2×2=4，在B、E異色時(shí)D有 2×1=2種，則依據(jù)上面的思路我們可以求出此題的解4×3×2×2+4×3×2×1=48+24=72種方式。
總之，染色問題也有路可循，分清了問題中的第一特殊區(qū)域，以及依次的各個(gè)區(qū)域問題就迎刃而解了。其中最關(guān)鍵的部分是找特殊區(qū)域，不要找錯(cuò)了，如例四若讓B 當(dāng)?shù)诙厥鈪^(qū)域就不會(huì)得到正確答案了。
