is_biconnected

is_biconnected(G)

如果图形是双连接的，则返回true，否则返回false。

只有当且仅当无法通过仅删除一个节点（以及该节点上的所有边）来断开连接时，图形才是双连接的。如果删除节点会增加图中断开连接的组件的数量，则该节点称为关节点或切割顶点。双连接图没有连接点。

参数

G网络X图表

无向图。

返回

biconnected布尔尔

如果图形是双连接的，则为True，否则为False。

加薪

NetworkXNotImplemented

如果输入图不是无向的。

参见

biconnected_components

articulation_points

biconnected_component_edges

is_strongly_connected

is_weakly_connected

is_connected

is_semiconnected

笔记

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

工具书类

1

Hopcroft，J.；Tarjan，R.（1973）。”图形处理的有效算法”。ACM通信16:372–378。内政部：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