Отличается ли связующее дерево минимального продукта от связующего дерева минимальной суммы?

Со всеми весами ребер (положительными, отрицательными и нулевыми):

Они не могут быть одинаковыми.

Возьмите это, например:

       -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 и b с суммой c в остальной части дерева.

Предполагая, что a, b, c > 0...

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

Таким образом, если выбор a приводит к наименьшему продукту, он также приведет к наименьшей сумме.

Таким образом, получение наименьшего произведения и наименьшей суммы будет состоять из выбора всех одинаковых ребер.

Таким образом, они будут иметь одинаковые остовные деревья.

Только с положительными весами ребер и нечеткими весами ребер:

Вышеприведенное предполагает различные веса ребер, если это не так, может быть несколько остовных деревьев для любого из них, и они, очевидно, не обязательно будут одинаковыми, но выбор остовных деревьев для обоих будет одинаковым, потому что все они будут иметь тот же продукт и та же сумма, поскольку единственная разница заключается в выборе между двумя ребрами с одинаковым весом.

Рассмотреть возможность:

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

Два возможных остовных дерева:

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

И то, и другое является минимальным продуктом и суммарным остовным деревом (единственная разница в том, какое 5 мы выбираем, но 5 = 5, так что это не меняет сумму или произведение).

Если все веса ребер строго положительны, то они будут одним и тем же деревом. Один из простых способов убедиться в этом — изучить алгоритмы MST и заметить, что они не делают никакого фактического сложения, а только выбирают минимальное ребро из определенного набора на каждом шаге.

Если веса ребер строго положительны, то остовное дерево минимального произведения с весами Wi будет таким же, как остовное дерево минимальной суммы с весами log(Wi), а поскольку функция log монотонна, то любой алгоритм MST будет вести себя одинаково с весами log(Wi), чем с веса Wi.

Более математическим доказательством было бы отметить, что (при условии, что все веса ребер различны) MST графа будет состоять из ребра с минимальной стоимостью, пересекающего каждый разрез графа. Итак, ясно, что MST инвариантен относительно монотонных преобразований весов ребер.