染色問題的解題策略

染色問題的解題策略

染色問題來源於"四色定理"，由於染色問題試題新穎，包含豐富的數學思想方法，解題方法靈活多變.本文擬從四個方面總結染色問題的解決策略.

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]種方法.

練習：同室四個人各寫一張賀年卡，先集中起來，然後每人從中拿出一張賀年卡，恰好都不是自己的賀年卡，有多少種不同的拿法？