How to eulerize a graph

1

Graph Theory Ch. # 9

9.1 A Walk Through Konigsberg

Objectives

 Comprehend Euler’s solution to the Konigsberg bridge problem

 Understand the basic terms and concepts of graph theory

 See that graph theory has many, varied applications.

This field of mathematics can be applied for many issues, ranging from operational

research and chemistry to genetics and linguistics, and from electrical engineering and

geography to sociology and architecture.

A graph is a diagram that consists of points, called vertices (vertex) and connecting lines, called

edges.

An edge that connects a vertex with itself is called a loop.

The resident of Königsberg tried to find a route that allowed them to cross each of the seven

bridges just once.

The problem was solved by Swiss Mathematician Leonard Euler.

2

In the graph of Königsberg:

Every point has odd number of lines. This means that each point could be used as starting

point or as stopping there.

So that is no way to walk across each of Konigsberg’s seven bridges once.

Degree of a vertex

Degree of a vertex is the number of connection to that vertex.

Walk: Is a movement from vertex to vertex.

Circuit: Walk and return to the starting point. (Closed walk)

Euler walk

No need to return to the starting point, but have to cover every edge exactly once.

Euler’s circuit:

A circuit in which we use every vertex once

Euler walks and need to return to the starting point.

All vertices have even degree.

Seven bridges, start at any point and go through all bridges one and back to the same

starting point.

Euler reasoned like this:

Euler drew a simple picture to replace the map. In that picture, a line represents a bridge

and a point represents land.

Each line connects two points because each bridge connects two pieces of land.

Euler’s thoughts about using up bridges turned into thoughts about using line.

 A walker uses up a bridge when he crosses the first bridge on his walk.

 A walker uses up a bridge when he walks across piece of land: one in approaching the land and one in leaving the land.

 A walker uses up a bridge when he crosses the bridge on his walk. This means that if the walker were to start and stop the walk at different places, the starting

point must have an odd number of lines coming out of it: one line to start the walk and two

lines (or four or six,…)to revisit the point when crossing other bridges.

And the ending point must have an odd number of lines coming out of it for the same reason.

3

But all other points must have an even number of lines so that the walker can both approach

the point and depart the point.

If the walker were to start and stop the walk at the same point, then that point must have an

even number of lines:

one line to start the walk, an even number to revisit the point when crossing other bridges,

and one line to return to the starting point.

This means that all points must have an even number of lines.

In the graph of Königsberg, every point has an odd number of lines.

This means that each point could be used as a starting point or as a stopping point.

But none of the points could be visited without starting or stopping there.

So there is no way to walk across each of Königsberg’s seven bridges once.

4

9.2 Graphs and Euler Trials

Objectives

 Be able to utilize Euler’s Theorems

 Apply Fleury’s algorithm

 Understand Eulerization.

Two vertices are adjacent if they are joined by an edge.

Two edges are adjacent if they have a vertex in common.

Identical graphs if they describes the same schedule;

a. Edges that are adjacent in 1 st . are adjacent in the 2

nd .

b. Vertices that that are adjacent in 1 st . are adjacent in the 2

nd .

The two graphs has a different appearance. However, it describes the same schedule of games.

Edges that are adjacent in 1st. Figure are adjacent in 2nd .Figure, and vertices that are adjacent

in in 1st Figure are adjacent in 2nd Figure.

A trial is a sequence of adjacent vertices and distinct edges that connect them.

A circuit is a trial that begins and ends at the same vertex.

The degree of a vertex is the number of edges that connect to that vertex.

A loop connects to a vertex twice, so a loop

contributes to degree twice.

An odd vertex is a vertex with an odd degree.

An even vertex is a vertex with an even degree.

An Euler trail is a trial that is a circuit.

An Euler circuit is Euler trail that is a circuit.

A graph is connected if every pair of vertices is connected by a trail.

5

Euler’s Theorem

 A connected graph with only even vertices has at least one Euler trail, which also an Euler circuit.

 A connected graph with exactly two odd vertices and any number of even vertices has at least one Euler trail. Each of these trails will start at one odd vertex and end at the other

odd vertex.

 A graph with more than two odd vertices has no Euler trails and no Euler circuits.

 It is impossible for a connected graph to have only one odd vertex.

Euler’s Theorem refers to connected graphs.

A graph is connected if every pair of vertices is connected by a trail.

Disconnected graphs never have Euler trails and never have Euler circuits.

Ex:

A security guard to walk through the subdivision once every night.

The vertices are corners (intersections) and edges are streets.

This is a connected graph with only even vertices, so it has at least one Euler trail, which

is also an Euler circuit.

It is possible for the guard to walk a rout that allows him to walk through every block just

once and return to his car.

An Algorithm is a logical step-by-step procedure for solving a problem.

6

Fleury’s Algorithm for Finding Euler trails and Euler Circuits

1. Verify that the graph has an Euler trail or Euler circuit, using Euler’s Theorem.

2. Choose a starting point. a. If the graph has two odd vertices, we can find an Euler trail. Pick either of the odd

vertices as the starting point.

b. If the graph has no odd vertices, we can find an Euler circuit. Pick any point as the starting point.

3. Label each edge alphabetically as you travel that edge.

4. When choosing edges: a. Never choose an edge that would make the yet-to-be-traveled part of the graph

disconnected, because you won’t be able to get from one portion of the graph to the

other.

b. Never choose an edge that has already been followed, since you can’t trace any edges twice in Euler trails and Euler circuits.

c. Never choose an edge that leads to a vertex that has no other yet-to-be-traveled edges, because you won’t be able to leave that vertex.

Eulerization Algorithm

To efficiently Eulerize a graph that is laid out like a grid:

1. Choose a vertex along the outer perimeter of the graph.

2. If a vertex is an even vertex, add no edges and move on to the next vertex along the outer perimeter.

3. If a vertex is an odd vertex, add a duplicate edge that connects it to the next adjacent vertex along the outer perimeter, and move on to the next vertex along the outer perimeter.

4. Repeat these steps until you return to the vertex in step 1.

Ex:

7

a. Apply the Eulerization algorithm to the Secluded Glen community.

b. Use the result of part (a) to find an efficient route through the community for the postal carrier. All mailboxes are on one side of the street.

Solution:

Applying the Eulerization algorithm.

Step 1:

Choose a vertex along the outer perimeter of the graph. We’ll choose the vertex in

the upper left corner.

Step 2:

If a vertex is an even vertex, add no edges and move on to the next vertex along the

outer perimeter.

The vertex in the upper left corner is indeed an even vertex, so we add no edges and

move to the right to the next vertex.

Step 3:

If a vertex is an odd vertex, add a duplicate edge that connects it to the next adjacent

Vertex along the outer perimeter.

The second vertex is an odd vertex, so we add a

duplicate edge that connects it to the next vertex.

Step 4:

Repeat these steps until you return to the vertex in step 1.

This results in the graph shown

This scheme has five added edges. Wherever the postal carrier starts and stops, this

scheme would require her to walk five blocks a second time.

This is the most efficient scheme.

a. Using the result to find an efficient route through the community for the postal carrier.

8

We’ll do this with Fleury’s algorithm. The result is shown in Figure

In Figure 9.33, we show a map of the Secluded Glen community without the added edges

but with street names.

The beginning of the route described in Figure 9.32 with the letters a, b, c, and so on

Translates like this:

o Start at the corner of A Avenue and 1st Street.

o Go along A until you come to 4th, and turn onto 4th.

o Go along 4th until you come to C, and turn onto C.

o From C, turn onto 3rd.

o From 3rd, turn right onto B.

o From B, turn right onto 4th and then onto C. revisit two blocks.

o From C, turn onto 1st and then onto B.

o Turn left onto 3rd.

o Turn left onto A, and revisit one block.

o Turn onto 2nd, and then right onto C, revisiting one block.

o Turn onto 1st, revisit one block, and continue to the starting point.