1

如果我有一个无向图，G = (V, E)并且我想找到其中的所有顶点至少与 中的其他顶点有连接的S顶点子集。最好的方法是什么？GSnS

4

1 回答 1

1

起初，这个任务听起来类似于派系问题。这可能表明您的任务也将是 NP 难的。

再想一想，它实际上要简单得多，这是一个算法：

  1. 删除所有度数小于 n 的 v
  2. 在受限 G 上重复 (1) 直到它为空或所有剩余顶点的度数为 n 或更高
  3. 剩下的顶点是你的子集 S
于 2017-03-08T00:14:15.240 回答