algorithm - 删除最小权重边以断开一组节点

Question

问题是给定一个加权边双向图，通过删除给定节点集彼此断开的边来找到边集。而且这些边缘权重的总和应该是最小的。这个问题有名字吗？有什么特定的算法可以解决它们吗？我知道这一定是NP完全问题。

Answer 1

如果您只想找到一个将图形分成两部分的最小权重削减，这可以通过运行最大流量/最小削减算法（例如 Edmonds 算法）来完成。您只需修复一个顶点，然后找到它与所有其他 |V|-1 个顶点的最小切割，最后在所有切割中输出最小切割。请注意，您的固定顶点应位于组件之一中。为了在无向图上运行最大流/最小切割算法，只需将每条边绘制到两个方向。该算法导致运行最大流算法 * O(|V|)。

但是，如果您的问题是如何将图划分为具有最小权重削减的 k 个连通分量，这就是 NP-Hard 问题。