Past exam question: 2064 Jestha, Q10(b)
Open in the Padhaiko appQuestion
Write short notes on: b) Minimum cost spanning trees
Solution
Minimum Cost Spanning Trees (MST): For a connected, undirected, weighted graph , a spanning tree is an acyclic connected subgraph spanning all vertices with edges. A minimum cost spanning tree (MST) is a spanning tree whose sum of edge weights is as small as possible.
- Standard Algorithms: Kruskal's algorithm (, greedy edge sorting + Union-Find) and Prim's algorithm (, greedy vertex growth from a root).
- Applications: Designing minimum-cost road/telecom/fiber networks and power grids.
Answer:
A minimum cost spanning tree (MST) connects all vertices of a weighted undirected graph using acyclic edges with minimum total weight, computed via Kruskal's or Prim's algorithm.