最小生成树的证明（更多的是数学问题）

Question

众所周知，最小生成树试图实现树的权重总和“最小”。

现在是我的问题。 使用 prim 和 kruskal 算法，

1) 如果我们改变我们试图最小化的内容，树的权重“最小”总和为 W(T)= max eET{w(e)}，其中 w(e) 是树的边缘？即树的最大权重是 MST 的所有其他最大边的最小值？证明 prim 和 kruskal 在这种情况下会起作用。

2) 现在作为度量，我们需要树边权重的“最小”乘法。 w(T) = ΠeΕT w(e)。即该 MST 的权重是所有其他 MST 的树边权重的“最小”乘积。这同样适用于这里吗？

我知道 1）prim 和 kruskal 总是会起作用并实现我们想要的，2）它们会起作用，但仅在某些条件下。

你能给我举一个 2) 中 kruskal 和 prim 不起作用的例子吗？另外，对于 1) 我该如何开始以证明 prim 和 kruskal 总是有效，对于 2) 也一样？

非常感谢。

Answer 1

如果所有边权重均为正，则 Prim 或 Kruskal 找到的 MST 将具有最小值

sum(w(e))

，以及最小值

sum(log(w(e)))

，并且最小值

sum(log(w(e)))

必然对应于最小值

product(w(e))

。事实上，我们可以用任何单调递增函数替换

log

。

但是，如果某些权重为负，则

log(w(e))

并不总是被定义，这不起作用，并且 MST 不一定具有最小乘积。例如，树中奇数个负权重总是比偶数个负权重更好，因为它会产生负乘积。然而，MST 将具有最大数量的负权重，即使该最大数量是偶数。