GATE CS 2016 Set 1 Q14 — Minimum Spanning Trees

To determine which statements are true, let us analyze $P$ and $Q$ individually.

Analysis of Statement $P$: Minimum Spanning Tree (MST)

Let $G = (V, E)$ be a connected undirected graph with $V$ vertices. Any spanning tree $T$ of $G$ contains exactly $V - 1$ edges.

Let the original weight of an edge $e$ be $w(e)$. If every edge weight is increased by a constant $c > 0$, the new weight of the edge becomes $w'(e) = w(e) + c$.

The total weight of any spanning tree $T$ under the new weight function is:

Since $(V - 1)c$ is a constant added to the weight of every spanning tree, the relative ordering of the weights of all spanning trees remains unchanged. Therefore, the spanning tree that minimizes $W(T)$ will also minimize $W'(T)$.

Alternatively, greedy algorithms like Kruskal's or Prim's rely solely on the relative order of edge weights. Since $w(e_1) < w(e_2) \iff w(e_1) + c < w(e_2) + c$, the sorted order of edges remains identical. Thus, the MST does not change. Statement $P$ is TRUE.

Analysis of Statement $Q$: Shortest Path

The shortest path between two vertices depends on the number of edges in the path. Adding a constant $c$ to each edge penalizes paths with more edges more heavily than paths with fewer edges.

Let us consider a counterexample:

• Suppose we have two paths between vertices $u$ and $v$:
  • Path $P_1$ consisting of $2$ edges with weights $2$ and $2$ (Total weight = $4$).
  • Path $P_2$ consisting of $1$ edge with weight $5$ (Total weight = $5$).
• Initially, the shortest path is $P_1$ with a cost of $4$.
• Now, increase every edge weight by $c = 2$:
  • New weight of $P_1 = (2 + 2) + (2 + 2) = 8$.
  • New weight of $P_2 = 5 + 2 = 7$.

After the increase, the shortest path changes to $P_2$ (cost $7$). Thus, the shortest path can change. Statement $Q$ is FALSE.

Hence, only statement $P$ is true.