2.3. Cost of Spanning Trees

Try these first

1. 1.

   What constitutes a spanning tree?

   Hint

   Think about the characteristics of trees in graph theory.

2. 2.

   How many edges does a tree with n vertices have?

   Hint

   Consider how trees connect vertices.

3. 3.

   What is a Minimum Cost Spanning Tree?

   • A tree that connects all nodes with minimum edges
   • A tree with the least edge weight
   • A cycle-free graph

   Hint

   Focus on the 'minimum cost' aspect.

4. 4.

   True or False: Kruskal's Algorithm starts from a single vertex.

   • True
   • False

   Hint

   Consider how each algorithm approaches its start.

5. 5.

   Given a set of vertices and weighted edges, illustrate both Prim's and Kruskal's algorithms step by step on your graph.

   Hint

   Ensure to represent cycles correctly throughout the process.

6. 6.

   In a graph where weights are randomly assigned, identify a scenario where Kruskal’s might be more efficient than Prim's.

   Hint

   Consider the nature of the graph and available edges.