Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 53

График показан ниже 8 ребер с различными весами целочисленных ребер. Минимальное связующее дерево (MST) имеет вес 36 и содержит ребра: {(A, C), (B, C), (B, E), (E, F), (D, F)}. Вес ребер только тех ребер, которые находятся в MST, приведены на рисунке ниже. Минимально возможная сумма весов всех 8 ребер этого графика составляет ______________.


(А) 66
(Б) 69
(С) 68
(D) 70

Ответ: (Б)
Пояснение: В каждом цикле вес ребра, не являющегося частью MST, должен быть больше или равен весу других ребер, которые являются частью MST.

Поскольку все веса ребер различны, вес должен быть больше.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 53

0.00 (0%) 0 votes