Discussion
Let \(G\) be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant \(\alpha\) is added to the weight of every edge.
Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in \(G\) before and after the edge weight update?
Answer: C
Every MST remains an MST, and SPs need not remain SPs.
Every spanning tree of a graph with n vertices has exactly n - 1 edges. Adding α to every edge raises the weight of every spanning tree by the same amount, (n - 1)α, so their order by weight is unchanged and the minimum ones stay minimum.
Paths are different: a path with k edges gains kα, so paths with more edges are penalised more. Example: a direct edge u-v of weight 3 against a two-edge path u-w-v of weights 1 and 1. Before the update the two-edge path (2) is shorter; after adding α = 2 it costs 6 while the direct edge costs 5. So a shortest path need not stay shortest, which rules out the two options claiming that every SP survives, and the MST argument rules out the other.
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