Is the Minimum Product Spanning Tree different from a Minimum Sum Spanning Tree?

Question

Is the Minimum Product Spanning Tree different from a Minimum Sum Spanning Tree? plz explain (with examples ,if possible).I mean,edges that add to the minimum should(?) also have the minimum product.

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).

Answer 2

If all the edge weights are strictly positive then they will be the same tree. One easy way to see this is be examining MST algorithms, and noticing that the don't do any actual addition, they only pick the minimum edge out of a certain set in every step.

If edge weights are strictly positive, then the minimum product spanning tree with weights Wi will be the same as the minimum sum spanning tree with weights log(Wi), and since the log function is monotonic, then any MST algorithm will behave identically with weights log(Wi) than with weights Wi.

A more mathematical proof would be to note that (assuming all the edge weights are distinct), the MST of a graph will consist of the minimum cost edge crossing every cut of the graph. So clearly, the MST is invariant under monotonic transformations of edge weights.