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

Question

Отличается ли минимальное связующее дерево продуктов от минимального совокупного дерева? Пожалуйста, объясните (с примерами, если это возможно). Я имею в виду, что ребра, которые добавляют к минимуму, должны (?) также иметь минимальное произведение.

Answer 1

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

Они могут не совпадать.

Возьмите это к примеру:

       -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 приводит к наименьшему продукту, это также приведет к наименьшей сумме.

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

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

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

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

Рассматривать:

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

Два возможных связующих дерева:

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

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

Answer 2

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

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

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