Project ForgeLet 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.
- P only
- BQ only
- CNeither P nor Q
- DBoth P and Q
Explanation
P is TRUE: every spanning tree has exactly (n−1) edges, so adding a constant c to every edge weight adds the SAME total amount, c(n−1), to every spanning tree's weight — their relative ranking is unchanged, so whichever tree was minimum stays minimum. Q is FALSE: different paths between a pair of vertices can have different NUMBERS of edges, so adding c to every edge penalizes longer (more-edges) paths more than shorter ones, which can flip which path is shortest.
Source: GATE CS 2016 (Session 1 / Set A) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.