Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 83

Пусть s и t две вершины в неориентированном графе G + (V, E), имеющие различные веса положительных ребер. Пусть [X, Y] такое разбиение V, что s ∈ X и t ∈ Y. Рассмотрим ребро e, имеющее минимальный вес среди всех ребер, имеющих одну вершину в X и одну вершину в Y

Край е должен определенно принадлежать:
(А) минимальный взвешенный остове G
(B) взвешенный кратчайший путь от s до t
(С) каждый путь от с до т
(D) взвешенный самый длинный путь от s до t

Ответ: (А)
Пояснение: Минимальный весовой предел на любом срезе всегда является частью MST. Это называется Cut Property .

Это идея, используемая в алгоритме Прима . Минимальный вес обрезной кромки — это всегда минимальная граница остовного дерева.

Почему B (взвешенный кратчайший путь от s до t) не является ответом?
См. Пример ниже, край 4 (самый светлый в выделенном красном отрезке от s до t) не является частью кратчайшего пути.

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

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

ВОРОТА | GATE-CS-2005 | Вопрос 83

0.00 (0%) 0 votes