algorithm - 在无向连通图中如何找到删除哪个图断开连接的顶点集？

Question

我知道在 undirected connected graph 中 articulation point 是一个顶点，删除后哪个图变得断开。对于 Java 代码，我点击了此链接 http://algs4.cs.princeton.edu/41undirected/Biconnected.java.html .

现在假设我们有上图-

在上图中没有关节点，因为图不会因移除任何单个顶点而断开连接。但是我们可以通过删除超过 1 个顶点来使图断开连接，例如，如果我们删除 4,6 个顶点图断开连接。

如何找到一组顶点，以便在删除这些顶点后图形变得断开连接。假设可以删除的顶点数是 3 个。这意味着我们不能一次删除超过 3 个顶点来使图断开连接。

我正在考虑的方法-

第 1 步 - 运行算法以找到单个关节点。

第 2 步 - 如果在第 1 步之后没有关节点，我们从图中删除一个顶点并运行关节点算法，我们对所有节点都这样做图中的顶点。使用它我们可以找到 2 个顶点(第一个是在运行算法之前删除的顶点，第二个顶点是在运行算法之后找到的)它们的删除将使图断开连接并且程序将停止，因为我们找到了一组顶点。

第 3 步 - 如果我们无法在第 2 步中找到顶点集，我们会从图中删除 2 个顶点并运行关节点算法。我们在移除后运行这个算法每对图的顶点。使用它我们可以找到一组 3 个顶点，删除哪个图将断开连接。如果静止图没有断开连接，我们就不会再运行程序，因为我们可以删除的顶点限制为 3。

我认为有更好的方法。

如何在删除断开连接的图后找到最小顶点集。

有什么更好的方法可以找到删除断开连接的图的顶点集。

Answer 1

参见 http://www.cs.colorado.edu/~hal/Papers/expandersC.ps.gz获得我所知道的用于计算最小顶点切割的最佳算法。