java - 如何获得在图中断开某个节点的最小成本

Question

在给定的图中，我想计算在图中断开某个节点的最小成本。示例：
在此图中，假设我想通过删除这些节点之间的一些边来node A断开node C连接node F。即通过删除edge A-B和，edge F-E节点和将断开连接。这里的成本是指被移除的边缘的长度。在此示例中，断开和彼此的总最小成本为 2+1=3。 有人可以提供一些提示。我无法对这个问题进行分类，这是一种还是？ACFNode ANode CNode F
shortest path problemminimum spanning tree problem

Answer 1

这称为多端割问题。不幸的是，似乎没有维基百科条目。问题是，给定一个加权图和一个称为终端的顶点子集，计算最小权重的边集，其移除会断开每对终端的连接。坏消息是这个问题是 NP 难的，所以如果你真的需要一个不能被暴力破解的实例的最优解，你可能不得不求助于整数编程。好消息是有一个简单的 2 逼近算法（不是已知的最佳因子，但您可能需要复习线性规划并阅读研究文献以使用“更好”的），这可以通过采取st 切割的联合将每个终端与其他终端分开。