algorithm - 查找删除断开图的所有节点对

Question

给定无向连通图，找到所有节点对(由边连接)，其删除使图断开。
没有平行边，也没有边将节点连接到自身。

这个问题似乎类似于寻找连接的无向图的连接点(或桥)——但有一点不同，我们必须删除由一条边连接的一对顶点(以及连接到该对的所有其他边) .

这是一道作业题。我一直在尝试解决它，阅读有关 DFS 和关节点算法(每个节点的 bookkeap 深度和低点)的信息 - 但这些方法都没有帮助解决这个特定问题。我已经检查了 Cormen 的算法介绍，但没有一个主题本身是合适的(当然，这本书确实有 1500 页)。

虽然找到连接点确实也会(大多数时候)找到这样的对，但有很多对不是连接点 - 考虑一个有 4 个顶点、5 个边的图(正方形有单对角线):它有一对这样的但没有关节点(也没有桥)。

我迷路了。帮助我，堆栈溢出，你是我唯一的希望。

Answer 1

相当简单，也许不是最有效的:

设图为 G=(V,E)，其中 V := {v_1, ..., v_n}。对于 V 的每个子集 V'，设 G_V' 为包含节点 V\V' 的节点诱导子图。设进一步 N>_v_i := {v_j in V : {v_i,v_j} in E and j > i} 是 G 中 v_i 的索引大于 i 的所有邻居的集合。最后，设 c(G) 为图的连通分量集。

按如下方式计算对:

pairs = {}
for each v in V:
    compute G_{v}
    if G_{v} is unconnected:
        for each v' in N>_v:
            # Ensures that removal of v' does not render subgraph connected
            # (Note comment by MkjG)
            if |c(G_{v})| > 2 or {v'} not in c(G_{v}):
                add {v,v'} to pairs
    else:
        for each v' in N>_v:
            compute G_{v,v'}
            if G_{v,v'} unconnected:
                add {v,v'} to pairs

可以在 O(m+n) 中通过 DFS 或 BFS 检查连通性。因此，运行时间应该是 O(n * k * (m+n))，其中 k 是 G 的最大度数。