圖的m-着色判定問題
給定無向連通圖G和m種不同的顔色。用這些顔色為圖G的各頂點着色，每個頂點着一種顔色，是否有一種着色法使G中任意相鄰的2個頂點着不同顔色?
圖的m-着色優化問題
若一個圖最少需要m種顔色才能使圖中任意相鄰的2個頂點着不同顔色，則稱這個數m為該圖的色數。求一個圖的最小色數m的問題稱為m-着色優化問題。
解的長度是固定的，n。若x為本問題的一個解，則x[i]表示第i個節點的塗色編号。
可以将m種顔色看作每個節點的狀态空間。每到一個節點，周遊所有顔色，剪枝，回溯。
不難看出，可以套用回溯法子集樹模闆。
本文轉自羅兵部落格園部落格，原文連結：http://www.cnblogs.com/hhh5460/p/6930276.html，如需轉載請自行聯系原作者