3.1. Introduction to the Problem Domain

Try these first

1. 1.

   What is a spanning tree?

   Hint

   Think about how trees connect branches without forming loops.

2. 2.

   How many edges does a spanning tree have?

   Hint

   Consider a scenario with three vertices.

3. 3.

   What does Prim's algorithm aim to find in a graph?

   • Shortest path
   • Minimum spanning tree
   • Maximum flow

   Hint

   Think about the trees in graph theory.

4. 4.

   Prim's algorithm is a type of which algorithm?

   • Greedy
   • Dynamic Programming

   Hint

   Recall the definitions of different algorithm types.

5. 5.

   Given a connected graph with vertices A, B, C, D, and edges with weights, determine the minimum spanning tree using Prim's algorithm. Provide a visual representation.

   Hint

   List out edges by weight to start.

6. 6.

   Prove that Prim's algorithm will always yield an optimal solution. Reference the minimum separator lemma in your proof.

   Hint

   Explore the implications of making improper edge selections.