Printable PDF: 1.1 Euler Circuits

Chapter 1 : Urban Services:

Operational research: the underlying theme of management science) is finding the best method for solving some problems—what mathematicians call the optimal solution.

In some cases, the goal/objective may be to:
- finish a job as quickly as possible
- maximize profit or minimize cost

Our Goal: save time in traversing a street network while checking parking meters, delivering mail, removing snow, or collecting bottles for recycling.

First Task: Assisting the parking department of a city government. Show how management science techniques can help to make parking control more efficient.
Intro: Most cities and many small towns have parking meters that must be regularly checked for parking violations or emptied of coins

1.1 Euler Circuits

Job as the commissioner of parking is to find the most efficient for the parking-control office, who travels on foot, to check the meters in an area.
Efficient routes save money. For our example we will use a small area. But if we use larger areas, there are almost unlimited possibilities for parking-control routes.
The commissioner has two goals in mind:
(1) The parking-control officer must cover all the sidewalks that have parking meters without retracing any more steps than are necessary
(2) The route should end at the same point at which it began, perhaps where the officers’ patrol car is parked

To be specific, suppose there are only two blocks that have parking meters (the two top blocks). Suppose further that the parking-control officer must start and end at the upper left corner of the left-hand block.

Describing a Graph

Graph: A mathematical structure in which points (called vertices) are used to represent things of interest and in which links (called edges) are used to connect vertices, denoting that the connected vertices have certain relationships.
i.e. a finite set of dots and connecting links

Vertex: A point in a graph where one or more edges meet.
I.e. the dots of a graph (a multiple dots are called a vertices)

Edges: A link joining two vertices in a graph.
- each edge must connect two different vertices
o Example:

Path: a connected sequence of edges showing a route on the graph that starts at a vertex and ends at a vertex
- A path is usually described by naming in turn the vertices visited in traversing it

Circuit: a path that starts and ends at the same vertex

- A graph can represent our city map, a communications network, or even a system of air routes.

Parts of a Graph

The graph has 5 vertices and 7 edges. The vertices represent cities, and the edges represent nonstop airline routes between them.
- We see that there is a nonstop flight between Berlin and Rome, but no such flight between New York and Berlin.
- There are several paths that describe how a person might travel with this airline from New York to Berlin. The path that seems most direct is New York, London, Berlin, but New York, Miami, and Rome, Berlin is also a path. We can describe these two paths as NLB and NMRB. Another path would be New York, Miami, Rome, London, and Berlin, which can be written as NMRLB.
- An example of a circuit is Miami, Rome, London, and Miami.
o It is a circuit because the path starts and ends at the same vertex. The circuit can be described in symbols by MRLM.
- Another example of a circuit in this graph would be LBRL, which is the circuit involving the cities London, Rome, Berlin, and bad to London.
- EVERYDAY EXAMPLE:
o The circuit of our day: we start and end at home

Fig. 1.3
Returning to the case of the parking control, we can use a graph to represent the whole territory to be patrolled: Think of each street intersection as a vertex and each sidewalk that contains a meter as an edge.

Fig. 1.4 (a) Fig. 1.4 (b)
The numbered sequence of edges in figure 1.4 A shows one circuit that covers all the meters (note that it is a circuit because its path returns to its starting point). However, one edge is traversed three times.

Figure B shows another solution that is better because its circuit covers every edge (sidewalk) exactly once. In figure B no edge is covered more than once, or deadheaded (a term borrowed from shipping, which means making a return trip without a load).

Euler (oy’ lur) Circuit: A circuit that covers each edge of a graph once but not more than once.

Euler circuits get their name from the great eighteenth-century mathematician Leonhard Euler, who first studied them. Euler was the founder of the theory of graphs, or graph theory. Once of his first discoveries was that some graphs have no Euler circuits at all.

Fig. 1.5 (a) Fig. 1.5 (b)
It would be impossible to start at one point and cover all the edges without retracing some steps: If we try to start a circuit at the leftmost vertex, we discover that once we have left the vertex, we have “used up” the only edge meeting it. We have no way or returning to our starting point except to reuse that edge. But this is not allowed in an Euler circuit. If we try to start a circuit at one of the other two vertices, we likewise can’t complete it to form and Euler circuit.

Goals: Interested in finding circuits, Euler circuits are the most efficient ones
If there is no Euler circuit, need to develop the next best circuit, those having minimum deadheading

1.2 Finding Euler Circuits

Two Obvious Questions
1. Is there a way to tell by calculation, not by trial and error, if a graph as an Euler circuit?
2. Is there a method, other than trial and error, for finding an Euler circuit when one exists

Euler investigated these questions in 1735 by using concepts of valence and correctedness.

Valence: the valence of a vertex in a graph is the number of edges meeting at the vertex.

Fig. 1.6
Vertices A and D have valence 3, vertex B having valence 2, and vertex C having valence 0. Isolated vertices such as vertex C are an annoyance in Euler circuit theory. Because they don’t occur in typical applications, we henceforth assume that our graphs have no vertices of valence 0.

Fig. 1.3 (b)
Figure 1.3 (b) has four vertices of valence 2, namely, A, C, F, and D. This graph also has two vertices, B and E, and a valence 4. Notice that each vertex has a valence that is an even number. We will soon see that this is very significant.

Connected Graph: A graph is said to be connected if for every pair of its vertices there is at least one path connecting two vertices.

Fig. 1.7
Given a graph, if we can find even one pair of vertices not connected by a path, then we say that the graph is not connected. For example, the graph in Figure 1.7 is not connected because we are unable to join A to D with a pair of edges. However, the graph does consist of two “pieces” or connected components, one containing the vertices A, B, F, and G, the other containing C, D, and E. A connected graph will contain a single connected component. Notice that the parking-control graph of Figure 1.3 (b) is connected

We can now state Euler’s theorem, his simple answer to the problem of detecting when a graph G has an Euler circuit:

1. If G is connected and has all valences even, then G has an Euler circuit.
2. Conversely, if G has an Euler circuit, then G must be connected and all its valences must be even numbers

Because the parking-control graph of Figure 1.3 (b) conforms to the connectedness and even-valence conditions, Euler’s theorem tells us that it has an Euler circuit. We already have found and Euler circuit for Figure 1.4 (b) by trial and error. For a very large graph, however, trial and error may take a long time. It is usually quicker to check whether the graph is connected and even-valent than to find out if it has an Euler circuit.

Once we know that this is an Euler circuit in a certain graph, how do we fid it?

Fig. 1.8

Fig. 1.9

Fig. 1.10

Finding an Euler circuit without trial and error
- Never use an edge that is the only link between two parts of the graph that still need to be covered.

Fig. 1.9 (b)
Here we have started the circuit at A and gotten to D via B and C, and we want to know what to do next. Going to B would be a bad idea because the uncovered part of the graph would then be disconnected into left and right portions. You will never be able to get from the left part back to the right part because you have just used the last remaining link between these parts. Therefore, you should stay to the right side and finish that before using the edge from D to E. This kind of thinking needs to be applied every time you need to chose a new edge.

How it works:
Starting at the beginning A. From vertex A there are two possible edges, and neither of them disconnects the unused portion of the graph. Thus, we could have gone either to the left or down. Having gone down to B, we now have three choices, none of which disconnects the unused part of the graph. After choosing B to C, we find that any of the three choices at C is acceptable. Can you complete the Euler circuit? There are many ways to do this.

The method just described leaves many edge choices up to you. When there are many acceptable edges for your next step, you can pick one at random. You might even flip a coin. When computers carry out algorithms of this sort, they use random-number generators, which mimic the flipping of a coin.

Proving Euler’s Theorem
We’ll start by proving that if a graph has an Euler circuit, then it must have only even-valent vertices and it must be connected. Let X be any vertex of the graph. We will show that the edges at X can be paired up, and this will prove that the valence is even. Every edge at X is used by the Euler circuit as an outgoing edge (leaving from X) or an incoming edge (arriving at X). If the Euler circuit starts at X, then pair up the first edge used by the circuit with the last one (when the circuit returns to X for the last time). In addition, each other edge at X that is used by the circuit as an incoming edge will be paired with the outgoing edge that is used next. Because all edges at X are used by the Euler circuit, none more than once, this pairs up the edges.
But what if X is not the start of the Euler circuit? Then do the pairing like this: The first incoming edge at X is paired with the outgoing one used next, the second incoming edge at X is paired with the outgoing one used next, and so on.

Fig. 1.11
For example, in Figure 1.11 at vertex B, we would pair up edges 2 and 3 and edges 9 and 10. At vertex C, we would pair up edges 4 and 5 and edges 8 and 9.
- How would the pairs work at D?
- How about vertex A?

In studying this particular example, you might think it would be simpler to count the edges at a vertex to see that the valence is even. True, but our pairing method works for a graph about which we know nothing except that it has an Euler circuit.

To see that a graph with a Euler circuit is connected, note that by following the Euler circuit around we can get from edge to any other edge (it covers them all) using a portion of Euler circuit. Because ever vertex is on an edge (there are no vertices of 0 valence), we can get form any vertex to any other using a portion of Euler circuit.

So far, this is not a complete proof of Euler’s theorem. We also need to prove that if a graph has all vertices even-valent and is connected, ten an Euler circuit can be found for it.