Рубрики

ВОРОТА | GATE CS 2011 | Вопрос 54

Ненаправленный граф G (V, E) содержит n (n> 2) узлов с именами v1, v2,… .vn. Два узла vi, vj связаны тогда и только тогда, когда 0 <| i — j | <= 2. Каждому ребру (vi, vj) присвоен вес i + j. Пример графика с n = 4 показан ниже.

Какова будет стоимость минимального связующего дерева (MST) такого графа с n узлами?
(A) 1/12 (11n ^ 2 — 5n)
(B) n ^ 2 — n + 1
(С) 6n — 11
(D) 2n + 1

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

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

ВОРОТА | GATE CS 2011 | Вопрос 54

0.00 (0%) 0 votes