[prev] 38 [next]

Minimum Spanning Trees

Reminder: Spanning tree ST of graph G=(V,E)
  • spanning = all vertices, tree = no cycles
    • ST is a subgraph of G   (G'=(V,E') where E' ⊆ E)
    • ST is connected and acyclic
Minimum spanning tree MST of graph G
  • MST is a spanning tree of G
  • sum of edge weights is no larger than any other ST
Applications: Computer networks, Electrical grids, Transportation networks …

Problem: how to (efficiently) find MST for graph G?

NB: MST may not be unique   (e.g. all edges have same weight ⇒ every ST is MST)