2019-gate-computer-science-and-it-practice.pdf/Q18-alg5

Вопрос: Q18-alg5-31d68c

Предположим, что G — это связный неориентированный граф, ребра которого имеют положительные веса. Пусть M — минимальное остовное дерево этого графа. Мы модифицируем граф, добавляя «6» к весу каждого ребра, какое из следующих утверждений верно?

Ответы

• Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Крускала, изменится.
• Правильный ответ: Модификация добавляет к общему весу всех остовных деревьев.
• Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Прима, изменится.
• Ничего из вышеперечисленного.

Объяснение

Порядок добавления ребер при построении минимального остова не изменится. При добавлении 6 к весу каждого ребра, веса всех ребер в остовных деревьях увеличатся на 6. Поэтому общий вес всех остовных деревьев увеличится на , так как каждое остовное дерево имеет ребер.

Исходники — вопрос 18 на 244 странице книги «2019-gate-computer-science-and-it-practice.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.