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

米斯拉-格里斯边着色算法图论算法的一种,能够在多项式时间内找到任意图的一种边着色方案。这种着色算法最多使用种颜色,是该图节点的最大数。这对于一些图而言是最优的,根据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