Returns True if the graph is biconnected, False otherwise.
A graph is biconnected if, and only if, it cannot be disconnected by removing only one node (and all edges incident on that node). If removing a node increases the number of disconnected components in the graph, that node is called an articulation point, or cut vertex. A biconnected graph has no articulation points.
- GNetworkX Graph
An undirected graph.
True if the graph is biconnected, False otherwise.
If the input graph is not undirected.
The algorithm to find articulation points and biconnected components is implemented using a non-recursive depth-first-search (DFS) that keeps track of the highest level that back edges reach in the DFS tree. A node
nis an articulation point if, and only if, there exists a subtree rooted at
nsuch that there is no back edge from any successor of
nthat links to a predecessor of
nin the DFS tree. By keeping track of all the edges traversed by the DFS we can obtain the biconnected components because all edges of a bicomponent will be traversed consecutively between articulation points.
Hopcroft, J.; Tarjan, R. (1973). “Efficient algorithms for graph manipulation”. Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
>>> G = nx.path_graph(4) >>> print(nx.is_biconnected(G)) False >>> G.add_edge(0, 3) >>> print(nx.is_biconnected(G)) True