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
Problem: how to (efficiently) find MST for graph G?
|
![[prev]](icon/prev.gif){kind=icon}
![[index]](icon/up.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}