Contemporary MathematicsContemporary Mathematics at Nebraska

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.

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.

Example18.1Examples of trees

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

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.

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.

Example18.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 isn't really what we want. We want the minimal spanning tree.

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.

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

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

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.

Exploration18.1

Find a minimal spanning tree on the graph below using Kruskal's algorithm.

Solution

The edges are selected in the following order:

• AB: Add, cost 11
• BG: Add, cost 13
• AE: Add, cost 14
• AG: Skip, would create circuit ABGA
• EF: Add, cost 16
• EC: Add, cost 17

This completes the spanning tree.