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

Question

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

现在假设我们有上图-

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

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

我想的办法-

第 1 步 - 运行 寻找单个关节点的算法。

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

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

我认为有更好的方法。

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

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

Answer 1

对于度数（即邻居计数）为 d 的任何顶点，删除其所有 d 个邻居将断开图（除非这些是图中唯一的其他顶点）。因此，这立即为您提供了需要删除的顶点数量的上限，以及为达到该限制可以删除的实际顶点数：只需查找最小度数的顶点，并删除其所有邻居。

在您的示例图中，您知道这是最佳解决方案，因为存在度数为 2 的顶点，并且您已经排除了大小为 1 的解决方案，因为您发现该图是双连通的（即不包含衔接点）。然而，一般来说，有可能比这个上限做得更好：例如，考虑一个由 k 个顶点上的 clique 的 2 个副本以及 2 个附加边 (u1, v1) 和 (u2, v2) 组成的图，其中来自第一个集团的 u1 和 u2，来自第二个集团的 v1 和 v2。这可以通过仅删除 u1 和 u2（或仅删除 v1 和 v2）来断开连接，即使最小度数 k 可以任意大。

Answer 2

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