Let G be a weighted connected undirected graph with distinct positive edge weights If every edge weight is increased by the same value then which of the following statements isare TRUE P Minimum spanning tree of G does not change Q Shortest pat

The Eduladder is a community of students, teachers, and programmers just interested to make you pass any exams. So we solve previous year question papers for you.
See Our team
Wondering how we keep quality?
Got unsolved questions?

Ask Questions
Gate-cs-2016-->View question


Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest pat


(A) P only
(B) Q only
(C) Neither P nor Q
(D) Both P and Q



By:13priya

Taged users:


Likes:
Be first to like this question

Dislikes:
Be first to dislike this question

Talk about thisDelete|Like|Dislike|


Answers

(A) P only
Explanation: The shortest path may change. The reason is, there may be different number of edges in different paths from s to t. For example, let shortest path be of weight 15 and has 5 edges. Let there be another path with 2 edges and total weight 25. The weight of the shortest path is increased by 5*10 and becomes 15 + 50. Weight of the other path is increased by 2*10 and becomes 25 + 20. So the shortest path changes to the other path with weight as 45.
The Minimum Spanning Tree doesn’t change. Remember the Kruskal’s algorithm where we sort the edges first. IF we increase all weights, then order of edges won’t change

Aparna-Dasgupta

Likes:
Be first to like this answer

Dislikes:
Be first to dislike this answer
Talk about this|Once you have earned teacher badge you can edit this questionDelete|Like|Dislike|
------------------------------------

Can you help us to add better answer here? Please see this



Not the answer you're looking for? Browse other questions from this Question paper or ask your own question.

Join eduladder!