具有负权重的最小产品生成树

Question

假设如果所有边都具有正权重,则可以通过获取log每个边来获得最小产品生成树,然后应用Kruskal或Prim.但如果某些权重为负数,我们就无法应用此程序.因为我们需要包括奇数个负边,并且这些边必须是最大权重.在这种情况下该怎么做？

Answer 1

我非常怀疑你是否可以修改 Prims 算法来解决这个问题，因为负数完全改变了它。如果你设法得到负结果，那么绝对值必须最大化，这意味着必须使用具有最高绝对值的边，因此尝试优化 Prims 算法找到的结果并取 log(abs()) 将不起作用，除非不可能得到负结果，否则这实际上会返回最佳解决方案。

这使得问题变得更简单，因为我们只需要寻找最佳的负解，如果找不到，我们就使用带有 log(abs()) 的 Prims。

如果我们为每个顶点分配值 1，则可以通过使用两个顶点的所有边（连接它们的边除外）创建一个新顶点来合并两个顶点，并且该值是删除的顶点和边的值的乘积。

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

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

如果你最终得到一个节点并且它是负数，那么问题就成功解决了，如果它是正数，则没有负数解决方案。如果我们有一个 0 顶点，我们可以按任意顺序合并其余节点。更有可能的是，我们最终得到一个高度连接的图，其中每个节点至少有一个负边和一个正边。如果我们有奇数个负顶点，那么我们想要合并具有偶数个负边的节点，反之亦然。

始终按绝对值最高的边缘进行合并。如果生成的顶点 <= 0，则您找到了最佳解决方案。否则事情会变得复杂。您可以查看所有未使用的边，尝试添加它，看看哪些边可以被删除以使其再次成为一棵树，只查看那些具有不同符号的边并构建比率abs(added_edge/removed_edge)。然后最后以最佳比例进行更改（如果找到任何具有相反符号的组合，否则没有负解）。但我不能 100% 确定这是否总是能带来最好的结果。