6.3 MINIMUMSPANNINGTREE PROBLEMA spanning tree of an undirected graph G(N, A) has already been defined as a tree of the graph G that contains the complete set of nodes, N, of G (see also Figure 6.9). The minimumspanningtree problem is then concerned with finding the one among all possible spanning trees of a graph G(N, A) with the minimum total link length. If the number of nodes in the set N is n, then all spanning trees of G obviously contain n  1 links. Just as in the case of shortestpath problems, the minimumspanningtree
(MST) problem has direct applications of its own, primarily in problems of
transportation network design, and also constitutes an important building
block in some solution approaches to other more complex problems such as
nodecovering problems (see Section 6.4). For a brief example of an
application of the MST problem, consider the case in which map locations
of n rural towns are given along with a matrix listing the Euclidean
distances (or some other measure of distance, time, or cost) between all
possible pairs of towns. The MST can be interpreted in this case as the
minimum length of roads needed to connect, directly or indirectly, all
pairs of towns, assuming that all road segments (links) begin and end in
some pair of towns.
The last sentence emphasizes the distinction between the MST problem
and the socalled "Steiner problem." The latter has the same objective
as the former but allows the introduction of artificial "nodes" (i.e.,
links can meet anywhere on the plane instead of only at the specified
points that are to be spanned). To illustrate this further, consider
four towns that lie at the corners of a unit square. Obviously, one solution
to the MST problem in this case is the one shown in Figure 6.10a; the
total length of the minimum spanning tree is 3 units. On the other hand,
it can be shown that if creation of artificial nodes is permitted
(Steiner,s problem), the total line length needed to connect the four
points can be further reduced. The solution to Steiner's problem in this
case is shown in Figure 6.10b and involves creation of two artificial
nodes (A and B in Figure 6.10b); the total length of the Steiner tree is
1 + in this case.
