Ненаправленный взвешенный граф имеет уникальное минимальное остовное дерево. Назовите пример. Ответ включен

Question

Вопрос: Приведите пример неориентированного взвешенного графа с двумя ребрами одинакового веса, для которого все еще существует уникальное минимальное остовное дерево. Есть много примеров такого графа. В качестве тривиального примера любой неориентированный взвешенный граф, который действительно является деревом и имеет два ребра равного веса, имеет уникальное минимальное остовное дерево - весь граф является единственным возможным остовным деревом, поскольку сам граф является деревом.

Я не уверен, что понимаю ответ:

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

Answer 1

Предположим, у вас есть график, который уже является деревом. То есть он подключен и не имеет циклов. Поскольку граф является деревом, граф уже является собственным MST. Это означает, что вы можете присвоить веса ребрам так, как вам нравится, и вы всегда получите тот же график обратно, если вычислите MST с использованием любого алгоритма MST, а именно, вы получите сам график. Поэтому вы можете решить эту проблему, приведя в качестве примера дерево с двумя ребрами с одинаковым весом.

В качестве примера рассмотрим этот график:

     *  *
     |  |
  *--*--*--*
     |  |
     *  *

Этот граф является деревом так что это его собственный MST независимо от того, как вы весите края. Если вы сделаете так, чтобы каждое ребро весило 137, тогда для графика остался только один MST, а именно сам график.