首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >断开图算法中的所有顶点

问断开图算法中的所有顶点
EN

Stack Overflow用户
提问于 2015-06-23 12:15:56
回答 3查看 577关注 0票数 14

我正在寻找一种算法,通过从图中移除这个子集(以及连接这些顶点的边),找到最小的顶点子集,所有其他顶点都变得不连通(也就是说,图不会有任何边)。

  • 有这样的算法吗?
  • 如果没有:您能推荐某种启发式方法来指定顶点吗?

我有图论的基本知识,所以请原谅任何不正确的地方。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2015-06-23 12:19:10

这是经典的最小顶点覆盖问题,不幸的是,是NP完全问题。

幸运的是,在这种情况下,最直观、最贪婪的可能算法是一样好的。

票数 9
EN

Stack Overflow用户

发布于 2015-06-23 12:34:11

贪婪算法是顶点覆盖的2-逼近,理论上,在唯一的对策猜想下,它是尽可能好的。在实践中,求解顶点覆盖的公式作为整数程序很可能会产生更好的结果。程序是

代码语言:javascript
复制
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}.
票数 2
EN

Stack Overflow用户

发布于 2015-12-06 16:14:11

试着这样做:

  • 定义一个变量来计数顶点数,从0开始;
  • 创建一个顶点的最大堆,按每个顶点的相邻列表的长度排序;
  • 从堆的第一个顶点(边数最多的一个)中移除所有的边,并从堆中移除它,增加一个;
  • 当顶点的边数改变后,重新排序堆,重复上一步,直到第一个顶点的相邻列表的长度为0; 堆Q计数=0,而(1 ){ q= Create_Heap(G)顶点首先= Q.pop如果(first.adjacents.size() == 0) {==} for(顶点v: first.adjacent ){ RemoveEdge( first,v) RemoveEdge(v,first) /*取决于实现*/ } count = count +1}返回计数
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/31002559

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档