2

这里有两个关于安全顶点删除的 excises

5-28。图 G 的一个关节顶点是一个其删除断开 G 的顶点。设 G 是一个具有 n 个顶点和 m 个边的图。给出一个简单的 O(n + m) 算法来找到 G 的一个不是关节顶点的顶点——即 ，其删除不会断开 G。

5-29。继续上一个问题，给出一个 O(n + m) 算法，该算法找到 n 个顶点的删除顺序，使得没有删除会断开图的连接。（提示：想想 DFS/BFS。）

对于5-28，这是我的想法：

我只会做一个dfs，但不完整。完成处理的第一个顶点将是一个非关节顶点，因为它必须是一个叶子，或者一个后边缘指向其祖先的叶子（它也不是一个关节顶点）。

对于 5-29

我还不确定如何做得很好。我想到的是，在图中，循环中的任何顶点都不能安全地删除。此外，如果没有循环，则从 dfs 树向后删除顶点也是安全的。

谁能给我一些提示或告诉我我的想法是对还是错？

4

3 回答 3

2

我认为您对 5-28 的解决方案是正确的，它保证在 O(n+m) 时间内找到一个不是关节的节点。

对于 5-29，我认为一种方法是基于您对 5-28 的解决方案。在执行 dfs 时，请注意每个节点何时离开堆栈（处理完成的时间）。如您所说，首先离开的必须是叶节点，因此删除它不会断开图的连接。然后你可以删除第二个离开堆栈的节点，当我们删除第一个节点时，它也必须是一个叶子节点。因此，我们可以在执行 DFS 时按照从堆栈中弹出节点的相反顺序删除节点。这样做只需要一次 DFS，因此运行时间是 O(n+m)。

另一种简单的方法是使用 BFS。对于 5.28，删除任何具有最大深度的节点不会使图形断开连接。因为深度较小的节点可以到达其他节点。所以对于 5.29，我们可以按排序深度降序删除所有节点。而且，我们只需要 1 个 BFS，所以运行时间是 O(n+m)。我认为人们更容易理解这种方法。

于 2012-04-27T19:57:12.017 回答
0

5-29：扩展5-28的想法，当你处理完一个顶点时，它是一个非关节顶点，所以删除它。然后继续 DFS，每次处理完另一个顶点时，也将其删除。由于您删除了先前已完成处理的顶点，因此每次完成顶点处理时，实际上都是您第一次完成顶点处理（对于没有先前删除的顶点的图形）。

另一种方法，更容易证明，但效率稍低（但仍然 O(V + E)） - 从图中创建一个 DFS 树，然后进行拓扑排序，然后从最后一个顶点开始逐个删除排序图并返回第一个图。在每一步都删除最后一个，并且您确定（因为它是拓扑排序图）它不指向任何其他节点，这意味着除了通向它的边之外不会删除任何边。这意味着所有其他节点仍然可以从第一个节点到达，如果图是双向的，那么所有节点也可以到达第一个节点，使其连接。

于 2015-12-18T17:15:34.780 回答
-1

对于第一个问题，我将从图中删除要测试的顶点，然后从任何其他顶点开始运行 DFS/BFS，计算访问顶点的数量。如果它小于(original size - 1)，那么测试的顶点是一个关节顶点。

同样的想法适用于第二个问题。您随机选择一个顶点并将其删除，这通常会将图形切割成两个块。如果删除的顶点不是关节顶点，则两个块之一必须为空。否则，两个块都有一些顶点，在这种情况下，两个块中的所有顶点都必须按照最终的“安全删除”顺序列在该顶点的前面，而决定首先完全删除哪个块并不重要. 所以我们可以写一个这样的递归函数：

vertex[] safe_order_cut (vertex[] v)
    if (v.length==0) return empty_vertex_list;
    vertex x = randomly_pick(v);
    vertex v1[], v2[];
    cut_graph(v,x,v1,v2);
    return safe_order_cut(v1) + safe_order_cut(v2) + x;

连通性问题（以及相关的割点问题）已在图论中得到广泛研究。如果您有兴趣，可以阅读 wiki 页面了解更多算法。

于 2012-04-25T23:15:26.630 回答