1.6: Combinatorics and Optimization

You likely have already been introduced to optimization problems, as calculus students around the world are familiar with the plight of farmers trying to fence the largest area of land given a certain amount of fence or people needing to cross rivers downstream from their current location who must decide where they should cross based on the speed at which they can run and swim. However, these problems are inherently continuous. In theory, you can cross the river at any point you want, even if it were irrational. (OK, so not exactly irrational, but a good decimal approximation.) In this course, we will examine a few optimization problems that are not continuous, as only integer values for the variables will make sense. It turns out that many of these problems are very hard to solve in general.

Example 1.17

In Figure 1.18, we use letters for the labels on the vertices to help distinguish visually from the integer weights on the edges.

Figure 1.18. A labeled graph with weighted edges

Suppose the vertices are cities, the edges are highways and the weights on the edges represent distance.

1. What is the shortest path from vertex \(E\) to vertex \(B\)?
2. Suppose Ariel is a salesperson whose home base is city \(A\). In what order should Ariel visit the other cities so that she goes through each of them at least once and returns home at the end—while keeping the total distance traveled to a minimum? Can Ariel accomplish such a tour visiting each city exactly once?
3. Sanjay is a highway inspection engineer and must traverse every highway each month. Sanjay's homebase is City \(E\). In what order should Sanjay traverse the highways to minimize the total distance traveled? Can Sanjay make such a tour traveling along each highway exactly once?

Example 1.19

Now suppose that the vertices are locations of branch banks in Atlanta and that the weights on an edge represents the cost, in millions of dollars, of building a high capacity data link between the branch banks at it two end points. In this model, if there is no edge between two branch banks, it means that the cost of building a data link between this particular pair is prohibitively high (here we might be tempted to say the cost is infinite, but the authors don't admit to knowing the meaning of this word).

Our challenge is to decide which data links should be constructed to form a network in which any branch bank can communicate with any other branch. We assume that data can flow in either direction on a link, should it be built, and that data can be relayed through any number of data links. So to allow full communication, we should construct a spanning tree in this network. In Figure 1.20, we show a graph \(G\) on the left and one of its many spanning trees on the right.

Figure 1.20. A weighted graph and spanning tree

The weight of the spanning tree is the sum of the weights on the edges. In our model, this represents the costs, again in millions of dollars, of building the data links associated with the edges in the spanning tree. For the spanning tree shown in Figure 1.20, this total is

\(12 + 25 + 19 + 18 + 23 + 19 = 116\).

Of all spanning trees, the bank would naturally like to find one having minimum weight.

How many spanning trees does this graph have? For a large graph, say one with \(2875\) vertices, does it make sense to find all spanning trees and simply take the one with minimum cost? In particular, for a positive integer \(n\), how many trees have vertex set \(\{1,2,3,...,n\}\)?