piy*_*ukr 1 algorithm graph minimum-spanning-tree spanning-tree
最小乘积生成树与最小和生成树不同吗？请解释一下（如果可能的话，举例说明）。我的意思是，添加到最小值的边应该（？）也具有最小乘积。
对于所有边权重（正、负和零）：
\n\n它们可能不一样。
\n\n以此为例：
\n\n -10\n \xe2\x96\xa1______\xe2\x96\xa1\n / \\\n1 | | 0\n \\ /\n \xe2\x96\xa1\n这里我们有：
\n\nMinimum product spanning tree: Minimum sum spanning tree:\n -10 -10\n \xe2\x96\xa1______\xe2\x96\xa1 \xe2\x96\xa1______\xe2\x96\xa1\n / \\\n1 | | 0\n \\ /\n \xe2\x96\xa1 \xe2\x96\xa1\n对于非零边权重（正和负）：
\n\n它们可能不一样。
\n\n偶数个负值的乘积会产生正值，因此在这种情况下最好为最小乘积生成树选择正值。
\n\n以此为例：
\n\n -5\n \xe2\x96\xa1______\xe2\x96\xa1\n / \\\n5 | | -5\n \\ /\n \xe2\x96\xa1\n这里我们有：
\n\nMinimum product spanning tree: Minimum sum spanning tree:\n -5 -5\n \xe2\x96\xa1______\xe2\x96\xa1 \xe2\x96\xa1______\xe2\x96\xa1\n / \\\n5 | | -5\n \\ /\n \xe2\x96\xa1 \xe2\x96\xa1\n最好选择较高的正值，而不是较小的负值，只要我们最终得到奇数个负值。
\n\n使用非负边权重（正和零）：
\n\n可能有多个最小乘积生成树，其中一些可能不是最小和生成树（我还没有找到证明/反例，但目前看起来至少有一个最小乘积生成树将具有最小和） ）。
\n\n以此为例：
\n\n 0\n \xe2\x96\xa1______\xe2\x96\xa1\n / \\\n1 | | 10\n \\ /\n \xe2\x96\xa1\n这里10-0和1-0都是最小积生成树，但只有1-0是最小和生成树。
仅使用正边权重和不同边权重：
\n\n他们会是一样的。
\n\n证明：
\n\n考虑在树的其余部分中选择a和之间b的总和。c
假设 a,b,c > 0...
\n\nAssume ca < cb\nthen a < b (since c > 0)\nthen a + c < b + c\n因此，如果采摘a导致产品最小，那么它也将导致总和最小。
因此，获得最小的乘积和最小的总和将包括选取所有相同的边。
\n\n因此它们将具有相同的生成树。
\n\n仅使用正边权重和非明显边权重：
\n\n上面假设不同的边权重，如果不是这种情况，则两者都可能有多个生成树，并且它们显然不一定相同，但是两者的生成树选择将是相同的，因为它们都具有相同的产品和相同的总和，因为唯一的区别是在具有相同重量的 2 个边缘之间进行挑选。
\n\n考虑：
\n\n 10\n \xe2\x96\xa1______\xe2\x96\xa1\n / \\\n5 | | 5\n \\ /\n \xe2\x96\xa1\n两种可能的生成树是：
\n\n 10 10\n \xe2\x96\xa1______\xe2\x96\xa1 \xe2\x96\xa1______\xe2\x96\xa1\n / \\\n5 | | 5\n \\ /\n \xe2\x96\xa1 \xe2\x96\xa1\n两者都是最小乘积和求和生成树（唯一的区别是我们选择哪 5 个，但 5 = 5，所以它不会改变求和或乘积）。
\n