Рубрики

Алгоритмы | График Минимальное остовное дерево | Вопрос 8

Рассмотрим взвешенный полный граф G на множестве вершин {v1, v2, v}, такой, что вес ребра (v ,, v) равен 2 | ij |. Вес минимального остовного дерева G составляет: (GATE CS 2006)

(A) n — 1
(B) 2n — 2
(C) nC2
(D) 2

Ответ: (Б)
Пояснение: Минимальное остовное дерево такого графа

v1
  \
    v2
      \
       v3
         \
          v4
            .
              .
                .
                 vn
 

Вес минимального остовного дерева
= 2 | 2 — 1 | + 2 | 3 — 2 | + 2 | 4 — 3 | + 2 | 5 — 4 | …. + 2 | n — (n-1) |
= 2n — 2

Тест на этот вопрос

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

Алгоритмы | График Минимальное остовное дерево | Вопрос 8

0.00 (0%) 0 votes