Minimum Spanning Trees

• Read section 4.3, pages 94-99
  • What do we refer to as a spanning tree of a graph \(G\)?
    • What are the order and size of such a spanning tree?
  • The book describes two ways to produce a spanning tree, one by adding edges to an initially empty graph and another by removing edges from a more complete graph. Describe in more details those two ways.
  • Prove theorem 4.10: Every connected graph contains a spanning tree.
  • What do we refer to as a weighted graph?
  • How do we compute the weight of a subgraph of a weighted graph?
  • What is the Minimum Spanning Tree Problem?
  • Describe Kruskal’s Algorithm for locating a minimum spanning tree of a weighted graph.
  • Prove that Kruskal’s algorithm does indeed produce a minimum spanning tree. This consists of two parts:
    • Proving that the result of the construction is indeed a spanning tree.
    • Proving that it is a minimum spanning tree.
  • Describe Prim’s Algorithm for locating a minimum spanning tree of a weighted graph.
  • How do Kruskal’s and Prim’s algorithms differ?
  • Prove that Prim’s Algorithm does indeed produce a minimum spanning tree.
  • Work out problem 4.26
  • Practice Problems: 4.25, 4.27