MST II
Concept
Cut property
fix G a set
if
let T be MST of G that includes F
- if e = uv in T => good
- if e = uv not inn T
- consider T+e, there is a cycle with e
- take T’ = T+e-f
- T’ is a spanning tree and cost(T’) <= cost(T)
MST
Removing edges
if e is part of a cycle in a connected graph G, the graph G-e is also connected
Any MST includes the minimum cost edge
claim: for every G, there is a MST T’ of G that includes its edge e with minimum cost c_e
fix any MST T of G
if e inn T => good
if e not inn T
by exchange argument, consider T+e
it would have a cycle with e and some other edge f
then, take T' = T+e-f
T' is connected => T' is a spanning tree of G
its cost is
cost(T') = cost(T) + c_e - c_f, and c_e <= c_f
<= cost(T)
so T ' is an MST if it includes e
The smallest weight edge at every vertex is in the MST
claim: for every edge e=uv with minimum cost among all edges incident to u, there is a MST of G that includes e
same exchange argument as previous
f
.---.u
| :
| :e
| :
.---.v
Cut
a partition of V into two nonempty sets
cut is the set of edges
MST is built on the smallest edge in a cut
for every G and every non-trivial partition (S, V-S) of V, if e has minimum cost c_e among the edges in
same exchange argument
Prim’s algorithm
Kruskal’s algorithm
Kruskal(G,w)
sort edges by increasing weight
UFDS(|V|)
T = empty array
for edge {u,v} in sorted order:
if Find(u) != Find(v):
add {u,v} to T
Union(u,v)
return T