Spanning Trees

  • Given an undirected graph, a spanning tree T is a subgraph of G, where T:
    • These two properties make it a tree.
      • Is connected.
      • Is acyclic.
    • This makes it spanning.
      • Includes all of the vertices.
  • Example:
    • Spanning tree is the black edges and vertices.
  • A Minimum Spanning Trees is a spanning tree of minimum total weight.
    • Example: Directly connecting buildings by power lines.
  • A Minimum Spanning Trees is a spanning tree of minimum total weight.
    • Example: Directly connecting buildings by power lines.