Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 11

Если все веса ребер неориентированного графа положительны, то любое подмножество ребер, которое соединяет все вершины и имеет минимальный общий вес, является

(A) Гамильтонов цикл
(B) сетка
(С) гиперкуб
(D) дерево

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

Как здесь, мы хотим подмножество ребер, которое соединяет все вершины и имеет минимальный общий вес, т.е. минимальное остовное дерево
Вариант А — включает цикл, поэтому может соединять или не соединять все ребра.
Вариант Б — не имеет отношения к этому вопросу.
Вариант C — включает цикл, поэтому может соединять или не соединять все ребра.

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

ВОРОТА | GATE IT 2006 | Вопрос 11

0.00 (0%) 0 votes