Detailed Discussion of Spanning Trees
A spanning tree T of an nondirected graph G is a subgraph that itself is a tree that includes all vertices of G, with a minimum possible number of edges. In general, a graph may have several spanning trees. This concept has a lot of implications regarding optimization of tree structure and traversal. Let us have a look at this idea.
10.2.1 Motivation
The topic of spanning trees is motivated by a graph-optimization problem.
A graph of Atlantis University (Figure 10.2.1) shows that there are four campuses in the system. A new secure communications system is being installed and the objective is to allow for communication between any two campuses; to achieve this objective, the university must buy direct lines between certain pairs of campuses. Let G be the graph with a vertex for each campus and an edge for each direct line. Total communication is equivalent to G being a connected graph. This is due to the fact that two campuses can communicate over any number of lines. To minimize costs, the university wants to buy a minimum number of lines.
Figure 10.2.1 Atlantis University Graph
The solutions to this problem are all trees. Any graph that satisfies the requirements of the university must be connected, and if a cycle does exist, any line in the cycle can be deleted, reducing the cost. Each of the sixteen trees that can be drawn to connect the vertices North, South, East, and West (see Exercise 10.1.3.1) solves the problem as it is stated. Note that in each case, three direct lines must be purchased. There are two considerations that can help reduce the number of solutions that would be considered.
- Objective 1: Given that the cost of each line depends on certain factors, such as the distance between the campuses, select a tree whose cost is as low as possible.
- Objective 2: Suppose that communication over multiple lines is noisier as the number of lines increases. Select a tree with the property that the maximum number of lines that any pair of campuses must use to communicate with is as small as possible.
Typically, these objectives are not compatible; that is, you cannot always simultaneously achieve these objectives. In the case of the Atlantis university system, the solution with respect to Objective 1 is indicated with solid lines in Figure 10.2.1. There are four solutions to the problem with respect to Objective 2: any tree in which one campus is directly connected to the other three. One solution with respect to Objective 2 is indicated with dotted lines in Figure 10.2.1. After satisfying the conditions of Objective 2, it would seem reasonable to select the cheapest of the four trees.
10.2.2 Definition
Definition 10.2.2 Spanning Tree. Let G = (V, E) be a connected undirected graph. A spanning tree for G is a spanning subgraph 9.1.16 of G that is a tree.
Note 10.2.3
(a) If (V, E′) is a spanning tree, |E′| = |V | − 1.
(b) The significance of a spanning tree is that it is a minimal spanning set.
A smaller set would not span the graph, while a larger set would have a cycle, which has an edge that is superfluous.
For the remainder of this section, we will discuss two of the many topics that relate to spanning trees. The first is the problem of finding Minimal Spanning Trees, which addresses Objective 1 above. The second is the problem of finding Minimum Diameter Spanning Trees, which addresses Objective 2.
Definition 10.2.4 Minimal Spanning Tree. Given a weighted connected undirected graph G = (V, E, w), a minimal spanning tree is a spanning tree
(V, E′) for which 
, w(e) is as small as possible.
10.2.3 Prim's Algorithm
Unlike many of the graph-optimization problems that we've examined, a solution to this problem can be obtained efficiently. It is a situation in which a greedy algorithm works.
Definition 10.2.5 Bridge. Let G = (V, E) be an undirected graph and let {L, R} be a partition of V . A bridge between L and R is an edge in E that connects a vertex in L to a vertex in R.
Theorem 10.2.6 Let G = (V, E, w) be a weighted connected undirected graph. Let V be partitioned into two sets L and R. If e∗is a bridge of least weight between L and R, then there exists a minimal spanning tree for G that includes e∗.
Proof. Suppose that no minimal spanning tree including e∗ exists. Let T = (V, E′) be a minimal spanning tree. If we add e∗ to T, a cycle is created, and this cycle must contain another bridge, e, between L and R. Since w (e∗) ≤ w(e), we can delete e and the new tree, which includes e∗ must also be a minimal spanning tree.
Example 10.2.7 Some Bridges. The bridges between the vertex sets {a, b, c}and {d, e} in Figure 10.2.8 are the edges {b, d} and {c, e}. According to the theorem above, a minimal spanning tree that includes {b, d} exists. By examination, you should be able to see that this is true. Is it true that only the bridges of minimal weight can be part of a minimal spanning tree?
Figure 10.2.8 Bridges between two sets
Theorem 10.2.6 essentially tells us that a minimal spanning tree can be constructed recursively by continually adding minimally weighted bridges to a set of edges.
Algorithm 10.2.9 Prim's Algorithm. Let G = (V, E, w) be a connected, weighted, undirected graph, and let v0 be an arbitrary vertex in V . The following steps lead to a minimal spanning tree for G. L and R will be sets of vertices and E′ is a set of edges.
(1) (Initialize) L = V − {v0}; R = {v0}; E′ = ∅.
(2) (Build the tree) While L ≠ ∅:
(1) Find e∗ = {vL, vR}, a bridge of minimum weight between L and R.
(2) R = R ∪{vL};L = L − {vL}; E′ = E′ ∪{e∗}
(3) Terminate with a minimal spanning tree (V, E′).
Note 10.2.10
(a) If more than one minimal spanning tree exists, then the one that is obtained depends on v0 and the means by which e∗ is selected in Step 2.
(b) Warning: If two minimally weighted bridges exist between L and R, do not try to speed up the algorithm by adding both of them to E'.
(c) That Algorithm 10.2.9 yields a minimal spanning tree can be proven by induction with the use of Theorem 10.2.6.
(d) If it is not known whether G is connected, Algorithm 10.2.9 can be re- vised to handle this possibility. The key change (in Step 2.1) would be to determine whether any bridge at all exists between L and R. The condition of the while loop in Step 2 must also be changed somewhat.
Example 10.2.11 A Small Example. Consider the graph in Figure 10.2.12. If we apply Prim's Algorithm starting at a, we obtain the following edge list in the order given: {a, f}, {f,e}, {e, c}, {c, d}, {f,b}, {b, g}. The total of the weights of these edges is 20. The method that we have used (in Step 2.1) to select a bridge when more than one minimally weighted bridge exists is to order all bridges alphabetically by the vertex in L and then, if further ties exist, by the vertex in R. The first vertex in that order is selected in Step 2.1 of the algorithm.
Figure 10.2.12 A small weighted graph
Definition 10.2.13 Minimum Diameter Spanning Tree. Given a connected undirected graph G = (V, E), find a spanning tree T = (V, E′) of G such that the longest path in T is as short as possible.
Example 10.2.14 The Case for Complete Graphs. The Minimum Diameter Spanning Tree Problem is trivial to solve in a Kn. Select any vertex v0 and construct the spanning tree whose edge set is the set of edges that connect v0 to the other vertices in the Kn. Figure 10.2.15 illustrates a solution for n = 5.
Figure 10.2.15 Minimum diameter spanning tree for K5
For incomplete graphs, a two-stage algorithm is needed. In short, the first step is to locate a "center" of the graph. The maximum distance from a center to any other vertex is as small as possible. Once a center is located, a breadth-first search of the graph is used to construct the spanning tree.
Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.