2. Minimum Cost Spanning Trees

Try these first

1. 1.

   What is a spanning tree?

   Hint

   Think about the properties of trees.

2. 2.

   What does MCST stand for?

   Hint

   Consider what the objective of the spanning tree is.

3. 3.

   What does Minimum Cost Spanning Tree (MCST) refer to?

   • A tree with the largest weight
   • A tree that costs the least to connect all vertices
   • A tree with no nodes

   Hint

   Think about the objective of spanning trees.

4. 4.

   True or False: Prim's Algorithm starts from the smallest weight edge and builds the tree incrementally.

   • True
   • False

   Hint

   Consider the methodology used by each algorithm.

5. 5.

   Given a graph with specified vertices and weighted edges, calculate both Prim's and Kruskal's Minimum Cost Spanning Trees and compare the results.

   Hint

   Focus on the ways each algorithm approaches edge selection.

6. 6.

   Create a graph that contains several cycles and explain how Prim's and Kruskal's algorithms would handle it during the construction of the MCST.

   Hint

   Consider the properties of cycles in the context of spanning trees.