Coloring

Coloring

「著色」。一張圖的特定元件,通通塗上顏色,相鄰元件不可同色。

根據元件,著色有許多種類型:點著色、邊著色、面著色。

【註:英文「Coloring」為名詞,中文「著色」為動詞,英翻中致使文法不通,請多見諒。】

Vertex Coloring

Vertex Coloring

「點著色」。一張圖每個點塗上顏色,鄰點不同色。

Minimum Vertex Coloring / Chromatic Number

「最小點著色」是顏色數目最少的點著色,可能有許多種。「最小著色數」是最小點著色的顏色數目。NP-complete。

原圖的Minimum Vertex Coloring,等於補圖的Minimum Clique Cover。

k-Vertex Coloring

「k點著色」。使用k種顏色完成點著色。NP-complete。

特殊圖可推理出最小著色數的上限(保證可著色數的下限)。

G沒有點和邊:χ(G) = 0
G沒有邊:χ(G) ≤ 1
G為二分圖(Bipartite Graph):χ(G) ≤ 2
G為平面圖(Planar Graph):χ(G) ≤ 4(四色定理)
G為完全圖(Complete Graph):χ(G) = V
G的每個點的連接邊數相同(k-regular):χ(G) ≤ k + 1
G的每個點的連接邊數不同(non-regular),也就是一般的圖:χ(G) ≤ Δ(G)

χ(G):一張圖G的最小著色數。
Δ(G):一張圖G的最大degree。

UVa 10661 10004 10052

Greedy Vertex Coloring / Grundy Chromatic Number

「貪心點著色」是採用貪心法而得到的點著色,可能有許多種。「Grundy著色數」是貪心點著色的顏色數目。不控制著色數。

最小點著色、k點著色是NP-complete問題,沒有快速的演算法。於是有些人轉為討論貪心點著色,設計快速的演算法。

演算法:無向圖點著色(Welsh-Powell Algorithm)

貪心點著色。圖上每個點,依照邊數由大到小排序,依序塗色。針對一個點,依序嘗試各種顏色,直到不牴觸已塗色的點。

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

時間複雜度等同一次Graph Traversal的時間,如果圖的資料結構為adjacency matrix就是O(V²),如果圖的資料結構為adjacency lists就是O(V+E)。

UVa 10471

演算法:二分圖點著色

Graph Traversal可以判斷一張圖是否為二分圖。

順便判斷二著色。順便找出其中一種最小點著色。

演算法:平面圖點著色(Four Color Theorem)

一張真實地圖,每塊區域塗上顏色,相鄰區域必須是相異顏色。地圖可以化做平面圖:區域是點,相鄰區域是邊。

平面圖一定可以四著色(四色定理),P問題,有著O(N²)演算法。平面圖不一定可以三著色,NP-complete問題。

四色定理的證明方式,是把所有的圖精簡成幾種基本款式,逐一驗證是否能四著色,以電腦窮舉所有著色可能性。1976年基本款式共一千多種。1997年基本款式降到六百多種,同時發明了O(N²)四著色演算法(不保證著色數最小):

http://people.math.gatech.edu/~thomas/FC/fourcolor.html

有些數學家認為,電腦窮舉不是一個嚴謹的、具有數學意義的證明方式。因此這個問題現今仍有人在持續研究。

延伸閱讀:Four Color Theorem

下面提供一些個人想法,睡不著時加減想的,應該有誤:

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

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

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

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

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

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

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

以上就是我想到的證明。理所當然是個偽證。謝謝收看。

Edge Coloring

Edge Coloring

「邊著色」。一張圖每條邊塗上顏色,鄰邊不同色。

Minimum Edge Coloring / Edge Chromatic Number

「最小邊著色」與「邊著色數」,概念同前。

UVa 10615

Total Coloring

「全著色」。點邊都著色。

http://en.wikipedia.org/wiki/Total_coloring

Synchronizing Coloring

http://en.wikipedia.org/wiki/Road_coloring_theorem

Weighted Coloring

http://www-sop.inria.fr/members/Nicolas.Nisse/slides/weightedTrees.pdf

ICPC 7465