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)
|