Eulerian path

An Euler circuit or (closed ) Eulerzug (also Euler tour or Euler line) is in graph theory, a cycle that contains all the edges of a graph exactly once. An open Eulerzug ( Euler path or Eulerweg ) is given when the identity of start and end nodes is not required, that is, instead of a cycle only requires a sequence of edges that contains every edge of the graph exactly once. A connected graph that has an Euler circuit, also referred to as Eulerian graphs. Contains a graph only one Eulerweg and no Euler circuit, so it is called a semi- Eulerian graph.

The task of determining for a given graph, if this is Euler tour or not, are called Euler circuit problem. It dates back to 1736 by Leonhard Euler solved Königsberg bridge problem. The problem also exists for directed graphs and graphs with multiple edges.

Contrary to its name of the Euler circle is not a circle, at least if one follows the common definition, according to which no node is allowed to repeat in a circle.

• 6.1 The Königsberg bridge problem
• 6.2 The house of Nicholas

Characterization

According to the Euler- Hierholzer one can easily characterize Euler graph.

The following statements are equivalent in this case:

Are analogue for directed graphs the following statements are equivalent:

Generalization: Eulerweg

A ( undirected related ) graph contains a Eulerweg then if two or none of its nodes of odd degree are; has no odd degree nodes, it is in the Eulerweg an Euler circuit.

Decision problem

The question of whether there is an Euler circuit for a given graph, can be algorithmically solved relatively easily, since a graph is Euler tour if it is connected and each node has even degree. Using depth-first search can be this easy to find in linear time.

Finding an Euler circuit

To find a Euler circle are several methods. The algorithm of Fleury dates from 1883 and follows a very simple approach, which is why he has a duration of the order. More efficient is the algorithm of Hierholzer that calculates a Euler circuit in linear time. It is based on that an Euler graph can be decomposed into pairwise edge-disjoint circuits.

Algorithm of Hierholzer

Algorithm of Fleury

In the algorithm of Fleury bridge edges play an important role. These are edges, without which the graph would fall into two connected components.

The algorithm adds an initially empty sequence of edges added all edges of a graph so that an Euler circuit is formed.

Whether an edge is a bridge edge, can be checked by means of depth-first search in run time. As per step, an edge is removed, we need iterations. The number of tested edges per iteration corresponds to the degree of the current node. Overall, one can restrict the total number of verified through edges. The total running time is thus of the order.

History

Leonard Euler asked in his work in 1736 to Königsberg bridge problem if the given by the bridges of the city graph is an Euler graph, that is, whether a Eulerweg exists and replied in the negative, since the graph was odd corners. Euler proved that a Euler graph can only have straight corners. He also suspected (or gave no proof of this) that this is a sufficient condition: a connected graph in which each vertex is even, is an Euler graph. A proof of the theorem was first published by Carl Hierholzer 1873. In it, he also stated the algorithm of Hierholzer to find the Euler path.

Application Examples

The Königsberg bridge problem

The Königsberg bridge problem can be expressed in the following graph:

The circles (nodes) are the respective districts or viewpoints. The lines (edges) are the bridges. By trial and error you will find that it is not possible to find a tour of the city in which each bridge is used exactly once. So there is no Eulerweg and consequently no Euler circuit. Why is this so?

Euler discovered the following rule: If there is a Eulerweg in a graph G, then a maximum of two nodes have odd degree (ie, have no more than two knots an odd number of connected edges). When Königsberg bridge graph, there are four nodes with odd degree (the numbers next to the nodes give here the degree to which ). Therefore, the tour of the city with the only one-time use of each bridge is impossible.

An odd node is either the beginning or end of the path across the bridges: null odd node would mean that the beginning and end of the path are identical in Königsberg. A path with a beginning and end would have a maximum of two odd nodes. Ergo, it has not been possible in Königsberg, only to commit all the bridges in a way once each.

The house of Nicholas

The popular children's puzzle "This is the house of Nicholas " on the other hand contains a Eulerweg but no Euler circuit because its graph contains two nodes of degree 3.

A Eulerweg For example 1-2-4-3-1-4-5-3-2. Nodes 1 and 2 each have three neighbors, its degree is odd. In order to draw the house in a train, so you have to start at one of these two points.

A square with diagonals contains no Eulerweg, since all of its nodes have degree 3. Pictured are just the points 1,2,3,4 with the connecting edges.