推荐学习书目 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
有没有一种算法，能求出去掉尽可能少的顶点，让无向连通图变为不连通？
mikewang MikeWang000000 2023-04-09 03:33:46 +08:00 2507 次点击这是一个创建于 991 天前的主题，其中的信息可能已经有所发展或是发生改变。
边没有方向和权重之分，只需求出一种分割方法即可。
（网上随便找来的图）
举例：
下图中去除顶点 E ，可分割为两个连通图：
下图中去除 1 个顶点，或者 2 个顶点，均不能有效分割；去除 3 个顶点 (1, 4, 7) 可分割为两个连通图：
注：不要 ChatGPT ，谢谢
 | 1 geelaw 2023-04-09 04:23:09 +08:00  1 你需要的关键词是 vertex connectivity 。这个问题可以用（数次调用）最大流最小割算法解。 |
 | 2 ryd994 2023-04-09 07:57:54 +08:00 via Android 1 max flow min cut |
 | 3 PendingOni 2023-04-09 0:07:11 +08:00 1 |
 | 4 assiadamo 2023-04-09 12:37:06 +08:00 via Android 1 |
 | 5 mikewang OP @geelaw @ryd994 @PendingOni @assiadamo 感谢各位的回答， 了解了最小割的算法，但是好像都是将边割开，而不是将点去除； #4 这个求割点比较接近了，但是不能解决需要割掉两个以上点的情形 参考了一道题，奶牛的电信 ( https://www.luogu.com.cn/problem/P1345 ) 虽然思路可以将割点转化为了割边，但是这是有来源和目的地的； 对于一般场景如何应对呢... |
| 7 mikewang OP |
Select Language