Contemporary Mathematics: Contemporary Mathematics at Nebraska

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.

By way of comparison, here are some 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 Chapter 16 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.

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.

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.

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.