最小乘积生成树与最小和生成树不同吗？请解释（如果可能的话，用例子）。我的意思是，添加到最小值的边缘应该（？）也有最小的产品。
问问题
3537 次
2 回答
5
使用所有边权重（正、负和零）：
它们可能不一样。
以此为例：
-10
□______□
/ \
1 | | 0
\ /
□
在这里，我们有：
Minimum product spanning tree: Minimum sum spanning tree:
-10 -10
□______□ □______□
/ \
1 | | 0
\ /
□ □
使用非零边缘权重（正和负）：
它们可能不一样。
偶数个负值的乘积会产生一个正值，因此在这种情况下，最好为最小乘积生成树选择一个正值。
以此为例：
-5
□______□
/ \
5 | | -5
\ /
□
在这里，我们有：
Minimum product spanning tree: Minimum sum spanning tree:
-5 -5
□______□ □______□
/ \
5 | | -5
\ /
□ □
与小的负值相比，选择更高的正值也会更好，只要我们最终得到奇数个负值。
使用非负边缘权重（正和零）：
可能有多个最小乘积生成树，其中一些可能不是最小和生成树（我还没有找到证明/反例，但目前看起来至少有一个最小乘积生成树将具有最小和）。
以此为例：
0
□______□
/ \
1 | | 10
\ /
□
这里10-0和1-0都是最小乘积生成树，但只有1-0最小和生成树。
仅使用正边缘权重和不同的边缘权重：
它们将是相同的。
证明：
考虑在树的其余部分之间进行选择a。bc
假设 a,b,c > 0...
Assume ca < cb
then a < b (since c > 0)
then a + c < b + c
因此，如果拣货a导致最小的产品，它也将导致最小的总和。
因此，获得最小的产品和最小的总和将包括挑选所有相同的边。
因此，它们将具有相同的生成树。
仅使用正边缘权重和非明显边缘权重：
以上假设不同的边权重，如果不是这种情况，则可能有多个生成树，它们显然不一定相同，但是两者的生成树选择将是相同的，因为它们都将具有相同的产品和相同的总和，因为唯一的区别是在具有相同重量的 2 条边之间进行挑选。
考虑：
10
□______□
/ \
5 | | 5
\ /
□
两种可能的生成树是：
10 10
□______□ □______□
/ \
5 | | 5
\ /
□ □
两者都是最小乘积和总和生成树（唯一的区别是我们选择了哪个 5，但 5 = 5，因此它不会改变总和或乘积）。
于 2013-10-14T11:34:06.963 回答
3
如果所有边缘权重都是严格正的，那么它们将是同一棵树。看到这一点的一种简单方法是检查 MST 算法，并注意到不做任何实际的加法，他们只在每一步中从某个集合中选择最小边。
如果边权重严格为正，则具有权重的最小乘积生成树Wi将与具有权重的最小和生成树相同log(Wi)，并且由于该log函数是单调的，因此任何 MST 算法对权重的行为与对权重log(Wi)的行为相同Wi。
一个更数学的证明是要注意（假设所有边权重都是不同的），图的 MST 将包括穿过图的每个切割的最小成本边。很明显，MST 在边缘权重的单调变换下是不变的。
于 2013-10-14T12:04:47.177 回答