is_biconnected#

is_biconnected(G)[source]#

返回 True 如果图是双连通的，否则返回 False。

一个图是双连通的，当且仅当，它不能通过移除一个节点（以及该节点上的所有边）而被断开。如果移除一个节点增加了图中断开部分的数目，该节点被称为关节点或割点。一个双连通图没有关节点。

Parameters:

GNetworkX 图: 一个无向图。

Returns:

biconnectedbool: 如果图是双连通的，返回 True，否则返回 False。

Raises:

NetworkXNotImplemented: 如果输入图不是无向图。

See also

biconnected_components
articulation_points
biconnected_component_edges
is_strongly_connected
is_weakly_connected
is_connected
is_semiconnected

Notes

用于查找关节点和双连通组件的算法是使用一个非递归的深度优先搜索（DFS）实现的，该算法跟踪回边在DFS树中达到的最高级别。一个节点 n 是关节点，当且仅当，存在一个以 n 为根的子树，使得没有任何从 n 的后继节点到 n 的前驱节点的回边。通过跟踪DFS遍历的所有边，我们可以获得双连通组件，因为双连通组件的所有边将在关节点之间连续遍历。

References

[1]

Hopcroft, J.; Tarjan, R. (1973). “Efficient algorithms for graph manipulation”. Communications of the ACM 16: 372–378. doi:10.1145/362248.362272

Examples

>>> G = nx.path_graph(4)
>>> print(nx.is_biconnected(G))
False
>>> G.add_edge(0, 3)
>>> print(nx.is_biconnected(G))
True