algorithm - 最小積スパニング ツリーは、最小和スパニング ツリーとは異なりますか?

Question

最小積スパニング ツリーは、最小和スパニング ツリーとは異なりますか? plzは説明してください（可能であれば例を挙げて）。つまり、最小値に追加されるエッジには最小値の積もあるはずです（？）。

Answer 1

With all edge weights (positive, negative and zero):

They may not be the same.

Take this for example:

       -10
    □______□
   / \
1 |   | 0
   \ /
    □

Here we have:

Minimum product spanning tree:         Minimum sum spanning tree:
       -10                                -10
    □______□                           □______□
   /                                    \
1 |                                      | 0
   \                                    /
    □                                  □

With non-zero edge weights (positive and negative):

They may not be the same.

The product of an even number of negative values results in a positive value, so it would be better to pick a positive value in this case for the minimum product spanning tree.

Take this for example:

       -5
    □______□
   / \
5 |   | -5
   \ /
    □

Here we have:

Minimum product spanning tree:         Minimum sum spanning tree:
       -5                                 -5
    □______□                           □______□
   /                                    \
5 |                                      | -5
   \                                    /
    □                                  □

It would also be better to pick higher positive values, as opposed to small negative values, as long we end up with an odd number of negative values.

With non-negative edge weights (positive and zero):

There may multiple minimum product spanning trees, some of which may not be the minimum sum spanning tree (I am yet to find a proof / counter example, but currently it looks like at least one of the minimum product spanning trees will have the minimum sum).

Take this for example:

       0
    □______□
   / \
1 |   | 10
   \ /
    □

Here both 10-0 and 1-0 are minimum product spanning trees, but only 1-0 is a minimum sum spanning tree.

With positive edge weights only and distinct edge weights:

They will be the same.

Proof:

Consider picking between a and b with a sum of c in the rest of the tree.

Assuming a,b,c > 0...

Assume ca    < cb
then   a     < b      (since c > 0)
then   a + c < b + c

Thus if picking a leads to the smallest product, it will also lead to the smallest sum.

Thus getting to the smallest product and the smallest sum will consist of picking all the same edges.

Thus they will have the same spanning trees.

With positive edge weights only and non-distinct edge weights:

The above assumes distinct edge weights, if this is not the case, there may be multiple spanning trees for either, and they obviously won't necessarily be the same, but the choice of spanning trees for both will be identical because they will all have the same product and the same sum, since the only difference is picking between 2 edges with the same weight.

Consider:

       10
    □______□
   / \
5 |   | 5
   \ /
    □

The two possible spanning trees are:

       10              10
    □______□        □______□
   /                 \
5 |                   | 5
   \                 /
    □               □

Both are the minimum product and sum spanning trees (the only difference is which 5 we pick, but 5 = 5, so it doesn't change the sum or product).