Let G be a weighted connected undirected graph with distinct positive edge…

GATE · 2016 · CS · Set 1 · Computer Science & IT

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 path between any pair of vertices does not change

  1. A.

    P only

  2. B.

    Q only

  3. C.

    Neither P nor Q

  4. D.

    Both P and Q

Attempted by 346 students.

Show answer

Correct answer: A

The worked solution is available to enrolled students.

Video solution available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…