Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R Assertion A: Kruskal's algorithm and Prim's algorithm always produce minimum spanning tree (MST). Reason R: Every connected graph has a unique MST. In the light of the above statements, choose the most appropriate answer from the options given below
Evaluating Kruskal's, Prim's Algorithms & MST Uniqueness
Assertion A: Kruskal's and Prim's Algorithms Produce MST
Assertion A states that Kruskal's algorithm and Prim's algorithm always produce a Minimum Spanning Tree (MST).
- Kruskal's algorithm and Prim's algorithm are standard, proven greedy algorithms designed specifically to find an MST for a connected, undirected graph with weighted edges.
- They are guaranteed to find a spanning tree with the minimum possible total edge weight.
- Therefore, Assertion A is correct.
Reason R: Connected Graphs Have Unique MST
Reason R states that every connected graph has a unique MST.
- This statement is not always true.
- A connected graph has a unique MST if and only if all its edge weights are distinct.
- If a graph contains multiple edges with the same minimum weight, it is possible to construct different spanning trees that qualify as MSTs.
- For example, consider a graph with edges of equal weight; multiple spanning trees could have the same minimum total weight.
- Therefore, Reason R is incorrect.
Conclusion
Since Assertion A is correct and Reason R is incorrect, the most appropriate choice is that A is correct but R is not correct.
Important Questions from Spanning Tree
- 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$?
The maximum value of 𝑥 such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is _________ . (answer in integer)
