计算机科学

首页 > 计算机科学

Misra & Gries边着色算法

2018-08-28 09:37:27     所属分类:图算法

Misra & Gries边着色算法是图论算法的一种,能够在多项式时间内找到任意图的一种边着色方案。这种着色算法最多使用种颜色,是该图节点的最大度数。这对于一些图而言是最优的,根据Vizing定理,最坏情况下,这种算法给出的结果比最优值多使用一种颜色。

该算法由Jayadev Misra和David Gries在1992年首次提出[1],是对Béla Bollobás提出的一种算法的简化。[2]

对于边着色问题,该算法是已知最快的“几乎最优”算法。时间复杂度为。更小的时间复杂度在1985年Gabow等的一篇科技报告中提出,但从未被发表。[3]

总体上来说,最优边着色问题是NP完全的,所以很可能并不存在多项式时间内的算法。同时也有指数级的算法给出了该问题的最优解。

目录

  • 1
    • 1.1 扇的旋转
    • 1.2 路径的翻转
  • 2 算法
  • 3 参考文献

顶点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)是一个顶点序列,记为F1:k,该序列满足以下条件:

  1. F1:k是一个包含u的部分或全部邻居节点的非空序列
  2. (F1,u) E(G) 未被着色
  3. Fi+1 与u 的连边的颜色对于 Fi 未被使用,1 ≤ i < k
cdx路径的一个例子:ac,cg,gd 是一个“红-绿c”路径,bd,dg是一个“红-橙d”路径。

给定一个扇F,任意边(Fi, X),1 ≤ i ≤ k 是扇的一条边(Fan edge)。令 c 和 d 是两种颜色,一个 cdX 路径是一个经过节点X的,由只包含颜色 c 和 d 的边组成的路径,而且是最大的(即,不能添加任何边到这个路径中,否则就会包含颜色不为 c 或 d 的边)。注意到对于任意节点 X ,只会存在一条这样的边,因为每种颜色最多只有一条边与给定的节点邻接。

扇的旋转

翻转扇 F = x1x2x3,左边为翻转前,右边为翻转后。

给定对于节点X的一个扇 F1:k ,旋转操作进行以下操作:

  1. c(Fi,X) = c(Fi+1,X)
  2. 除去 Fk 到 u 的边的颜色

这种旋转进行后着色仍然有效,因为对于任意 i ,c(Fi + 1, X)对(FiX)未被使用。

路径的翻转

翻转“红-绿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. 令 F1:k 是 u 的一个最大扇,且 F1=v.
  3. 令 c 是对于 u 未被使用的一种颜色,d 是对于 Fk 未被使用的一种颜色.
  4. 翻转 cdu 路径
  5. 令 w ∈ V(G) 使得 w ∈ F, F'=F1...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. 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 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339794.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


上一篇:广度优先搜索
下一篇:拓扑排序
相关推荐
爱淘宝