Gries边着色算法

Gries边缘着色算法是图论中的多项式时间算法，可以找到任何图形的边缘着色。 着色产生最多使用Δ+ 1种颜色，其中Δ是图的最大程度。 这对于某些图是最佳的，并且根据Vizing定理，它最多使用一种颜色而不是所有其他颜色的最佳颜色。

它于1992年由Jayadev Misra和David Gries首次出版。 它是BélaBollobás对先前算法的简化。

算法输入：图表G。

输出：G边缘的适当着色c。

让 U:= E(G)

while U ≠ ∅ doLet (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 pathLet 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。

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 |）。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学