Urban GeometryThe tradition of mathematical playfulness set in motion by Euler is still alive and well today...
The geometry of urban services
Although we have moved from 2007 to 2008, the celebration of the 300th anniversary of the birth of Leonard Euler (born April 15, 1707) is still in full swing.
To solve the bridge problem we can, following in Euler's footsteps, use a geometrical tool called a graph. A graph is a diagram consisting of a finite number of dots called vertices, which are joined by a finite number of line segments (which can be straight or curved) called edges. (Here we will not allow an edge to join a vertex to itself, just as a matter of convenience, but it is not difficult to modify our discussion to take into account the allowing of "loops.") Typically the dots represent a collection of objects, perhaps ATM machines, and two dots are joined by an edge if objects they represent obey some condition or property. For example, in the case of ATM machines we might join two vertices representing ATM machines by an edge if it were possible to drive under 1/2 mile to get between them. To follow in the spirit of what Euler did, we can use a dot to represent a "land mass" and join two dots by an edge if the land masses they represent have bridges between them. In the famous problem Euler attacked there were cases where two bridges connected the same land masses (banks of the river or an island), so we use two edges to connect the dots in such a case.
The question that was posed to Euler, in more modern terms, was: Is it possible to find a route which crosses each of the bridges in Königsberg once and only once? We will also require that the tour begin and end in the same place. A version of this problem can be formulated in a much more tantalizing way as a problem about urban services. Suppose we interpret the diagram in Figure 4 as a street network in an urban neighborhood, with a snow plow located at B. Is it possible for the plow to traverse each street once and only once, returning to B?
Euler's spectacular insight
Euler's insight into the Königsberg Bridge Problem was to notice that not only is it not possible to find what has come to be known as an Eulerian circuit in the graph in Figure 3, but he found an extremely simple condition that can be applied to any connected graph. A graph is connected (as mentioned above) if it is possible to get between any two vertices of the graph by moving along the edges of the graph.
There are numerous ways one can show that a graph will have an Eulerian circuit when the graph is connected and even-valent. The process can be illustrated using the even-valent (and connected) graph in Figure 6.
If a graph G has every vertex being even-valent, then G can be written as the disjoint union of (simple) circuits. In the graph above, for example, the color- coded edges that form (some of the) circuits of the graph. For example, d, e, f, g, h, d is a simple circuit (in red) while w, j, k, w is a simple circuit (in green). We can form an Eulerian circuit by piecing together these simple circuits: w, j, f, e, c, a, d, e, b, d, h, ,g, f, h, i, j, k, w. The circuits of different colors have been pieced together to form longer tours of edges at vertices that the circuits have in common. (It is worth noting that usually a graph can be written as the union of circuits whose edge sets are disjoint in more than one way. For example, in the graph above we could have used dbed and adhgfeca instead of adeca and bdhgfeb.) Typically, there are many Eulerian circuits in a connected even-valent graph, which means in applied problems one can choose an Eulerian circuit that allows one to achieve some additional special goal.
Suppose we duplicate existing edges in this graph in such a manner as to make the resulting graph even-valent. The graph with the duplicated edges will have an Eulerian circuit and we can interpret moving along a duplicated edge as retraversing an edge in the original graph. These retraversals are sometimes referred to as deadheads since no work is being done during the second traversal. Might it be necessary to retraverse some edge more than twice in achieving the minimum repetition route? A moment's thought will show that if, say, 3 repeats were necessary to make the ends of edge e even-valent when they started as odd-valent, we could leave off two repeats, getting down to 1 repeat, and still have the ends of e even-valent. In the graph below the blue edges show those that correspond to duplicated edges.
Since this graph has exactly two odd-valent vertices, those with the labels 0 and 7, we need to duplicate the edges on some path from vertex 0 to vertex 7. However, there are many such paths. Which one should be chosen? If all of the edges have the same weight, then to find a minimum cost tour we need to find a shortest path from vertex 0 to vertex 7. In this graph, the shortest path from 0 to 7 has length 3 and there are several such paths. If there were weights on the edges, we would need an algorithm for finding the shortest weight path between 0 and 7.
Chinese postman problem
Our improved model, which goes beyond the analysis of Euler and yet involves ideas concerning Eulerian circuits, is often referred to as the Chinese postman problem. The reason for this is that at the surprisingly recent date of 1962, the Chinese mathematician Meigu Guan (also often known as Mei-Ko Kwan) raised issues related to efficient urban service in a paper published in Chinese.
By trial and error it is easy to see that there are three different perfect matchings in this graph: 7 + 17; 10 + 16; 11 + 14. The minimum sum corresponds to repeating the edges on a shortest path from A to C and from B to D.
(Photo of Jack Edmonds, courtesy of Jack Edmonds and Michel Las Vergnas)
(Photo of Ellis Johnson, courtesy of Ellis Johnson and Jack Edmonds)
Beltrami, E. and L. Bodin, Network and vehicle routing for municipal waste collection, Networks 4 (1974) 65-94.
Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance
Comments: Email Webmaster