给定一个图,我想找到节点集 S1, S2, ... 的移除可能会断开网络。这些集合中的每一个都可能包含一个或多个节点。此外,这些集合中的任何一个都不是彼此的子集,即我们不考虑 S3=S1 U S2 尽管它也断开了网络。
我们不想找到:
- 只有一个关键节点集,但所有
- 最大程度断开网络的单组节点。
任何关于这些的任何建议:
- 问题的难度
- 解决方案的一些方向/论文参考
- 我可能需要提供的任何证明
给定一个图,我想找到节点集 S1, S2, ... 的移除可能会断开网络。这些集合中的每一个都可能包含一个或多个节点。此外,这些集合中的任何一个都不是彼此的子集,即我们不考虑 S3=S1 U S2 尽管它也断开了网络。
我们不想找到:
任何关于这些的任何建议:
删除断开图的顶点集称为分隔符。参见例如 A. Berry, JP Bordat, O. Cogis:Generating all the Minimal Separators of a Graph。
您要查找的是图形分区。
这是一个NP难题。有关图分区的更多理解,
请参阅此内容。如果你用谷歌搜索的话,有可用的图分区的近线性时间算法。