给定一个图，我想找到节点的集合 S1、S2、...，这些节点的移除可能会导致网络断开。这些集合中的每一个都可能包含一个或多个节点。 此外，这些集合中的任何一个都不是彼此的子集，即我们不考虑 S3=S1 U S2，尽管它也会断开网络连接。
我们不想找到:
- 只有一个关键节点集但所有
- 最大程度断开网络连接的单个节点集。
关于这些的任何建议:
- 问题的难度
- 解决方案的一些方向/论文引用
- 我可能需要提供的任何证明
最佳答案
删除后会断开图形连接的顶点集称为分隔符。参见例如A. Berry、J-P Bordat、O. Cogis:Generating all the Minimal Separators of a Graph .
关于algorithm - 查找图中的所有关键节点集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17441319/