Michelle Homp, Alyssa Seideman, Sean Gravelle, Andrew Hayes,
Section17.1Networks and Minimal Spanning Trees
SubsectionNetworks and Trees
A network is just another name for any connected graph. In this chapter, we will consider a certain type of network: one which connects a given set of vertices using the fewest possible edges.
Trees
For a given network, the following properties are all equivalent. That is, if any one of them is true for that network, then all the rest must also be true.
The network has no circuits.
The number of edges in the network is one fewer than the number of vertices. So, if the network has \(N\) vertices, it will have \(N1\) edges.
Every edge in the network is a bridge.
Given any pair of two vertices in the netowork, only one path exists connecting those two vertices.
A network which satisfies these properties is called a tree.
Notice, in particular, that because every edge of a tree is a bridge, removing any edge from the tree will make the graph disconnected. Thus, we can say that a tree is a graph that connects a given set of vertices using the fewest possible edges. Some examples are shown below.
Example17.1Examples of trees
Figure17.2Figure17.3
By way of comparison, here are some graphs that are not trees:
Example17.5Examples of graphs that are not trees
Figure17.6Figure17.7
We can often determine whether a graph is a tree or not without seeing a diagram. Since there are many equivalent conditions which characterize trees, we can make this determination if given even just a little information about a graph. Sometimes, however, we would still need more information to determine whether a graph is a tree. Let's look at some examples of this.
Example17.9
We are given descriptions, but not pictures, of several networks. Do we have enough information to determine whether or not each is a tree?
The network has 5 vertices and 4 edges.
Is it a tree? Yes.
Reason: It has one fewer edge than the number of vertices.
The network has 5 vertices and 6 edges.
Is it a tree? No.
Reason: It has one more edge than the number of vertices.
The network has 8 vertices, and between vertices A and B, there is only one path.
Is it a tree? Maybe (either is possible; we need more information).
Reason: To determine whether this graph is a tree, we would need to check every pair of vertices, not just A and B.
The network has 7 vertices and exactly 3 bridges.
Is it a tree? No.
Reason: If a network is a tree, then it has one fewer edge than the number of vertices, and every edge will be a bridge. Thus, a tree with 7 vertices must have 6 edges which are all bridges.
The network has 7 vertices and at least 3 bridges.
Is it a tree? Maybe. We need more information.
Reason: If a network is a tree, then it has one fewer edge than the number of vertices, and every edge will be a bridge. Thus, a tree with 7 vertices must have 6 edges which are all bridges. Since this network has at least 3 bridges, it may or may not actually have exactly 6, and be a tree.
A tree minimizes the number of edges in a network, so we could say that it solves the problem of connecting a set of vertices in an optimal way. This is, however, only one type of optimization we could consider. Recall that in Chapter16 we assigned weights to the edges of a graph, and considered how to find a Hamilton circuit with minimum weight. We can ask the same question for networks. Any tree will minimize the number of edges that connect a set of vertices. But if the edges are given weights, we can then ask for a tree that minimizes the total weight of the edges as well. We turn to this question for the remainder of this section.
SubsectionSpanning Trees
A company requires reliable internet and phone connectivity between their five offices (named A, B, C, D, and E for simplicity) in New York, so they decide to lease dedicated lines from the phone company. The phone company will charge for each link made. The costs, in thousands of dollars per year, are shown in the graph.
In this case, we don't need to find a circuit, or even a specific path; all we need to do is make sure we can make a call from any office to any other. In other words, we need to be sure there is a path from any vertex to any other vertex. If we choose the fewest possible edges from the existing graph that allows it to remain connected, we will be left with a tree. Since this tree will connect all the vertices of the original graph, we can say that it spans the original graph.
Spanning Trees
A subgraph is a new graph formed using a selection of vertices and edges from a larger original graph.
A spanning tree for a graph is a subgraph which is a tree and which connects every vertex of the original graph.
So, when given a graph, we will find a spanning tree by selecting some, but not all, of the original edges. We need just enough edges so that all the vertices will be connected, but not too many edges. Since the smaller graph is a tree, it will include the smallest number of edges needed to connect all the vertices.
In general, a given graph will have many different spanning trees. We can see this in the example below.
Example17.10
Consider the graph at right. It is not a tree, because it has too many edges. We can make it a tree by removing some of the edges.
Some examples of spanning trees for this graph are shown below.
Of course, any random spanning tree isnt really what we want. We want the minimal spanning tree.
Minimal spanning tree
The minimal spanning tree (MST) is the spanning tree with the smallest total edge weight.
The problem of finding a MST is called the network connection problem. Unlike the traveling salesman problem, the network connection problem has an algorithm that is both simple and guaranteed to find the optimal solution.
Kruskal's Algorithm
Given a graph, follow these steps to find a minimal spanning tree.
Select the cheapest unused edge in the graph.
Repeat step 1, adding the cheapest unused edge, unless adding the edge would create a circuit.
Repeat until a spanning tree is formed.
Example17.11
Let's find a MST for the phone company graph introduced previously. Using Kruskal's algorithm, we add edges in the following order:
AB (cost $4): Select.
AE (cost $5): Select.
BE (cost $6): Reject. It would close the circuit ABEA.
DC (cost $7): Select.
AC (cost $8): Select.
At this point we stop: every vertex is now connected, so we have formed a spanning tree with cost $24 thousand a year.
We can perform the algorithm even if we are given a table instead of a graph. In such a situation, one useful strategy is to draw the graph one edge at a time as you select them. For large graphs, this can be easier than starting with a complete diagram of the graph. This process is demonstrated in the example below.
Example17.12
The power company needs to lay updated distribution lines connecting the ten Oregon cities below to the power grid. How can they minimize the amount of new line to lay?
Ash.
Ast.
B.
C.
C.L.
E.
N.
P.
Sal.
Sea.
Ashland

374
200
223
108
178
252
285
240
356
Astoria
374

255
166
433
199
135
95
136
17
Bend
200
255

128
277
128
180
160
131
247
Corvallis
223
166
128

430
47
52
84
40
155
Crater Lake
108
433
277
430

453
478
344
389
423
Eugene
178
199
128
47
453

91
110
64
181
Newport
252
135
180
52
478
91

114
83
117
Portland
285
95
160
84
344
110
114

47
78
Salem
240
136
131
40
389
64
83
47

118
Seaside
356
17
247
155
423
181
117
78
118

Table17.13
Using Kruskal's algorithm, we add edges from cheapest to most expensive, rejecting any that close a circuit. We stop when the graph is connected.
Seaside to Astoria
17 miles, Select
Corvallis to Salem
40 miles, Select
Portland to Salem
47 miles, Select
Corvallis to Eugene
47 miles, Select
Corvallis to Newport
52 miles, Select
Salem to Eugene
Reject: closes a circuit
Portland to Seaside
78 miles, Select
The graph up to this point is shown to the right.
Continuing,
Newport to Salem
reject
Corvallis to Portland
reject
Eugene to Newport
reject
Portland to Astoria
reject
Ashland to Crater Lk
select (108 miles)
Eugene to Portland
reject
Newport to Portland
reject
Newport to Seaside
reject
Salem to Seaside
reject
Bend to Eugene
select (128 miles)
Bend to Salem
reject
Astoria to Newport
reject
Salem to Astoria
reject
Corvallis to Seaside
reject
Portland to Bend
reject
Astoria to Corvallis
reject
Eugene to Ashland
select (178 miles)
This connects the graph. The total length of cable to lay would be 695 miles.
Exploration17.1
Find a miminal spanning tree on the graph below using Kruskal's algorithm.