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.
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 \(N-1\) 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
By way of comparison, here are some graphs that are not trees:
Example17.5Examples of graphs that are not trees
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.
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.
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.
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.
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.
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.
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.
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?
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.
Newport to Salem
Corvallis to Portland
Eugene to Newport
Portland to Astoria
Ashland to Crater Lk
select (108 miles)
Eugene to Portland
Newport to Portland
Newport to Seaside
Salem to Seaside
Bend to Eugene
select (128 miles)
Bend to Salem
Astoria to Newport
Salem to Astoria
Corvallis to Seaside
Portland to Bend
Astoria to Corvallis
Eugene to Ashland
select (178 miles)
This connects the graph. The total length of cable to lay would be 695 miles.
Find a miminal spanning tree on the graph below using Kruskal's algorithm.