断开图中的所有顶点 - 算法

Question

我正在寻找一种算法，可以找到最小的顶点子集，通过从图中删除此子集（以及连接这些顶点的边），使所有其他顶点变得不相连（即图中将没有任何边）。

• 是否有这样的算法？
• 如果没有：您能推荐一些启发式方法来确定顶点吗？

我对图论有基本的了解，敬请谅解其中的任何不正确之处。

- NefariousOctopus

---

要求我们推荐或寻找书籍、工具、软件库、教程或其他外部资源的问题在 Stack Overflow 上是不适合的，因为它们往往会吸引主观的答案和垃圾邮件。相反，请描述问题以及已经采取的解决方法。 - AStopher

@cybermonkey，没有推荐的请求。这个问题是切题的，而且有一个明确的答案（请参见@AmiTavory的回答）。 （显然还有更多的答案，但没有一个是垃圾意见的答案）。他正在描述一个问题，并得到了答案。 - amit

它要求一个算法，这与“为我编写代码”相同。 - AStopher

没错，询问算法是完全可以的。这里有四个例子（Example 1、Example 2、Example 3、Example 4）证明了询问如何完成某项任务是可以的，而且询问算法也是主题之一，因为它可以轻松地转换为任何编程语言。你可以认为这些问题没有展示足够的研究努力，但那是另一个问题。 - amit

Answer 1

如果我理解正确，这是经典的最小顶点覆盖问题，但不幸的是，它是NP完全问题。

幸运的是，在这种情况下，最直观和贪心的算法就是最好的。

- Ami Tavory

---

当集合大小为 1.2738^(subset_size) 时间过长时，即便是“最直观和最贪心的算法”也只能达到其极限。 - user380772

Answer 2

贪心算法是顶点覆盖问题的2近似算法，在理论上，根据唯一游戏猜想，这是最优解。然而在实践中，将顶点覆盖问题转化为整数规划问题求解很可能会得到更好的结果。该程序为：

min sum_{v in V} x(v)
s.t.
forall {u, v} in E, x(u) + x(v) >= 1
forall v in V, x(v) in {0, 1}.

- David Eisenstat

Answer 3

尝试这种方式：

• 定义一个变量来计算顶点的数量，从0开始；
• 创建一个按每个顶点相邻列表长度排序的顶点最大堆；
• 从堆中删除第一个顶点（具有最多边数的顶点）的所有边，并将其从堆中删除，将计数器加1；

• 重新排序堆，因为顶点的边数已更改，重复上一步，直到第一个顶点的相邻列表长度为0；

  Heap Q
  int count = 0
  
  while(1){
  
      Q = Create_Heap(G)
      Vertex first = Q.pop
      if(first.adjacents.size() == 0) {
          break
      }
  
      for( Vertex v : first.adjacent ){
          RemoveEdge(first, v)
          RemoveEdge(v, first)    /* 取决于实现 */
      }
  
      count = count + 1
  
  }
  
  return count
  

- Daniel