具有负权重的最小生成树问题

Question

假设所有边权都为正数，可以通过取每条边的log然后应用Kruskal或Prim算法来获取最小生成树。但是如果一些边的权值为负数，则无法应用此过程，因为我们需要包括奇数条负边，并且这些边必须具有最大权重。在这种情况下该怎么办呢？

- AJAY HAYAGREEVE

---

为什么权重会是负数，遍历肯定还是有成本的吧？为什么不将树中所有边的权重都偏移最小负值，以便所有边都是正数。 - Mark

@Mark：反例> 顶点：{A，B，C}，边缘：{(A，B，-2)，(B，C，0)，(A，C，1)}。 - Shridhar R Kulkarni

@Mark，这显然是一个理论问题，你是基于现实在提问... - shole

虽然这是理论上的，但并没有太多意义。因为如果你设法包含奇数个负边，则需要最大绝对乘积生成树（取最长的边而不是最小的边）。0-边也很棘手，如果你无法得到负结果，则可以将其包含在内，其余部分则无关紧要。 - maraca

首先值得尝试的是：将图G的边权重的绝对值作为边权重，生成一个图G'。在G'中解决最大乘积生成树T'。将T'转移到G中，得到最大绝对乘积生成树T。计算T中负边的数量。如果这个数字恰好是奇数，则T是最小乘积生成树。否则，请使用其他方法。 - Colonel Panic

Answer 1

这里有一个简单的解决方案。如果至少有一条负边，则找到最优生成树，使log(abs(edge))之和最大化。然后，检查实际乘积（不带绝对值）是否为负数。如果是，输出当前生成树；否则用正边替换一条负边或用负边替换一条正边以得到解决方案。

如果没有边是负数，则最小化log(edge)之和应该有效。

复杂度：使用朴素算法为O(n^2)。

更多关于朴素算法的解释： 选择具有最低绝对值以进行删除的边。删除此边将树分成两部分。我们可以遍历这些集合之间的每个对（取决于情况应该是正数或负数），其边值最大。此部分的复杂度为O(n^2)。

我们可能需要尝试删除多条边才能达到最佳解决方案。假设我们遍历每条边，则复杂度为O(n^3)。

我非常有信心这可以改进。

- ElKamina

---

将其中一个正边替换为负边或将负边替换为正边-这部分可能需要一些详细说明。天真的方法是检查每条边是否可以被任何其他边替换以形成生成树，并选择最佳边，但您还需要在此基础上进行循环检测（这可能会使其变慢）。这里的“n”是什么？边数（|E|）还是顶点数（|V|）？ - Bernhard Barker

如何确保通过删除最低绝对值边将树分成两部分后，必须有另一条边来连接这两部分？（假设如果您通过某些非最低绝对值边进行拆分，则可以改进解决方案） - shole

Answer 2

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

这使问题变得简单一些，因为我们只需要寻找最好的负解决方案，如果我们找不到任何负解决方案，我们就使用带有log(abs())的Prims。

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

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

此外，我们可以合并所有仅具有正边或负边的节点，并删除绝对值最高的边。合并后，新节点可能与同一节点建立多个连接，您可以丢弃除最高绝对值的负边和正边以外的所有连接（因此最多有2条边指向同一节点）。顺便说一句，一旦我们有两条边指向同一节点（遵循上述移除条件），我们就知道存在一个解<=0。

如果最终只剩下一个节点，而它是负数，则问题已成功解决，如果是正数，则没有负解。如果我们有一个0节点，则可以按任意顺序合并其余节点。更有可能的是，我们会得到一个高度连接的图形，其中每个节点至少具有一个负边和一个正边。如果我们有奇数个负节点，则要合并具有偶数个负边的节点，反之亦然。

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

- maraca