Chapter 11 Simple Graphs338
by suitable tie-breaking.
The coloring that explains Algorithm 1 also justifies a more flexible algorithm
which has Algorithm 1 as a special case:
Algorithm 3.Grow a forest one edge at a time by picking any component and
adding a minimum-weight edge among the edges leaving that component.
This algorithm allows components that are not too close to grow in parallel and
independently, which is great for “distributed” computation where separate proces-
sors share the work with limited communication between processors.
These are examples of greedy approaches to optimization. Sometimes it works
and sometimes it doesn’t. The good news is that it works to find the MST. So we can
be sure that the MST for our example graph has weight 17 since it was produced by
Algorithm 2. And we have a fast algorithm for finding a minimum-weight spanning
tree for any graph.
Ok, to wrap up this story, all that’s left is the proof that extending edges are the
same as minimal gray edges. This might sound like a chore, but it just uses the
same reasoning we use to be sure there will be a gray edge when you need it.
Proof. (of Lemma 11.11.10)
LetFbe a pre-MST that is a subgraph some some MSTMofG, and supposee
is a minimum weight gray edge under some solid coloring ofF. We want to show
thatFCeis also a pre-MST.
Ifehappens to be an edge ofM, thenFCeremains a subgraph ofM, and so
is a pre-MST.
The other case is wheneis not an edge ofM. Then sinceMis a spannning tree,
MCeis a spanning subgraph. AlsoMhas a pathpbetween the different colored
endpoints ofe, soMCehas a cycle consisting ofetogether withp. Nowphas
both a black endpoint and a white one, so it must contain some gray edgeg¤e.
The trick is to removegfromMCeto obtain a subgraphMCe g. We claim
thatMCe gis an MST that containsFCe, which shows thateextendsF.
We begin proving the claim with the observation thatMCe gcontainsFCe,
which follows because gray edges likegare by definition not edges ofF. Also,
since the weightw.e/is minimum among gray edges,w.MCe g/is at most
w.M/, the minimum possible weight of a spanning tree. So to confirm thatMC
e gis an MST containingFCe, we just have to show thatMCe gis a
spanning tree,
ButM Ceis a spanning subgraph, andgis on a cycle ofM Ce, so by
Lemma 11.9.5, removinggwon’t disconnect anything, which means thatMCe g
is still a spanning subgraph. Moreover,MCe ghas the same number of edges
asM, so Lemma 11.11.4 confirms that it must be a tree, as claimed.