ВОРОТА | ВОРОТА КС 2021 | Набор 2 | Вопрос 11

Пусть G — связный неориентированный взвешенный граф. Рассмотрим следующие два утверждения.

• S1: существует ребро минимального веса в G, которое присутствует в каждом минимальном остовном дереве G.
• S2: Если каждое ребро в G имеет различный вес, то G имеет уникальное минимальное остовное дерево.

Какой из следующих вариантов правильный?
(A) И S1, и S2 верны
(B) S1 верно, а S2 ложно
(C) S1 ложно, а S2 верно
(D) И S1, и S2 ложны

Ответ: (С)
Объяснение:

• S1: False, потому что когда мы меняем количество ребер в минимальном остовном дереве. Это минимальное ребро будет заменено другим ребром. Также может быть случай, когда все ребра имеют одинаковый вес, тогда вы можете выбрать любое ребро.
• S2: Верно, потому что, если веса ребер уникальны, возможен только один уникальный MST.

Викторина этого вопроса