Discussion
Let \(G\) be any undirected graph with positive edge weights, and \(T\) be a minimum spanning tree of \(G\). For any two vertices, \(u\) and \(v\), let \(d_{1}(u, v)\) and \(d_{2}(u, v)\) be the shortest distances between \(u\) and \(v\) in \(G\) and \(T\), respectively. Which ONE of the options is CORRECT for all possible \(G\), \(T\), \(u\) and \(v\)?
Answer: B
For all graphs, \(d_{1}(u, v) \le d_{2}(u, v)\).
The minimum spanning tree T is a subgraph of G, so the unique path between u and v in T is also a path in G. The shortest path in G can only be as short as that path or shorter, so \(d_{1} \le d_{2}\).
Equality need not hold, because an MST minimises total weight, not individual distances. In a triangle with edges u-v of weight 3 and u-w, w-v of weight 2 each, the MST keeps the two edges of weight 2, so \(d_{2}(u, v) = 4\) while \(d_{1}(u, v) = 3\). That example rules out '=' and '\(\ge\)', and the case where u and v are joined by an MST edge rules out '\(\ne\)'.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development