algorithm - 不会导致图形断开的安全顶点删除

Question

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

5-28. An articulation vertex of a graph G is a vertex whose deletion disconnects G. Let G be a graph with n vertices and m edges. Give a simple O(n + m) algorithm for finding a vertex of G that is not an articulation vertex—i.e. , whose deletion does not disconnect G.

5-29. Following up on the previous problem, give an O(n + m) algorithm that finds a deletion order for the n vertices such that no deletion disconnects the graph. (Hint: think DFS/BFS.)

---

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

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

适合 5-29 岁

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

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

Answer 1

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

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

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