Рубрики

ВОРОТА | GATE-CS-2000 | Вопрос 41

Пусть G — неориентированный связный граф с различным весом ребер. Пусть emax будет ребром с максимальным весом, а emin — ребром с минимальным весом. Какое из следующих утверждений является ложным?
(A) Каждое минимальное остовное дерево G должно содержать emin
(B) Если emax находится в минимальном остовном дереве, то его удаление должно отключить G
(C) Минимальное связующее дерево не содержит emax
(D) G имеет уникальное минимальное остовное дерево

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

В алгоритме Крускала мы выбираем ребра в порядке возрастания и добавляем их в лес, если цикл не сформирован. Вариант A имеет значение True, потому что первое ребро никогда не может создать цикл.
Единственная причина, по которой emax присутствует в минимальном остовном дереве, может заключаться в том, что он является единственным возможным ребром, покрывающим определенную вершину в дереве, поскольку все вершины должны присутствовать в остовном дереве по определению. Посмотрите на изображение ниже

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

ВОРОТА | GATE-CS-2000 | Вопрос 41

0.00 (0%) 0 votes