Skip to main content
\(\require{cancel}\newcommand\degree[0]{^{\circ}} \newcommand\Ccancel[2][black]{\renewcommand\CancelColor{\color{#1}}\cancel{#2}} \newcommand{\alert}[1]{\boldsymbol{\color{magenta}{#1}}} \newcommand{\blert}[1]{\boldsymbol{\color{blue}{#1}}} \newcommand{\bluetext}[1]{\color{blue}{#1}} \delimitershortfall-1sp \newcommand\abs[1]{\left|#1\right|} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

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 \(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
Figure17.2
Figure17.3
Figure17.4
By way of comparison, here are some graphs that are not trees:
Example17.5Examples of graphs that are not trees
Figure17.6
Figure17.7
Figure17.8

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.

  1. Select the cheapest unused edge in the graph.
  2. Repeat step 1, adding the cheapest unused edge, unless adding the edge would create a circuit.
  3. 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.

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.