Discussion
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
Answer: A
The answer is P only.
P is true. Every spanning tree has exactly \(|V| - 1\) edges, so adding the same constant to every edge raises every tree's total by the same amount. The order of trees by weight is unchanged, and so is the minimum spanning tree. (Kruskal's algorithm also sees the same order of edges.)
Q is false. Paths have different numbers of edges, so the increase depends on path length. For example, a direct edge of weight 6 against a two-edge path of weights 2 + 3: before, the two-edge path (5) is shorter; after adding 2 to each edge, it costs 9 while the direct edge costs 8. Paths with more edges are penalized more.
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