Рубрики

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

G = (V, E) — это неориентированный простой граф, в котором каждое ребро имеет различный вес, а e — это конкретное ребро G. Какое из следующих утверждений о минимальных остовных деревьях (MST) в G является / является ИСТИННЫМ?

I.  If e is the lightest edge of some cycle in G, 
    then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, 
    then every MST of G excludes e

(А) Я только
(B) только II
(С) как I, так и II
(D) ни я, ни я

Ответ: (Б)
Объяснение:
Я НЕ верен.
Пусть G = (V, E) — прямоугольный граф, где V = {a, b, c, d} и E = {ab, bc, cd, da, ac}.
Пусть ребра имеют веса: ab = 1, bc = 2, cd = 4, da = 5, ac = 3. Тогда, очевидно, ac является самым легким ребром цикла cdac, однако MST abcd со стоимостью 7 (= ab + bc + cd) не включает его.
Пусть ребра имеют весовые коэффициенты: ab = 6, bc — 7, cd = 4, da = 5, ac = 3. Тогда снова ac является самым легким ребром цикла cdac, а MST bacd со стоимостью 13 (= ba + ac + cd) включает его.
Таким образом, MST из G могут включать или не включать самый легкий край.

II это правда
Пусть край тяжести будет е. Предположим, что минимальное остовное дерево содержит e. Если мы добавим еще одно ребро в связующее дерево, мы создадим цикл. Предположим, мы добавляем ребро e 'в связующее дерево, которое сгенерировало цикл C. Мы можем уменьшить стоимость минимального остовного дерева, если выберем ребро, отличное от e, из C для удаления, что подразумевает, что e не должно быть в минимальном остовном дереве, и мы получите противоречие.

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

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

0.00 (0%) 0 votes