graph-theory - 如何找到连接图的断开组件的最小顶点数？

Question

假设，我有一个具有固定数量的节点和边的图。但是，并非所有节点都始终保持活动状态，从而导致图表断开连接。在这种情况下，我想找出最小的顶点集，在保持活动状态的情况下，将始终保持图形连接。

我怎么解决这个问题？这个问题可以映射到任何已知问题吗？

Answer 1

我认为您正在寻找图表中的一组关节点！

如果是这样，这是深度优先搜索的一个应用：

http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Answer 2

这听起来像是连通支配集。