圖著色問題（Graph Coloring Problem, GCP）又稱著色問題，是最著名的NP-完全問題之一。它涉及的是如何將圖的頂點著色，使得相鄰頂點顏色不同，并且使用的顏色數盡可能少。
簡介
圖的m-著色判定問題——給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色，是否有一種著色法使G中任意相鄰的2個頂點著不同顏色。
圖的m-著色優化問題——若一個圖最少需要m種顏色才能使圖中任意相鄰的2個頂點著不同顏色，則稱這個數m為該圖的色數。求一個圖的最小色數m的問題稱為m-著色優化問題。
路線著色問題
G是一個有限有向圖并且G的每個頂點的出度都是k。G的一個同步著色滿足以下兩個條件：
1.G的每個頂點有且只有一條出邊被染成了1到k之間的某種顏色。
2.G的每個頂點都對應一種走法，不管你從哪里出發，按該走法走，最后都結束在該頂點。
有向圖G存在同步著色的必要條件是G是強連通而且是非周期的。一個有向圖是非周期的是指該圖中包含的所有環的長度沒有大于1的公約數。路線著色定理這兩個條件(強連通和是非周期)也是充分的。也就是說,有向圖G存在同步著色當且僅當G是強連通而且是非周期的。
道路著色問題（Road Coloring Problem）是圖論中最著名的猜想之一。通俗的說，這個猜想認為，可以繪制一張“萬能地圖”，指導人們到達某一目的地，不管他們原來在什么位置。這個猜想最近被以色列數學家艾夫拉漢· 特雷特曼(Avraham Trahtman)在2007年9月證明。
特雷特曼在數學上的這一成果極為令人矚目，英國《獨立報》為此事專門發表了一篇題為“身無分文的移民成了數學超級明星”的文章，給予了高度的評價。
算法
點著色問題有簡單的時間復雜度為O(3^n)的算法，即設f(S)表示集合的色數。
算法描述
color[n]存儲n個頂點的著色方案，可以選擇的顏色為1到m。
當t=1時，對當前第t個頂點開始著色：若t>n，則已求得一個解，輸出著色方案即可。否則，依次對頂點t著色1-m， 若t與所有其它相鄰頂點無顏色沖突，則繼續為下一頂點著色；否則，回溯，測試下一顏色。
寄存器分配技術
利用相交圖（interference graph）來表示程序變量的生命期是否相交，將寄存器分配給變量的問題，可近似地看成是給相交圖著色：相交圖中，相交的節點不能著同一顏色；每一種顏色對應一個寄存器。Chaitin等人最早提出了基于圖著色的寄存器分配方法其著色思路采用了Kempe的著色方法，即，任意一個鄰居節點數目少于k的節點，都能夠被k著色。判斷一個圖是否能夠被k(k>=3)種顏色著色，即k著色問題，被Karp證明是一個NP-complete問題。
但是，寄存器分配不僅僅是圖著色的問題。當寄存器數目不足以分配某些變量時，就必須將這些變量溢出到內存中，該過程稱為spill。最小化溢出代價的問題，也是一個NPcomplete問題。如果簡化該問題——假設所有溢出代價相等，那么最小化溢出代價的問題，等價于k著色問題，仍然是NP-complete問題。
此外，若兩個變量的生命期僅因為在同一個拷貝指令中而相鄰，那么，通過將這兩個變量分配到同一個寄存器，就可以消除該拷貝指令，成為coalescing。這個方向的努力在Chaitin的文章以后的1/4個世紀，成為推動寄存器分配的主要動力之一，涌現出了包括aggressive coalescing,conservative coalescing和optimistic coalescing。但是，將兩個變量分配到同一個寄存器，等價于將這兩個變量合并成同一個變量，生命期合并，因而會加劇相交圖的聚簇現象，降低相交圖的可著色性。Bouchez等人證明了coalescing問題都是NP-complete的。
為降低相交圖的聚簇現象，提高相交圖的可著色性，可通過將變量拷貝給一個臨時變量，并將以后對該變量的使用替換成對該臨時變量的使用，從而將一變量的生命期分解成兩個變量的生命期，稱為live range splitting。顯然，這是一個與coalescing的作用相反的過程。Bouchez等人考慮了該方法的復雜度。
此外，寄存器分配還需要考慮寄存器別名(aliasing)和預著色(pre-coloring)的問題。寄存器別名是指，在某些體系結構中，一個寄存器的賦值可能會影響到另外一個寄存器。比如，在x86中，對AX寄存器的賦值，會影響AL和AH寄存器。預著色是指，某些變量必須被分配到特定的寄存器。比如，許多體系結構會采用特定寄存器來傳遞函數參數。
George和Appel發展了Chaitin的算法，更好地考慮了coalescing過程和賦值過程，以及各過程之間的迭代，在基于圖著色的寄存器分配方法中具有廣泛的影響。
參考資料 >