Introduction to Algorithms, Third Edition

partition the set
V
of vertices into two sets
V
1
and
V
2
such that
j
V
1
j
and
j
V
2
j
differ

---

638
Chapter 23
Minimum Spanning Trees
by at most
1
. Let
E
1
be the set of edges that are incident only on vertices in
V
1
, and
let
E
2
be the set of edges that are incident only on vertices in
V
2
. Recursively solve
a minimum-spanning-tree problem on each of the two subgraphs
G
1
D
.V
1
; E
1
/
and
G
2
D
.V
2
; E
2
/
. Finally, select the minimum-weight edge in
E
that crosses the
cut
.V
1
; V
2
/
, and use this edge to unite the resulting two minimum spanning trees
into a single spanning tree.
Either argue that the algorithm correctly computes a minimum spanning tree
of
G
, or provide an example for which the algorithm fails.
Problems
23-1
Second-best minimum spanning tree
Let
G
D
.V; E/
be an undirected, connected graph whose weight function is
w
W
E
!
R
, and suppose that
j
E
j j
V
j
and all edge weights are distinct.
We define a second-best minimum spanning tree as follows. Let
T
be the set
of all spanning trees of
G
, and let
T
0
be a minimum spanning tree of
G
. Then
a
second-best minimum spanning tree
is a spanning tree
T
such that
w.T /
D
min
T
00
2
T
f
T
0
g
f
w.T
00
/
g
.