如何有效地找到图中的节点对，当删除这些节点时会导致图分裂？

Question

考虑这个简单的双连通图（没有关节点的图）：

G = nx.diamond_graph()
nx.draw(G, with_labels=True)

我想找出从图中删除哪两对节点会导致图分裂（本例中为

(1, 2)

）。为此，我将节点的组合一一删除，并计算图中剩余的组件数量。

from itertools import combinations

breaking_combinations = []
combos = combinations(G.nodes(), 2)
for combo in combos:
    G_copy = G.copy()
    init_num_components = nx.number_connected_components(G_copy)
    G_copy.remove_nodes_from(combo)
    num_components_after_combo_removed = nx.number_connected_components(G_copy)
    if num_components_after_combo_removed > init_num_components:
        breaking_combinations.append(combo)

print(breaking_combinations)

逻辑工作正常，我得到了预期的结果：在这个例子中

(1, 2)

。但这个过程在大图（约 10,000 个节点）上非常慢，以至于需要很长时间才能找到图中的所有组合。

我的问题是：是否有一种有效的替代方法可以用来实现相同的结果 - 也许通过使用内置的 networkx 算法？

Answer 1

扩展我上面的评论：

import networkx as nx

G = nx.diamond_graph()

solutions = []
for removed_node in G:
    H = G.subgraph([node for node in G if node != removed_node]) # subgraph views are much faster to initialize than copies
    solutions.extend([(removed_node, node) for node in nx.articulation_points(H)])
print(solutions)
# (1, 2), (1, 2)