PowerPoint Presentation
Lecture 8
Minimum Spanning Trees (MST)
MST problem
Cut property
Prim’s Algorithm
Kruskal’s Algorithm
Cut Property for MST
For any cut (S, V-S) in a connected weighted graph G = (V, E, w), any least-weight crossing edge e = (u,v) with u ∈ S and v ∈ V – S is in some MST of G.
A cut of a graph G = (V,E) is a partition of its vertices V into two nonempty disjoint subsets, S and V − S. A crossing edge is an edge that connects a vertex in one of the subsets with a vertex in the other.
Proof: Let T be an MST of G.
T has a path from u to v.
u ∈ S and v ∈ V – S, so the path has some edge e’ = (x,y) with x ∈ S and y ∈ V – S.
T’ = T – {e’} ∪ {e} is a spanning tree of G, and w(T’) = w(T) – w(e’) + w(e).
But e is a least-weight edge crossing cut (S, V – S):
Therefore w(e) ≤ w(e’).
Therefore w(T’) ≤ w(T).
Therefore T’ is an MST of G, and contains e.
Cycle Property for MST
Let e = (u,v) be a maximum-weight edge in a cycle in a connected weighted graph G = (V, E, w). Then e is not in some MST of G.
Prim’s Algorithm
Prim’s Algorithm
Prim’s and Kruskal’s algorithms for MST based on different choices of cut (S, V – S).
What is the relevant cut for Prim?
Let S be subset of vertices in current tree.
Add cheapest edge with exactly one endpoint in S.
Cut property asserts that e is in MST.
Kruskal’s Algorithm
Kruskal’s Algorithm
What is the relevant cut for Kruskal?
Edges are in sorted order.
If adding e = (u,v) does not create cycle, then e is min-weight edge with exactly one endpoint in S.
Cut property asserts that e is in MST.
Analysis:
Time = Tsort + Θ(V) · TMakeset + Θ(E) · (TFind + TUnion)
= O(E lg E) + + Θ(V) + Θ(E)O(lg V)
= O(E lg V) + + Θ(V) + O(E lg V)
= O(E lg V)
/docProps/thumbnail.jpeg