Skip to main content
Logo image

Applied Discrete Structures

Section 10.2 Spanning Trees

Subsection 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.
described in detail following the image
Atlantis University Graph
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.

Subsection 10.2.2 Definition

Note 10.2.3.

  1. If (V,Eβ€²) is a spanning tree, |Eβ€²|=|V|βˆ’1.
  2. 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 βˆ‘e∈Eβ€²w(e) is as small as possible.

Subsection 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.

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?
described in detail following the image
Bridges between two sets
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.

Note 10.2.10.

  1. 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.
  2. 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’.
  3. That Algorithm 10.2.9 yields a minimal spanning tree can be proven by induction with the use of Theorem 10.2.6.
  4. If it is not known whether G is connected, Algorithm 10.2.9 can be revised 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.
described in detail following the image
A weighted graph
Figure 10.2.12. A small weighted graph
For small examples, the following table is a suggested way to demonstrate an understanding of how Prim’s algorithm plays out. The first line, step 0, is the initialization of the two sets, L and R. In completing Step 3, there are two bridges of minimal weight, {e,c} and {e,d}. We selected the former. If we had selected the latter, the resulting spanning tree would be different, but would have the same total weight.
Table 10.2.13. Prim’s Algorithm Steps
Step Added Bridge L R Added Weight
0 - {b,c,d,e,f,g} {a} -
1 {a,f} {b,c,d,e,g} {a,f} 3
2 {e,f} {b,c,d,g} {a,e,f} 4
3 {e,c} {b,d} {a,c,e,f} 3
4 {c,d} {b,g} {a,c,d,e,f} 2
5 {f,b} {g} {a,b,c,d,e,f} 5
6 {b,g} {} {a,b,c,d,e,f,g} 3
Total weight 20

Definition 10.2.14. 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. A solution to this problem is relatively easy to obtain by combining the idea the center of a graph with the breadth first search.

Example 10.2.15. 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.16 illustrates a solution for n=5.
described in detail following the image
Minimum diameter spanning tree for K_5
Figure 10.2.16. 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.

Exercises 10.2.4 Exercises

1.

Suppose that after Atlantis University’s phone system is in place, a fifth campus is established and that a transmission line can be bought to connect the new campus to any old campus. Is this larger system the most economical one possible with respect to Objective 1? Can you always satisfy Objective 2?
Answer.
It might not be most economical with respect to Objective 1. You should be able to find an example to illustrate this claim. The new system can always be made most economical with respect to Objective 2 if the old system were designed with that objective in mind.

3.

Find a minimal spanning tree for the following graphs.
described in detail following the image
Figure for exercise-10-2-4a
Figure 10.2.17.
described in detail following the image
Figure for exercise-10-2-4b
Figure 10.2.18.
described in detail following the image
Figure for exercise-10-2-4c
Figure 10.2.19.
Solution.
  1. There are three minimal spanning tree, with edges {0,5},{0,3},{4,5} and any two of the following edges {0,1},{0,2},{1,2}.
  2. There is only one minimal spanning tree. If we start with BOS as the β€œright set”, the edges in the following set are ordered according to how they are added in Prim’s Algorithm: {{BOS,NY},{NY,PHI},{PHI,DC},{DC,ATL},{PHI,KC},{KC,CHI},{KC,LA},{LA,SF}}.
  3. There is only one minimal spanning tree, which has edges {{1,8},{2,8},{2,7},{3,7},{3,6},{4,6},{4,5}}

4.

Find a minimal spanning tree for the following graph using Prim’s algorithm starting at vertex 1. Your tree will not be unique. How many different minimal spanning trees are there?
described in detail following the image
A graph with several different minimal spanning trees.
Figure 10.2.20.

5.

In each of the following parts justify your answer with either a proof or a counterexample.
  1. Suppose a weighted undirected graph had distinct edge weights. Is it possible that no minimal spanning tree includes the edge of minimal weight?
  2. Suppose a weighted undirected graph had distinct edge weights. Is it possible that every minimal spanning tree includes the edge of maximal weight? If true, under what conditions would it happen?
Solution.
  1. No, every minimal spanning tree will include the edge of minimal weight? At some point, the edge of minimal weight will be part of a bridge between two sets and will be included in the spanning tree.
  2. Yes, this will happen if the edge of maximal weight is the only bridge between two sets.

7.

Find a minimum diameter spanning tree for the following graphs.
described in detail following the image
Figure for exercise-10-2-5a
Figure 10.2.21.
described in detail following the image
Figure for exercise-10-2-5b
Figure 10.2.22.
Solution.
  1. Edges in one solution are: {8,7},{8,9},{8,13},{7,6},{9,4},{13,12},{13,14},{6,11},{6,1},{1,2},{4,3},{4,5},{14,15}, and {5,10}
  2. Vertices 8 and 9 are centers of the graph. Starting from vertex 8, a minimum diameter spanning tree is
    {{8,3},{8,7},{8,13},{8,14},{8,9},{3,2},{3,4},{7,6},{13,12},{13,19},{14,15},{9,16},{9,10},{6,1},{12,18},{16,20},{16,17},{10,11},{20,21},{11,5}}.
    The diameter of the tree is 7.
You have attempted 1 of 1 activities on this page.