Рубрики

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 24

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

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change

(A) только P

(B) только Q
(С) Ни P, ни Q
(D) и P и Q

Ответ: (А)
Объяснение: кратчайший путь может измениться. Причина в том, что может быть разное количество ребер на разных путях от s до t. Например, пусть кратчайший путь имеет вес 15 и имеет 5 ребер. Пусть будет еще один путь с 2 ребрами и общим весом 25. Вес самого короткого пути увеличится на 5 * 10 и станет 15 + 50. Вес другого пути увеличится на 2 * 10 и станет 25 + 20. Таким образом, кратчайший путь меняется на другой путь с весом 45.

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

ВОРОТА | GATE-CS-2016 (набор 1) | Вопрос 24

0.00 (0%) 0 votes