负权最小积生成树

Question

假设所有边的权值都为正，那么通过对每条边的log，然后应用Kruskal或Prim得到最小乘积生成树。但如果某些权重为负值，我们就不能应用这个程序。因为我们需要包含奇数个负边，而这些边必须具有最大的权重。在这种情况下怎么办？

Answer 1

我非常怀疑你能修改Prims算法来解决这个问题，因为负数完全改变了它。如果您设法得到一个负的结果，那么绝对值必须最大化，这意味着必须使用绝对值最高的边，因此试图优化Prims algo找到的结果并取log（abs（））是行不通的，除非不可能得到一个负的结果，那么这实际上将返回最佳解。

这使得问题变得简单了一点，因为我们只需要寻找最好的负解，如果找不到，我们就使用带log（abs（））的Prims。

如果我们给每个顶点赋一个值1，那么两个顶点可以通过创建一个新的顶点合并，这个新的顶点除了连接它们的顶点之外，所有的边都是被删除的顶点的值和边的乘积。

在此基础上，我们可以通过合并只有一条边的所有节点来开始简化。与每一步合并并行，删除的边必须标记为原始图中使用的边，以便最终从标记的边重建树。

此外，我们可以合并所有只有正边或只有负边的节点，删除绝对值最高的边。合并后，新节点可以有多个到同一节点的连接，您可以丢弃除绝对值最高的负边和正边（因此同一节点最多有2条边）以外的所有边。顺便说一句。只要同一个节点有2条边（遵循上面的移除条件），我们就知道必须存在一个<=0的解。

如果您最终得到一个节点并且它是负的，那么问题已经成功解决，如果它是正的，则没有负的解决方案。如果我们有一个0顶点，我们可以以任何顺序合并其余的节点。更可能的是，我们最终得到一个高度连通的图，其中每个节点至少有一个负边和一个正边。如果我们有奇数个负顶点，那么我们希望合并带有偶数个负边的节点，反之亦然。

始终按绝对值最高的边合并。如果得到的顶点<=0，那么您找到了最佳解。否则就会变得复杂。您可以查看所有未使用的边，尝试添加它，看看哪些边可以删除以使它再次成为树，只查看那些具有不同符号的边，并构建比率abs(added_edge/removed_edge)。然后最后用最佳比例做改变（如果你发现任何组合有相反的符号，否则就没有负解）。但我不能百分之百确定这是否总是给出最好的结果。