米斯拉-格里斯邊着色算法是圖論算法的一種，能夠在多項式時間內找到任意圖的一種邊着色方案。這種着色算法最多使用種顏色，是該圖節點的最大度數。這對於一些圖而言是最優的，根據Vizing定理，最壞情況下，這種算法給出的結果比最優值多使用一種顏色。
該算法由Jayadev Misra和戴維·格里斯在1992年首次提出[1]，是對Béla Bollobás提出的一種算法的簡化。[2]
對於邊着色問題，該算法是已知最快的「幾乎最優」算法。時間複雜度為。更小的時間複雜度在1985年Gabow等的一篇科技報告中提出，但從未被發表。[3]
總體上來說，最優邊着色問題是NP完全的，所以很可能並不存在多項式時間內的算法。同時也有指數級的算法給出了該問題的最優解。
扇
對於一種顏色x，如果c(u,z) ≠ x 對於所有的 (u,z) E(G) : z≠v均成立，則稱這種顏色x對於邊(u, v)未被使用。
頂點u的一個扇(Fan)是一個頂點序列，記為F[1:k]，該序列滿足以下條件：
- F[1:k]是一個包含u的部分或全部鄰居節點的非空序列
- (F[1],u) E(G) 未被着色
- F[i+1] 與u 的連邊的顏色對於 F[i] 未被使用，1 ≤ i < k
給定一個扇F，任意邊(F[i], X)，1 ≤ i ≤ k 是扇的一條邊(Fan edge)。令 c 和 d 是兩種顏色，一個 cdX 路徑是一個經過節點X的，由只包含顏色 c 和 d 的邊組成的路徑，而且是最大的（即，不能添加任何邊到這個路徑中，否則就會包含顏色不為 c 或 d 的邊）。注意到對於任意節點 X ，只會存在一條這樣的邊，因為每種顏色最多只有一條邊與給定的節點鄰接。
給定對於節點X的一個扇 F[1:k] ，旋轉操作進行以下操作：
- c(F[i],X) = c(F[i+1],X)
- 除去 F[k] 到 u 的邊的顏色
這種旋轉進行後着色仍然有效，因為對於任意 i ，c(F[i + 1], X)對(F[i], X)未被使用。
操作「翻轉 cdX 路徑」將該路徑上的每個顏色為 c 的邊改變為 d ，每個顏色為 d 的邊改變顏色為 c 。如果X處於路徑的末端，則翻轉操作能夠釋放節點X上的一種顏色：如果 X 與 c 而非 d 相鄰，現在會變成與 d 而非 c 相鄰，把顏色 c 釋放出來，可以給其他與 X 鄰接的邊。這一翻轉操作不會改變着色的有效性，因為對於路徑末端的節點，只會有 c 或 d 中的一種顏色，而對於邊上的其他節點，翻轉操作只是交換了邊的顏色，並未增加新顏色。
算法
輸入: 圖 G.
輸出: 對於圖 G 的邊的一個合適染色方案
令 U := E(G)
while U ≠ ∅ do
- 令 (u,v) 是 U 的任意一條邊。
- 令 F[1:k] 是 u 的一個最大扇，且 F[1]=v.
- 令 c 是對於 u 未被使用的一種顏色，d 是對於 F[k] 未被使用的一種顏色.
- 翻轉 cdu 路徑
- 令 w ∈ V(G) 使得 w ∈ F, F'=[F[1]...w] 是一個扇，且顏色 d 對於 w 未被使用。
- 旋轉扇 F' 並設置 c(u,w)=d.
- U := U - {(u,v)}
end while
參考文獻
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
