圖著色問題

"一，路線著色問題是圖論中最著名的猜想之一。 有向圖G存在同步著色的必要條件是G是強連通而且是非周期的。 也就是說

圖著色問題（Graph Coloring Problem, GCP）　又稱著色問題，是最著名的NP-完全問題之一。一，路線著色問題

是圖論中最著名的猜想之一。通俗的說，這個猜想認為，可以繪製一張“萬能地圖”，指導人們到達某一目的地，不管他們原來在什麼位置。這個猜想最近被以色列數學家Avraham Trahtman在2007年9月證明。
舉個例子。在維基網給出的圖例中，如果按圖中所示方式將16條邊著色，那么不管你從哪裡出發，按照“藍紅紅藍紅紅藍紅紅”的路線走9步，你最後一定達到黃色頂點。路線著色定理就是說在滿足一定條件的有向圖中，這樣的著色方式一定存在。嚴格的數學描述如下。我們首先來定義同步著色。G是一個有限有向圖並且G的每個頂點的出度都是k。G的一個同步著色滿足以下兩個條件：1)G的每個頂點有且只有一條出邊被染成了1到k之間的某種顏色；2)G的每個頂點都對應一種走法，不管你從哪裡出發，按該走法走，最後都結束在該頂點。有向圖G存在同步著色的必要條件是G是強連通而且是非周期的。一個有向圖是非周期的是指該圖中包含的所有環的長度沒有大於1的公約數。路線著色定理這兩個條件(強連通和是非周期)也是充分的。也就是說,有向圖G存在同步著色若且唯若G是強連通而且是非周期的。