有没有一种算法，能求出去掉尽可能少的顶点，让无向连通图变为不连通？

[mikewang]

边没有方向和权重之分，只需求出一种分割方法即可。

---

（网上随便找来的图）

举例：
下图中去除顶点 E ，可分割为两个连通图：

下图中去除 1 个顶点，或者 2 个顶点，均不能有效分割；去除 3 个顶点 (1, 4, 7) 可分割为两个连通图：

---

注：不要 ChatGPT ，谢谢

[geelaw]

你需要的关键词是 vertex connectivity 。这个问题可以用（数次调用）最大流—最小割算法解。

[ryd994]

max flow min cut

[PendingOni]

https://www.cs.princeton.edu/courses/archive/spr04/cos226/lectures/maxflow.4up.pdf

[assiadamo]

https://oi-wiki.org/graph/cut/

[mikewang]

@geelaw @ryd994 @PendingOni @assiadamo
感谢各位的回答，
了解了最小割的算法，但是好像都是将边割开，而不是将点去除；

#4 这个求割点比较接近了，但是不能解决需要割掉两个以上点的情形

参考了一道题，奶牛的电信 ( https://www.luogu.com.cn/problem/P1345 )
虽然思路可以将割点转化为了割边，但是这是有来源和目的地的；
对于一般场景如何应对呢...

[geelaw]

@mikewang #5 你可以固定一个源，然后枚举汇。

[mikewang]

@geelaw 哈哈 我脑袋有点傻了 这样确实可解
不过这种情况任选一个源点固定，枚举汇点即可？比如 5 个点，调用 4 次即可
源点不用枚举吗

[geelaw]

@mikewang #7 固定的源属于某个连通分量，枚举不属于那个连通分量的汇。