Interesting Map Problems

Don Knuth is working on Volume 4 of the Art of Computer Programming. One of the chapters is on Binary Decision Diagrams and their applications, a subject that I find very interesting. Knuth shows that a variety of interesting graph problems can be encoded as Boolean formulas, and the derived BDD represents all possible solutions to the problem. Often there is some sort of optimization criterion, and it is fairly easy to extract the "best" solution from the BDD by a simple dynamic programming algorithm.

Here we show a few examples, using the graph representing the 48 contiguous states, with a node for each state, and an edge between two states if they share a border. For each of the maps, if you click on he image you will reach the source document in SVG format. Here is the graph, locating the nodes at the capitals of the states:

Capital Tours

Suppose you want to visit the 48 state capital with the requirement that you only pass through each state once. (In other words, you want to find a Hamiltonian path in the graph.) As you can see from the above map, if you follow the most direct route between state capitals, you will often pass through another state, or in the case of going from Lansing, Michigan to Madison, Wisconsin, you will drive across Lake Michigan. Instead, you should to take the shortest driving route that stays within the two states for each leg of the journey. Let us call such a route a Capital Tour. Here is a diagram of the allowable routes between the states:

Based on a simple analysis, plus Knuth's efforts, we can say the following:

All tours must start or end in Maine, since Maine has only a single neighbor. We will use Maine as the starting point.
All tours must end beyond New York, since it is an articulation point.
There are 68,656,026 different capital tours overall.

Here is the shortest capital tour, totalling 11,698 miles:

Here is the longest capital tour, totalling 18,040 miles:

Graph Coloring

Another interesting class of problems involves coloring the map. The rule is that no two adjacent states can have the same color. The famous Four Color Theorem states that any planar graph can be colored with at most four colors.

There are many colorings of the graph for the 48 contiguous state. Here are some interesting examples:

A balanced coloring, in which each color is used for exactly 12 states:
An unbalanced coloring, in which one of the colors (green) is used as little as possible (2 states).
An unbalanced coloring, in which one of the colors (yellow) is used as much as possible (18 states).
Combining both. It is possible to have one color (green) used for the minimum possible (two states), while another color (yellow) is used for the maximum possible (18 states).

Randal E. Bryant

Last modified: Mon Nov 16 11:15:16 EST 2009