Рубрики

ВОРОТА | Gate IT 2005 | Вопрос 52

Пусть G — взвешенный неориентированный граф, а e — ребро с максимальным весом в G. Предположим, что в G есть остовное дерево минимального веса, содержащее ребро e. Какое из следующих утверждений всегда ИСТИННО?

(A) Существует множество сечений в G, имеющее все ребра максимального веса.
(B) В G существует цикл, имеющий все ребра максимального веса
(C) Край е не может содержаться в цикле.
(D) Все ребра в G имеют одинаковый вес

Ответ: (А)
Объяснение: Предпосылки: Для связного и ненаправленного графа остовное дерево этого графа является подграфом, который является деревом и соединяет все вершины вместе.

  1. Остовное дерево имеет ровно V — 1 ребер.
  2. В одном графе может быть много разных связующих деревьев. Минимальное связующее дерево (MST) или минимальное весовое остовное дерево для взвешенного, связного и ненаправленного графа — это остовное дерево с весом, меньшим или равным весу любого другого остовного дерева. Вес остовного дерева — это сумма весов, присвоенных каждому ребру остовного дерева.
  3. Может быть более одного возможного связующего дерева графа. Например, график в этом вопросе имеет 6 возможных связующих деревьев.
  4. MST имеет самый легкий край каждого среза. Помните алгоритм Прима, который в основном выбирает самый легкий край из каждого среза.

Выбор этого вопроса:
а) В G существует сечение, имеющее все ребра максимального веса : это правильно. Если в MST имеется самое тяжелое ребро, то существует разрез со всеми ребрами с весом, равным ребру тяжести. Смотрите пункт 4, обсуждаемый выше.

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

ВОРОТА | Gate IT 2005 | Вопрос 52

0.00 (0%) 0 votes