Рубрики

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

GATE

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

Ответ: (А)
Пояснение: Предположим, что кратчайший путь из A-> B равен 6, но в MST мы имеем A-> C-> B (A-> C = 4, C-> B = 3), затем по пути в MST мы иметь минимальную загруженность, т.е. 4
Тест на этот вопрос

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

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

0.00 (0%) 0 votes