Getting Around Graphs Sheet E
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk
Many problems in operations research (the area of mathematics concerned with helping governments and business operate more efficiently) are phrased in terms of moving around the edges of a graph. The terminology of walks, trails, paths, circuits, Eulerian circuits, Eulerian paths, Hamiltonian circuits, and Hamiltonian paths were developed to deal with such problems. The applications involve such issues as garbage collection, pot hole inspection, parking meter inspection or coin collection, mail delivery, trash or medical waste pickup, school bus and camp pickups, meals on wheels programs, etc.
The term Eulerian honors Leonhard Euler (Swiss born but spent most of his career in what is modern Germany and Russia) and William Rowan Hamilton, an Irish mathematician best known for his work on quarternions.
"Eulerian" questions deal with visiting edges efficiently while "Hamiltonian" questions deal with visiting vertices efficiently. The problems sound very similar but are worlds apart in practice, as has been shown by mathematical investigation. There is a very simple test to check if a connected graph has an Eulerian circuit (Is the graph even-valent?) It is harder but not computationally hard to find an Eulerian circuit in an even-valent connected graph. However, there is NO easy test for seeing if a "random" connected graph has a Hamiltonian circuit. And even if we knew that some 2,000,000 vertex graph has a Hamiltonian circuit, there is no "fast" algorithm for finding the Hamiltonian circuit which we know exists! (The question of finding a Hamiltonian circuit even for a 3-valent plane graph is NP-complete.)
For each of the graphs below you can assume that all of its edges have equal "cost:" If a connected graph G does not have an Eulerian circuit, it has some odd-valent vertices. One can seek a closed tour of the graph which visits each edge of the graph at least once and minimizes the number of repeated edges (Chinese postman problem). This is typically thought of as duplicating existing edges to obtain a new graph (with multiple edges) which has only even-valent vertices. This process is known as "eulerizing" the graph. The reason why we allow duplicating only existing edges is that adding new edges that don't join vertices already joined will typically require the garbage collection truck to traverse a road that does not exist! Retraversing existing edges means "wasted" or "non-productive" work but it is "feasible" because the road (or sidewalk) is there already. The number of edges that can be added to a graph to make all of its vertices even-valent is always vodd/2 where vodd is the number of odd-valent vertices in the graph. However, the number of edges needed to eulerize a graph is often much larger than vodd/2. Again, the reason why we want to duplicate existing edges when we eulerize a graph is that in applied situations we can only move along existing edges, ones that were used to create our mathematical model of the real world.
Consider the graph in Figure 1.
We can make this graph even-valent by adding the edge 04 (same as 40) to the graph. However, to eulerize this graph we need to "duplicate" edges 01, 12, 23, 36, 67, 75, and 54. Thus, this is a graph in which it is hard to inspect for potholes efficiently. We must repeat every edge in order to carry out the inspection for pot holes if each edge is to be visited at least once, our route starts and ends at the same place, and minimizes the number of repeated edges. Such a route for this graph starting at vertex 2 would be: 210123675457632. The route is inefficient but it is the best we can do. For some graphs one can "kill two birds with one stone" and get away with duplicating only vodd/2 when the graph is eulerized.
a. Find an Eulerian circuit or explain why there is none.
b. Find an Eulerian path or explain why there is none.
A Hamiltonian circuit (HC) of a connected graph G is a (simple) circuit which visits each vertex of the graph once and only once. (For convenience assume the graph has at least three vertices.)
c. Find a Hamiltonian circuit.
d. Find a Hamiltonian path.
e. List the cut vertices of the graph.
f. Solve the Chinese postman problem for each of the graphs below.
g. Give examples of real world problems which involve the concept of Eulerian circuit, Eulerian path, Hamiltonian circuit, Hamiltonian path which extend the list of such problems given above.
