## Urban GeometryThe tradition of mathematical playfulness set in motion by Euler is still alive and well today...Joseph Malkevitch
## The geometry of urban servicesAlthough 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.
Figure 1
Figure 2
## A graph theory primerTo solve the bridge problem we can, following in Euler's footsteps, use a geometrical tool called a Figure 3
Figure 4 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? Figure 5
Proof: If there were an odd number of vertices of odd valence, then summing the valences of the vertices of the graph would give an odd number which contradicts the theorem. You can verify that the graph in Figure 3 has four odd-valent vertices while the graph in Figure 5 has six odd-valent vertices. ## Euler's spectacular insightEuler'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 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. 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, Figure 7 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
Figure 8
Figure 9
Figure 10 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 problemOur improved model, which goes beyond the analysis of Euler and yet involves ideas concerning Eulerian circuits, is often referred to as the Figure 11
Figure 12 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)
## References: Beltrami, E. and L. Bodin, Network and vehicle routing for municipal waste collection, Networks 4 (1974) 65-94. Joseph Malkevitch 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 |