R igraph 手册页

greedy_vertex_coloring {igraph}

R 文档

贪婪顶点着色

描述

greedy_vertex_coloring 基于简单的贪婪算法为图的顶点找到一种着色方案。

用法

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

参数

图	要着色的图对象
启发式	用于选择下一个要考虑的顶点的启发式方法。目前仅支持一种启发式方法：“colored_neighbors” 选择已着色邻居数量最多的顶点。

详细信息

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

值

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

示例

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

---