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

查看 80|回复 4
作者: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/
您需要登录后才可以回帖 登录 | 立即注册

返回顶部