Какие из следующих опций верны в отношении MST?

Question

Я беру курс Алгоритмы: проектирование и анализ II , и один из вопросов следующий:

Рассмотрим связанный неориентированный граф с различными затратами на ребро.Что из следующего верно?[Отметьте все подходящие варианты.]

1. Предположим, что край ? не самый дешевый край, который пересекает разрез (?, ?).Тогда ? не принадлежит ни одному минимальному остовному дереву.
2. Предположим, что ребро ? является самым дорогим ребром, содержащимся в цикле ?.Тогда ? не принадлежит ни одному минимальному остовному дереву.
3. Минимальное остовное дерево уникально.
4. Предположим, что ребро ? является самым дешевым ребром, которое пересекает разрез (?, ?).Тогда ? принадлежит каждому минимальному остовному дереву.

Насколько мне известно, все четыре варианта верны.Варианты 1, 2 и 4 следуют из свойства Cut;Вариант 3 правильный, потому что веса ребер различны.Однако включение варианта 1 оказывается неверным.Зачем?

Answer 1

Прежде всего, давайте посмотрим на определение mst. MST - это подмножество связанного неориентированного графа с различными затратами на ребра, который соединяет все вершины вместе, без каких-либо циклов и с минимально возможным общим весом ребра.

1. Если ребро e является единственным способом пройти от А до В, не вызывая цикл, он может принадлежать mst.

2. Если есть цикл С, тогда мы не можем говорить о нембудет замкнутым путем. Это определение цикла.

3.Если каждое ребро имеет определенную стоимость, как вы упомянули, тогда будет только одно уникальное минимальное остовное дерево.

4. Это может не произойти, потому что это может вызвать цикл, подобный циклу или схеме, тогда мы не используем этот край, чтобы пересечь от A до B

Answer 2

1. Нет
2. Да
3. Да
4. Да

Основная часть ответа здесь# 3. Для графа со всеми различными затратами на ребра это верно. Ответы на все остальные вопросы вы можете получить, используя ответ на третий.

Для # 1:

 A1 --- B1
        |
 A2 --- B2

Предположим, w(A1,B1) > w(A2,B2), но вам все равно нужно включить их обоих в MST.