如何确定删除给定的环将是否会使图变为不连通状态

Question

我曾看到过检测图中循环的方法，但我仍然没有找到一种检测“桥-类”循环的方法。假设我们已经在连通（且无向）图中发现了一个循环，那么我们如何确定删除此循环是否会断开图形呢？所谓删除循环是指删除循环中的边（因此顶点不受影响）。

其中一种方法是明显计算删除前后的组件数量。但我只是想知道是否有更好的方法。

如果存在相关算法，请问是否可以指向相关工作/论文/出版物？

- Wayne

---

在图中，"关节点"会很有帮助。 - vish4071

你是删掉环的顶点还是只删除边？ - David Eisenstat

@DavidEisenstat 很确定是顶点，因为如果只有边，你可以简单地找到一个不是自环的循环，它将成为答案。 - Pavel

@DavidEisenstat 我只删除边缘。 - Wayne

@paulpaul1076 实际上我需要的是：假设我们在一个图中找到了一个环，如何检查删除它是否会使图断开连接？（我之前可能用词不当 - 对此感到抱歉。我已经编辑了我的帖子以使其更清晰。）其中一种方法是，就像你提到的那样，计算组件的数量。但我只是好奇是否有更好的方法。我之前看到过你关于关节点的帖子，我认为那很有趣。 - Wayne

Answer 1

Vish提到了关节点，这绝对是正确的方向。但还可以说得更多。可以通过修改后的DFS算法找到关节点，大致如下：

执行DFS，为每个数字分配其DFS编号（例如，在它之前访问的节点数）。当你遇到一个已经被发现的顶点时，将其DFS编号与当前顶点进行比较，并且可以存储与该顶点相关联的LOW号码（例如，此节点“看到”的最低DFS编号）。当您回归到起始顶点时，可以将父顶点与子顶点的LOW号码进行比较。在回归过程中，如果父顶点看到一个子顶点的LOW号码大于或等于自己的DFS编号，则该父顶点是一个关节点。

我在这里经常使用“子”和“父”作为描述符，因为在DFS树中，我们必须考虑根的特殊情况。如果它看到一个子节点的LOW号码大于或等于自己的DFS编号，并且它在树中有两个子节点，则第一个顶点是一个关节点。

这是一个有用的关节点图像

另一个需要熟悉的概念，特别是对于无向图而言，是双连通分量，也称为任何子图，其顶点在一个包含所有其他顶点的环中。

这里有一个有用的带有双连通分量的彩色图像

你可以证明任何两个双连通分量最多只能共享一个顶点；两个“共享”的顶点意味着它们与组件中的所有其他顶点一起形成一个环，因此这两个组件实际上是一个大组件。正如你在图中看到的，任何被两个组件共享的顶点（具有多种颜色）都是关节点。因此，删除包含任何关节点的环将断开图形。

- zstoebs

---

我找不到修改后的DFS算法的原始论文，但在图中查找关节点有很多文献资料。 - zstoebs

Answer 2

你可以用 dfs + 动态规划来获取 E+V 图中的所有桥。

你可以为 E+V 进行此操作。

http://www.geeksforgeeks.org/bridge-in-a-graph

将它们保存下来（只需创建布尔[E]，并将其设置为true。 然后你可以说O(1)的边是桥还是非桥。 你只需要取出所有来自你的循环的边，并验证它是否是桥。

- Aleksandr Lovkov

Answer 3

这是一个朴素算法，就复杂度而言，我认为没有更有效的方法来进行检查。

• 从边的列表（cycleEdges）开始
• 获取cycleEdges中的顶点集合（cycleVertices）
  • 如果cycleVertices中的顶点仅包含cycleEdges的一部分，则返回FALSE
• 对于cycleVertices中的每个顶点
  • 递归地跟随不在cycleEdges中的顶点的边缘（避免已经访问过的顶点）
    • 如果到达一个不在cycleVertices中的顶点，则将其添加到集合outsideVertices中（停止递归搜索此路径）
  • 如果只到达了cycleVertices中的顶点，则返回FALSE
• 如果outsideVertices包含1个元素，则返回TRUE
• 选择outsideVertices中的一个顶点，并将其从outsideVertices中删除
  • 递归地跟随不在cycleEdges中的该顶点的边缘（避免已经访问过的顶点）（优先选择包含outsideVertices中的顶点的边缘，以提高大型图的运行时间）
    • 如果到达一个在outsideVertices中的顶点，则将其从outsideVertices中删除
      • 如果outsideVertices为空，则返回TRUE
• 返回FALSE

- Louis Ricci

---

那么，cycleEdges 是所有循环的边还是一个循环的边？ - Pavel

@paulpaul1076 - cycleEdges 表示我们正在测试的当前循环中的边缘。OP 希望在保持图形连通性的同时删除已经找到的循环。 - Louis Ricci

Answer 4

好的，由于从任何一个顶点 x 都可以到达任何其他顶点 y，反之亦然，因此它是一个强连通分量，因此我们可以将一个循环缩成代表该循环的单个顶点。使用 DFS 可以在 O(n+m) 的时间内执行此操作。现在，我们可以再次应用 DFS，以检查缩小的循环是否为关节点，如果是，则删除它们将断开图形，否则不会。总时间为 2(n+m) = O(n+m)

- Number1729