双连通分量

查找图的双连通分量

用法

biconnected_components(graph)

参数

图

输入图。即使是有向图，也会被视为无向图。

值

具有三个组件的命名列表

no

数值标量，一个整数，表示图中的双连通分量数。

tree_edges

组件本身，一个数字向量列表。每个向量是一组边ID，给出双连通分量中的边。这些边定义了组件的生成树。

component_edges

数字向量列表。它给出了组件中的所有边。

components

数字向量列表，组件的顶点。

articulation_points

图的割点。请参见articulation_points()。

详细信息

如果删除任何单个顶点（及其相邻边）不会断开连接，则该图是双连通的。

图的双连通分量是其最大的双连通子图。图的双连通分量可以由其边的分区给出：每条边恰好是一个双连通分量的成员。请注意，这对于顶点是不正确的：同一顶点可以是许多双连通分量的一部分。

参见

articulation_points(), components(), is_connected(), vertex_connectivity()

连通分量 articulation_points(), component_distribution(), decompose(), is_biconnected()

作者

Gabor Csardi csardi.gabor@gmail.com

C 库中的相关文档

biconnected_components().

示例

g <- disjoint_union(make_full_graph(5), make_full_graph(5))
clu <- components(g)$membership
g <- add_edges(g, c(which(clu == 1), which(clu == 2)))
bc <- biconnected_components(g)