articulation_points: Articulation points and bridges of a graph

In igraph: Network Analysis and Visualization

Articulation points and bridges of a graph

Description

articulation_points() finds the articulation points (or cut vertices)

Usage

articulation_points(graph)

bridges(graph)

Arguments

graph

The input graph. It is treated as an undirected graph, even if it is directed.

Details

Articulation points or cut vertices are vertices whose removal increases the number of connected components in a graph. Similarly, bridges or cut-edges are edges whose removal increases the number of connected components in a graph. If the original graph was connected, then the removal of a single articulation point or a single bridge makes it disconnected. If a graph contains no articulation points, then its vertex connectivity is at least two.

Value

For articulation_points(), a numeric vector giving the vertex IDs of the articulation points of the input graph. For bridges(), a numeric vector giving the edge IDs of the bridges of the input graph.

Related documentation in the C library

igraph_articulation_points(), igraph_bridges().

Author(s)

Gabor Csardi [e-mail]

See Also

biconnected_components(), components(), is_connected(), vertex_connectivity(), edge_connectivity()

Connected components biconnected_components(), component_distribution(), decompose(), is_biconnected()

Examples

g <- disjoint_union(make_full_graph(5), make_full_graph(5))
clu <- components(g)$membership
g <- add_edges(g, c(match(1, clu), match(2, clu)))
articulation_points(g)

g <- make_graph("krackhardt_kite")
bridges(g)

igraph documentation built on Oct. 20, 2024, 1:06 a.m.