2.5. Building a Minimum Cost Spanning Tree

Try these first

1. 1.

   What is a spanning tree?

   Hint

   Think about how trees connect branches.

2. 2.

   Name one application of Minimum Cost Spanning Trees.

   Hint

   Consider situations that involve connectivity.

3. 3.

   Which of the following statements is true regarding Minimum Cost Spanning Trees?

   • Every spanning tree has cycles.
   • A Minimum Cost Spanning Tree is the most expensive spanning tree.
   • A Minimum Cost Spanning Tree connects all vertices without cycles.

   Hint

   Recall the definition of a spanning tree.

4. 4.

   Prim's algorithm builds an MST by:

   • Connecting random edges.
   • Adding edges in descending order of cost.
   • Expanding from the smallest edge incrementally.

   Hint

   Think about the strategy of growth in this algorithm.

5. 5.

   Given a graph with vertices A, B, C, and D having edges AB (weight 5), AC (weight 3), AD (weight 4), BC (weight 2), and BD (weight 1). Find the Minimum Cost Spanning Tree using both Prim’s and Kruskal’s algorithms. Illustrate each step.

   Hint

   Visualize the graph as you proceed to understand better.

6. 6.

   Construct a real-world scenario involving travel routes and use Kruskal's algorithm to minimize the costs of travel while ensuring all points are accessible. Illustrate with steps.

   Hint

   Ensure to account for cost efficiency in your scenario.