0

给定一个图,我想找到节点集 S1, S2, ... 的移除可能会断开网络。这些集合中的每一个都可能包含一个或多个节点。此外,这些集合中的任何一个都不是彼此的子集,即我们不考虑 S3=S1 U S2 尽管它也断开了网络。

我们不想找到:

  1. 只有一个关键节点集,但所有
  2. 最大程度断开网络的单组节点。

任何关于这些的任何建议:

  1. 问题的难度
  2. 解决方案的一些方向/论文参考
  3. 我可能需要提供的任何证明
4

2 回答 2

1

删除断开图的顶点集称为分隔符。参见例如 A. Berry, JP Bordat, O. Cogis:Generating all the Minimal Separators of a Graph

于 2013-07-05T09:22:06.173 回答
0

您要查找的是图形分区
这是一个NP难题。有关图分区的更多理解,
请参阅此内容。如果你用谷歌搜索的话,有可用的图分区的近线性时间算法。

于 2013-07-03T06:49:23.630 回答