查找其删除将断开图形连接的所有节点对

Question

给定无向连通图，查找其删除会断开该图的所有节点对（通过边连接）
没有平行边，也没有将节点连接到自身的边。

这个问题似乎类似于寻找一个连通的无向图的连接点（或桥），但有一个转折点，我们必须移除一对由边连接的顶点（以及所有其他与该对连接的边）。

这是一个家庭作业问题。我一直在尝试解决这个问题，阅读有关DFS和关节点算法（即每个节点的深度和低点）的文章，但这些方法都不能解决这个特定的问题。我查阅了科曼的算法简介，但并没有合适的主题（当然，这本书有1500页）。

虽然找到关节点（大多数情况下）也会找到这样的一对，但有很多不是关节点的对-考虑一个有4个顶点、5个边（带一条对角线的正方形）的图：它有一对这样的对，但没有关节点（也没有桥）。

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

Answer 1

断开图的k条边的集合称为k割。您试图枚举图的所有2-割。

本文描述了一种枚举图的所有割集的有效算法。应该可以对其进行调整，以找到图的所有2-割。

Answer 2

根据@MkjG关于使用DFS计算关节点的建议，更新我之前的回答。

设图为G=（V， E），V：={v_1，...，v_n}_。对于V的每个子集，设G_V是由节点V\V组成的节点诱导子图。对于G连通，如果G_{v}不连通，我们称V中的v为关节点。设N_v是G中v的邻居集。

关节点可以通过DFS计算，有关算法的更多信息请阅读此处。简而言之：

1. 为V中的某个根节点r计算DFS树T
2. r是一个连接点，如果T中有多个子节点
3. v中的任何其他节点v都是一个连接点，当它在T中有一个子v’时，该子v’满足以下条件：在T的子树T’中，以v’为根的节点都没有到v的祖先的后缘

设图G上DFS的结果是v中节点v上的函数c。c（v）是N\u v的子集，当满足以下两个条件时，它在c（v）中保持v'：

1. v’是T中v的子代
2. 在以v为根的T的子树T'中，没有节点具有v的祖先的后缘

注意，对于T的根节点r，c（r）是r的所有子节点的集合。可以在时间O（n m）中计算函数c。

按如下方式计算分隔符对：

# performs DFS on G for some root node r
c = DFS(G,r)
# computes articulation points of G and corresponding number of components
aps = {}
compCounts = {}
for each v in V:
    numComps = |c(v)|
    if v != r:
        ++numComps
    if numComps > 1:
        add v to aps
        compCounts[v] = numComps
# computes the set of all separator pairs containing at least on ap
S = {}
for each v in aps:
    numComps = compCounts[v]
    for each v' in N_v:
        if numComps > 2:
            # G_{v,v'} has at least two connected components
            add {v,v'} to S
        else:
            # if v' is an isolated node in G_{v}, then G_{v,v'} is connected
            if N_v' != {v}:
                add {v,v'} to S
# computes remaining separator pairs
for each v in V \ aps:
    compute G_{v}
    # performs DFS on G_{v} for some root r_v != v
    c_v = DFS(G_{v},r_v)
    # adds separator pairs for articulation points of G_{v} in N_v
    for each v' in N_v:
        numComps = |c(v')|
        if v' != r_v:
            ++numComps
        if numComps > 1:
            add{v,v'} to S

运行时间为O（n*（n m））

Answer 3

非常简单，可能不是最有效的：

设图为G=（V， E），V：={v_1，...，v_n}。对于V的每个子集，G_V是包含节点V\V的节点诱导子图。再让N

按如下方式计算对：

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的最大阶数。