c++ - 将无向连通图分成两个部分

Question

是否有任何算法可以通过删除最小个顶点将连通无向图分解成恰好2个连通图 .

例1:边列表[1-2, 2-3, 3-4]，这里我们可以删除2号顶点或3号顶点来分解图分为两个连通分量。

示例 2: 边列表 [1-2, 2-5, 2-3, 3-4]，这里我们不能删除顶点编号 2 作为 它将图分解为 3 个连通分量(我们不希望这样)，但我们可以删除顶点编号 3 以将图分解为两个连通分量。

Answer 1

你需要寻找minimal vertex separator算法。