Coloring

Coloring

替一張圖的各個元件都塗上顏色,並規定相鄰元件不可同色。一張圖的上色情形,稱做一種「著色」。

根據元件的不同,著色可分為許多種類型,例如點著色(vertex coloring)、邊著色(edge coloring)、面著色(face coloring)。以下只討論點著色:替一張圖上的每個點塗上顏色,並規定以邊相連的相鄰兩點不可同色。

【註:英文的「Coloring」為名詞。至於中文的「著色」實為動詞,而非名詞。為求文義順暢,以下內容把「著色」二字做為動詞。】

chromatic number

中譯「著色數」、「最小著色數」,著色一張圖至少所需要的顏色種類數目;換個方式說,用「著色數」種顏色,就足以著色一張圖。數學領域中把一張圖G的最小著色數標記為χ(G)。

當G沒有點和邊,χ(G) = 0。
當G沒有邊,χ(G) ≦ 1。
當G為二分圖(Bipartite Graph),χ(G) ≦ 2。
當G為平面圖(Planar Graph),χ(G) ≦ 4。(四色定理)
當G為完全圖(Complete Graph),χ(G) = V。

除了一些特例之外,要找出一張圖的最小著色數是NP-Hard問題。

k-colorable

一張圖若能以k種顏色著色,則稱這張圖為k-colorable。要確定一張圖是不是k-colorable是NP-Complete問題。

這裡提供一些跟著色有關的題目。

UVa 193 10004

Vertex Coloring: Welsh-Powell Algorithm

Welsh-Powell Algorithm

找出一張圖的其中一種著色,不限制顏色用量。

演算法

一個很簡單的Greedy演算法。首先把圖上每個點,依照degree由大到小排序,然後一一塗色。每一個點都先嘗試塗第一種顏色,若牴觸了已塗色的點,就換下一種顏色,直到顏色不牴觸為止。

這個演算法不保證著色數最小。

時間複雜度

每個點的度數範圍都只有0到V-1(不考慮多重的邊、不考慮自己連向自己的邊),故排序時可以採用Counting Sort,時間複雜度是O(V)。

每個點都著色的時間複雜度等同一次Graph Traversal的時間,如果圖的資料結構為adjacency matrix就是O(V^2),如果圖的資料結構為adjacency lists就是O(V+E)。

找出其中一種著色(adjacency matrix)

UVa 10471

Four Color Theorem

Four Color Theorem

四色定理。給定一張真實的地圖,是否能用四種顏色,就把這張地圖上的每塊區域都塗上顏色,並且相鄰的區域不得同顏色。兩塊區域僅以點接觸,則不算相鄰;兩塊區域以邊接觸,才算是相鄰。

這樣的一張地圖其實可以化做圖論中的平面圖(planar graph),平面圖的定義是沒有重疊的邊的一張圖;另外要是我們移動圖上的點和邊,而讓邊不重疊,如此也算是一張平面圖。

證明

據說是超級難證的。這裡僅提供一些我的想法,不知道正不正確就是了。

甲、零個點、一個點、兩個點、三個點、四個點的圖,每個點分別塗一種顏色也不會超過四種顏色,所以應該不太需要證明了。

乙、點著色的問題,圖上的邊越多,限制就越多。完全圖(complete graph)的邊是最多的,所以只要完全圖可以解決,那麼只要從完全圖上刪掉幾條邊,其他邊比較少的圖也都可以解決了。因此,這裡我們考慮一下四個點的完全圖。

丙、由於點的編號順序是無所謂的,不失一般性,這裡我們規定前三點是最外圍的點,而之後的點皆會落在前三點所構成的範圍裡面。四個點一共將整個範圍切成四塊區域。(有一個特例是點剛好在邊上,留待最後討論。)

丁、第五點會落在這四塊區域的其中一塊。當然依照我們的順序規定,第五點是不可能落在第四塊區域的。若是第五點落在第一塊區域,那麼就將第五點塗上在他外邊對頂的那個點的顏色。其他區域也是類似的。

戊、決定第五點後,以Divide and Conquer的觀點來看,構成了一個子問題。其他的區域也還是可以再放入點。放好所有點之後,只要刪除了其中的邊,就可以做出任意一種平面圖了。

己、之前有個點在邊上的特例還沒解決。如果把點放在邊上面,可以歸類成三種情形:甲、放在最外圍的邊,乙、放在裡面的邊,但是邊的兩邊區域能容忍的顏色不相同,丙、放在裡面的邊,邊的兩邊能容忍的顏色相同。其中甲和丙都是合法操作,而乙則是不合法操作,可由別的方式來做出一樣的圖。

庚、最後再提供一種想法:被分割的區域們其實又形成了一個四色圖問題。

以上就是我想到的證明。謝謝收看。