我正在寻找一种算法,通过从图中移除这个子集(以及连接这些顶点的边),找到最小的顶点子集,所有其他顶点都变得不连通(也就是说,图不会有任何边)。
我有图论的基本知识,所以请原谅任何不正确的地方。
发布于 2015-06-23 12:19:10
幸运的是,在这种情况下,最直观、最贪婪的可能算法是一样好的。
发布于 2015-06-23 12:34:11
贪婪算法是顶点覆盖的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}.发布于 2015-12-06 16:14:11
试着这样做:
https://stackoverflow.com/questions/31002559
复制相似问题