2.1. Problem Motivation

Try these first

1. 1.

   Define a spanning tree.

   Hint

   Look for the main properties of trees.

2. 2.

   Why do we need to minimize costs in Minimum Cost Spanning Trees?

   Hint

   Think about government budgets after disasters.

3. 3.

   What is a Minimum Cost Spanning Tree?

   • A tree that connects all vertices without loops
   • The most expensive tree
   • Any tree in a graph

   Hint

   Recall the definition we discussed.

4. 4.

   True or False: A spanning tree can have cycles.

   • True
   • False

   Hint

   Think about the properties of trees.

5. 5.

   Given a tree with six vertices connected with edges weighted as follows: A-B (10), A-C (15), B-D (5), B-E (10), and C-F (20). Calculate the minimum cost spanning tree.

   Hint

   Start with the smallest weights but remember to maintain connectivity.

6. 6.

   Design a spanning tree connecting five locations in a park with the following distances (weights): A-B (2), A-C (6), B-C (3), B-D (9), C-E (5). What's the least costly way to connect all?

   Hint

   Work systematically from the lowest weights, ensuring no cycles.