在图中查找反馈顶点集

图的反馈顶点集是顶点的一个子集，删除这些顶点会破坏图中的所有环。在有向图和无向图上，找到最小反馈顶点集是一个 NP 完全问题。

用法

feedback_vertex_set(graph, weights = NULL, algo = c("exact_ip"))

参数

graph

输入图

weights

可能的顶点权重。如果图有一个名为“weight”的顶点属性，并且此参数为 NULL，则会自动使用该顶点属性。反馈顶点集问题的目标是找到具有最小总权重的反馈顶点集。

algo

指定要使用的算法。目前，“exact_ip”是唯一的选择，它使用精确整数规划方法解决反馈顶点集问题。

值

顶点序列（默认情况下，但请参阅 igraph_options() 的 return.vs.es 选项），包含反馈顶点集。

参见

其他结构属性：bfs()、component_distribution()、connect()、constraint()、coreness()、degree()、dfs()、distance_table()、edge_density()、feedback_arc_set()、girth()、is_acyclic()、is_dag()、is_matching()、k_shortest_paths()、knn()、reciprocity()、subcomponent()、subgraph()、topo_sort()、transitivity()、unfold_tree()、which_multiple()、which_mutual()

图环：feedback_arc_set()、find_cycle()、girth()、has_eulerian_path()、is_acyclic()、is_dag()、simple_cycles()

C 库中的相关文档

feedback_vertex_set().

示例

g <- make_lattice(c(3,3))
feedback_vertex_set(g)
#> + 2/9 vertices, from a395789:
#> [1] 2 8