首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >删除最小权重边以断开一组节点

问删除最小权重边以断开一组节点
EN

Stack Overflow用户
提问于 2012-04-27 02:50:25
回答 1查看 804关注 0票数 1

问题是给定一个加权边双向图,找出边的集合,通过删除给定的一组节点彼此断开连接的边。而且这些边权重的和也应该是最小的。这个问题有什么名字吗?有没有什么特别的算法来解决它们?我知道这一定是NP完全问题。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2012-04-27 06:19:51

如果你只是想找到一个最小的权重切割,将你的图分成两部分,这可以通过运行最大流量/最小切割算法(例如Edmonds算法)来实现。你只需要修复一个顶点,然后找到它与所有其他|V|-1个顶点的最小割线,最后在所有割线中找出最小割线。请注意,您的固定顶点应该位于一个组件中。要在无向图上运行max-flow/min cut算法,只需将每条边绘制成两个方向即可。此算法导致运行最大流算法* O(|V|)。

但如果你的问题是如何以最小的权重将图划分为k个连通分量,这就是NP-Hard问题。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/10339576

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档