如何在图表中获得将某个节点彼此断开连接的最低成本

Question

在给定的图中,我想计算在图中断开某个节点彼此的最小成本.例:
在该图中,让说我要断开连接node A,node C并node F相互除去这些节点间的一些边缘.通过去除,即edge A-B和edge F-E,节点A,C和F将被断开.这里的成本是指被移除的边缘的长度.在用于断开该实例中总成本最小Node A,Node C并且Node F彼此为2 + 1 = 3.
有人可以提供一些提示.我无法对这个问题进行分类,这是一种shortest path problem还是minimum spanning tree problem？

Answer 1

这称为多端切割问题。不幸的是，维基百科似乎没有条目。问题是，给定一个加权图和称为终端 的顶点子集，计算边的最小权重集，其删除会断开每对终端的连接。坏消息是这个问题是 NP 难题，因此如果您确实需要在无法暴力破解的实例上找到最佳解决方案，那么您可能必须转向整数规划。好消息是，有一个简单的 2 近似算法（不是已知的最佳因子，但您可能需要温习线性规划并阅读研究文献才能使用“更好”的算法），可以通过以下方式实现st 切口的联合将每个端子与其他端子分开。