11.11. Forests & Trees 335
2
3
3
7
1
2
1
(a)2
3
3
7
1
2
1
4 1
1
3
(b)Figure 11.23 A spanning tree (a) with weight 19 for a graph (b).2
3
7
1
2
1
1
Figure 11.24 An MST with weight 17 for the graph in Figure 11.23(b).is also a spanning tree of the graph shown in Figure 11.23(b), and this spanning
tree has weight 17.
What about the tree shown in Figure 11.24? Is it an MST? It seems to be, but
how do we prove it? In general, how do we find an MST for a connected graphG?
We could try enumerating all subtrees ofG, but that approach would be hopeless
for large graphs.
There actually are many good ways to find MST’s based on an invariance prop-
erty of some subgraphs ofGcalled pre-MST’s.
Definition 11.11.7.Apre-MSTfor a graphGis a spanning subgraph ofGthat is
also a subgraph of some MST ofG.
So a pre-MST will necessarily be a forest.
For example, the empty graph with the same vertices asGguaranteed to be a
pre-MST ofG, and so is any actual MST ofG.