多面體染色

多面體染色是組合數學中一類常見問題。其大致題意為：對於一個正多面體，用一定種類的顏色對其表面、頂點或（和）邊進行染色。若兩種染色方案可以通過旋轉對應，則視其為同一染色方案。題目希望求得對於給定條件下，不同染色可能的方案數目。注意，本文所指多面體染色和圖著色問題為兩類完全不同的問題。

多面體染色問題一般可通過波利亞定理與burnside引理求解。

基本介紹

• 中文名：多面體染色
• 外文名：Polyhedron Coloring

問題定義

多面體染色的常見描述為：對於一個正N面體，用M種不同顏色對其表面、頂點或（和）邊進行染色。若兩種染色方案可以通過旋轉對應，則視其為同一染色方案。題目最終希望求得對於給定條件下，不同染色可能的方案數目。給定條件一般可包括：N與M的數值，每種顏色使用次數等等。

例1：正六面體的六個面分別用紅，藍兩種顏色著色，有多少方案？

解釋：此即為N=6，M=2時的標準題型。

例2：用六種不同顏色塗一正方體，一面一色，且每面顏色不同，會有多少種塗法？

解釋：該題目除了要求N=6，M=6外，還要求每種顏色只能使用一次。

例3：甲烷CH4的4個鍵任意用H(氫),Cl(氯),CH3(甲基), C2H5(乙基) 連線，有多少種方案？

解釋：甲烷為正四面體結構，若將四種化學集團視為四種不同“顏色”，該問題等價於正四面體的頂點進行四染色問題。

例4：在正六面體的每個面上任意做一條對角線，有多少方案？

解釋：在每個面上做一條對角線的方式有2種，可參考正六面體的表面-2著色問題。但需要注意，按照面心-面心的轉動軸轉±90 時，無不動圖象。

考慮到對稱性，所有可能的正多面體為：正四面體、正六面體、正八面體、正十二面體、正六十面體。此外，“足球“的染色也經常出現。

所有可能的正多面體

問題解法

多面體染色問題一般可以通過波利亞定理與burnside引理求解。詳細內容可參加相關文章。

其基本思路為：首先列出該正多面體所有可能的旋轉群，然後計算每個旋轉群內，不動點的數量（即在該種旋轉下，旋轉後顏色不改變的染色數）。然後利用burnside引理，將不動點的數量相加並除以旋轉群數量，即可得到解。在求解不動點個數時，一般需要用到波利亞定理或者指數型波利亞定理。即有：

若有 ，則：

問題解法

不同多面體可能的旋轉群可參考詞條：旋轉群以及。

問題解法

例題

例1：正六面體的六個面分別用紅，藍兩種顏色著色，有多少方案？

解：考慮正六面體轉動群中，頂點的置換：

根據Polya定理，

例2：用六種不同顏色塗一正方體，一面一色，且每面顏色不同，會有多少種塗法？

解：考慮正六面體轉動群中，面的置換：

置換類型	置換數量	不動點個數
不動置換	1個置換	6!個不動點
面面中心轉±90度	2*3個置換	無不動點
面面中心轉180度	3個置換	無不動點
棱中對棱中轉180度	6個置換	無不動點
對角線為軸轉±120度	2*4個置換	無不動點

根據Burnside引理， 個方案

例3：甲烷CH4的4個鍵任意用H(氫),Cl(氯),CH3(甲基), C2H5(乙基) 連線，有多少種方案？

解：考慮正四面體轉動群中，點的置換：

置換類型	置換解釋	置換數量	循環表示
不動旋轉	-	1個置換
以頂點與對面的中心連線為軸按反時針方向旋轉±120度	置換(BCD)與(BDC)。置換(ACD)與(ADC)，置換(ABD)及(ADB)，(ABC)及(ACB )所對應的旋轉。	8個置換
以正四面體的3對對邊之中點聯線為旋轉軸旋轉180度	(AB)(CD)，(AC)(BD)，(AD)(BC)	3個置換

因此，根據Polya定理，方案數為l = (4^4+8 * 4^2 + 3 * 4 ^2)/12 = 36

多面體