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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 595 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

（网上随便找来的图）

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

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

注：不要 ChatGPT ，谢谢

顶点

分割

连通图

去除

8 条回复 • 2023-04-09 22:39:54 +08:00

geelaw

2023-04-09 04:23:09 +08:00

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

ryd994

2023-04-09 07:57:54 +08:00 via Android

max flow min cut

PendingOni

2023-04-09 08:07:11 +08:00

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

assiadamo

2023-04-09 12:37:06 +08:00 via Android

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

mikewang

2023-04-09 15:42:40 +08:00

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

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

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

geelaw

2023-04-09 15:44:38 +08:00 via iPhone

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

mikewang

2023-04-09 16:05:14 +08:00

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

geelaw

2023-04-09 22:39:54 +08:00 via iPhone

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