多面體染色

問題定義

多面體染色的常見描述為：對於一個正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個置換
以頂點與對面的中心連線為軸按反時針方向旋轉±120度	置換(BCD)與(BDC)。置換(ACD)與(ADC)，置換(ABD)及(ADB)，(ABC)及(ACB )所對應的旋轉。	8個置換
以正四面體的3對對邊之中點聯線為旋轉軸旋轉180度	(AB)(CD)，(AC)(BD)，(AD)(BC)	3個置換