米斯拉-格里斯邊着色算法

米斯拉-格里斯邊着色算法圖論算法的一種,能夠在多項式時間內找到任意圖的一種邊着色方案。這種着色算法最多使用種顏色,是該圖節點的最大數。這對於一些圖而言是最優的,根據Vizing定理,最壞情況下,這種算法給出的結果比最優值多使用一種顏色。

該算法由Jayadev Misra和戴維·格里斯英語David Gries在1992年首次提出[1],是對Béla Bollobás提出的一種算法的簡化。[2]

對於邊着色問題,該算法是已知最快的「幾乎最優」算法。時間複雜度為。更小的時間複雜度在1985年Gabow等的一篇科技報告中提出,但從未被發表。[3]

總體上來說,最優邊着色問題是NP完全的,所以很可能並不存在多項式時間內的算法。同時也有指數級的算法給出了該問題的最優解。

 
頂點v的一個扇 F=[x_1,x_2,x_3](虛線邊代表未着色),(v,x_1),(v,x_2),(v,x_3)是扇的邊. F'=[x_1,x_2] 也是v的一個扇, 但不是最大的

對於一種顏色x,如果c(u,z)x 對於所有的 (u,z)   E(G) : z≠v均成立,則稱這種顏色x對於邊(u, v)未被使用。

頂點u的一個(Fan)是一個頂點序列,記為F[1:k],該序列滿足以下條件:

  1. F[1:k]是一個包含u的部分或全部鄰居節點的非空序列
  2. (F[1],u)   E(G) 未被着色
  3. F[i+1] 與u 的連邊的顏色對於 F[i] 未被使用,1 ≤ i < k
 
cdx路徑的一個例子:ac,cg,gd 是一個「紅-綠c」路徑,bd,dg是一個「紅-橙d」路徑

給定一個扇F,任意邊(F[i], X),1 ≤ i ≤ k 是扇的一條邊(Fan edge)。令 c 和 d 是兩種顏色,一個 cdX 路徑是一個經過節點X的,由只包含顏色 c 和 d 的邊組成的路徑,而且是最大的(即,不能添加任何邊到這個路徑中,否則就會包含顏色不為 c 或 d 的邊)。注意到對於任意節點 X ,只會存在一條這樣的邊,因為每種顏色最多只有一條邊與給定的節點鄰接。

扇的旋轉

編輯
 
翻轉扇 F = [x1x2x3],左邊為翻轉前,右邊為翻轉後

給定對於節點X的一個扇 F[1:k] ,旋轉操作進行以下操作:

  1. c(F[i],X) = c(F[i+1],X)
  2. 除去 F[k] 到 u 的邊的顏色

這種旋轉進行後着色仍然有效,因為對於任意 i ,c(F[i + 1], X)對(F[i], X)未被使用。

路徑的翻轉

編輯
 
翻轉「紅-綠a」路徑,左邊為翻轉前,右邊為翻轉後

操作「翻轉 cdX 路徑」將該路徑上的每個顏色為 c 的邊改變為 d ,每個顏色為 d 的邊改變顏色為 c 。如果X處於路徑的末端,則翻轉操作能夠釋放節點X上的一種顏色:如果 X 與 c 而非 d 相鄰,現在會變成與 d 而非 c 相鄰,把顏色 c 釋放出來,可以給其他與 X 鄰接的邊。這一翻轉操作不會改變着色的有效性,因為對於路徑末端的節點,只會有 c 或 d 中的一種顏色,而對於邊上的其他節點,翻轉操作只是交換了邊的顏色,並未增加新顏色。

算法

編輯

輸入: 圖 G.

輸出: 對於圖 G 的邊的一個合適染色方案

令 U := E(G)

while U ≠ ∅ do

  1. 令 (u,v) 是 U 的任意一條邊。
  2. 令 F[1:k] 是 u 的一個最大扇,且 F[1]=v.
  3. 令 c 是對於 u 未被使用的一種顏色,d 是對於 F[k] 未被使用的一種顏色.
  4. 翻轉 cdu 路徑
  5. 令 w ∈ V(G) 使得 w ∈ F, F'=[F[1]...w] 是一個扇,且顏色 d 對於 w 未被使用。
  6. 旋轉扇 F' 並設置 c(u,w)=d.
  7. U := U - {(u,v)}

end while

參考文獻

編輯
  1. ^ Misra, Jayadev; Gries, David. A constructive proof of Vizing's theorem (PDF). Information Processing Letters. 1992, 41 (3): 131–133 [2015-01-17]. doi:10.1016/0020-0190(92)90041-S. (原始內容 (PDF)存檔於2015-09-23). 
  2. ^ Bollobás, Béla. Graph theory. Elsevier. 1982: 94. 
  3. ^ Gabow, Harold N.; Nishizeki, Takao; Kariv, Oded; Leven, Daniel; Terada, Osamu, Algorithms for edge-coloring graphs, Tech. Report TRECIS-8501, Tohoku University, 1985