Euler tour

From Algorithmist
Jump to: navigation, search

Contents

[edit] Definitions

An Euler tour (or Eulerian tour) in an undirected graph is a tour that traverses each edge of the graph exactly once. Graphs that have an Euler tour are called Eulerian.

Some authors use the term "Euler tour" only for closed Euler tours.

[edit] Necessary and sufficient conditions

An undirected graph has a closed Euler tour iff it is connected and each vertex has an even degree.

An undirected graph has an open Euler tour iff it is connected, and each vertex, except for exactly two vertices, has an even degree. The two vertices of odd degree have to be the endpoints of the tour.

A directed graph has a closed Euler tour iff it is strongly connected and the in-degree of each vertex is equal to its out-degree.

Similarly, a directed graph has an open Euler tour iff for each vertex the difference between its in-degree and out-degree is 0, except for two vertices, where one has difference +1 (the start of the tour) and the other has difference -1 (the end of the tour) and, if you add an edge from the end to the start, the graph is strongly connected.

[edit] Fleury's algorithm

Fleury's algorithm is a straightforward algorithm for finding Eulerian paths/tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian. A version of the algorithm, which finds Euler tour in undirected graphs follows.

Start with any vertex of non-zero degree. Choose any edge leaving this vertex, which is not a bridge (i.e. its removal will not disconnect the graph into two or more disjoint connected components). If there is no such edge, stop. Otherwise, append the edge to the Euler tour, remove it from the graph, and repeat the process starting with the other endpoint of this edge.

Though the algorithm is quite simple, it is not often used, because it needs to identify bridges in the graph (which is not a trivial thing to code.) Slightly more sophisticated, but easily implementable algorithm is presented below.

[edit] Cycle finding algorithm

This algorithm is based on the following observation: if C is any cycle in a Eulerian graph, then after removing the edges of C, the remaining connected components will also be Eulerian graphs.

The algorithm consists in finding a cycle in the graph, removing its edges and repeating this steps with each remaining connected component. It has a very compact code with recursion:

'tour' is a stack

find_tour(u):
	for each edge e=(u,v) in E:
		remove e from E
		find_tour(v)
	prepend u to tour

to find the tour, clear stack 'tour' and call find_tour(u),
where u is any vertex with a non-zero degree.

This algorithm can also be used to find Eulerian paths: simply connect the path's endpoints by a dummy edge, and find Euler tour.

[edit] Generalizations

In some practical situations, it is desirable to find a cycle, which visits all edges of a graph, when the graph does not have an Euler tour. In this case some of the edges will have to be visited more than once. If the graph is weighted, and a minimum-cost such cycle is sought, then this is what is known as a Chinese Postman Problem.

It's possible to generalize Euler tours to the case of mixed graphs, which contain both directed and undirected edges. See article UVa_10735 for a description of one possible algorithm for such graphs.

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox