贪婪顶点着色

greedy_vertex_coloring() 基于一个简单的贪婪算法查找图的顶点的着色。

用法

greedy_vertex_coloring(graph, heuristic = c("colored_neighbors", "dsatur"))

参数

graph

要着色的图对象。

heuristic

用于选择下一个要考虑的顶点的启发式方法。可能的值包括：“colored_neighbors”选择具有最大数量已着色邻居的顶点。“dsatur”选择邻域中具有最大数量唯一颜色的顶点，即其“饱和度”；当有多个最大饱和度顶点时，将选择具有最多未着色邻居的顶点。

值

一个数值向量，其中项目 i 包含与顶点 i 关联的颜色索引。

详细信息

顶点着色的目标是为图的每个顶点分配一个“颜色”（表示为一个正整数），使得相邻的顶点永远不会具有相同的颜色。此函数通过根据启发式方法逐个考虑顶点来解决此问题，始终选择与已着色邻居的颜色不同的最小颜色。以这种方式获得的着色不一定是最小的，但可以在线性时间内计算出来。

C 库中的相关文档

vertex_coloring_greedy().

示例

g <- make_graph("petersen")
col <- greedy_vertex_coloring(g)
plot(g, vertex.color = col)