Gries邊緣著色算法是圖論中的多項式時間算法，可以找到任何圖形的邊緣著色。 著色產生最多使用Δ+ 1種顏色，其中Δ是圖的最大程度。 這對於某些圖是最佳的，並且根據Vizing定理，它最多使用一種顏色而不是所有其他顏色的最佳顏色。
它於1992年由Jayadev Misra和David Gries首次出版。 它是BélaBollobás對先前算法的簡化。
基本介紹
- 中文名：Gries邊著色算法
- 外文名：Gries edge coloring algorithm
算法,證明正確,複雜度,
算法
輸入：圖表G。
輸出：G邊緣的適當著色c。
讓 U:= E(G)
while U ≠ ∅ do
Let (u,v) be any edge in U.
Let F[1:k] be a maximal fan of u starting at F[1]=v.
Let c be a color that is free on u and d be a color that is free on F[k].
Invert the cdu path
Let w ∈ V(G) be such that w ∈ F, F'=[F[1]...w] is a fan and d is free on w.
Rotate F' and set c(u,w)=d.
U := U - {(u,v)}
end while
證明正確
算法的正確性分為三個部分。 首先，示出了cdu路徑的反轉保證了頂點w，使得w∈F，F'= [F [1] ... w]是扇形，並且d在w上是自由的。 然後，顯示邊緣著色是適當的並且需要至多Δ+ 1種顏色。
1、路徑反轉是正確的；
2、邊緣著色是正確的；
3、該算法最多需要Δ+ 1種顏色。
複雜度
在每個步驟中，旋轉使邊緣（u，w）展開，同時著色先前未著色的邊緣（u，F [1]）和（u，v）。 因此，一個額外的邊緣變色。 因此，循環將運行O（| E |）次。 找到最大風扇，顏色c和d並反轉cdu路徑可以在O（| V |）時間內完成。 找到w並旋轉F'需要O（deg（u））∈O（| V |）|）時間。 查找和刪除邊（u，v）可以使用常量時間的堆疊（彈出最後一個元素）完成，並且可以在O（| E |）時間內填充此堆疊。 因此，循環的每次疊代花費O（| V |）時間，並且總運行時間是O（| E | + | E | | V |）= O（| E | | V |）。
