is_biconnected#

is_biconnected(G)[source]#

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

当且仅当移除任何一个节点（及其所有关联边）都不会导致图断开时，该图是双连通的。如果移除某个节点会增加图中不连通分量的数量，则该节点称为关节点或割点。双连通图没有关节点。

参数:

GNetworkX 图

一个无向图。

返回:

biconnectedbool

如果图是双连通的，返回 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). “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