When L. Euler used a representation of vertices and edges to explain a legend about the existence of a route that someone could cross each bridge of Konigsberg city exactly once and go back to the origin, he actually developed the graph theory. This new theory was found useful in explaining many problems. Then, theorems about the existence of such Euler tours that cross each edge of a graph exactly once were introduced. These theorems show that there should be some conditions for a graph to posses such a tour which in simple graphs is to be connected and even. Also, other definitions and applications of Euler tours in cases where the tour is not closed or the graph is directed were developed. Euler tours have many real world applications, and therefore, some polynomial time algorithms are developed to find such tours in graphs.
TopIntroduction
Probably the first published paper on graph theory dates back to 1736 when L. Euler used a representation of vertices and edges to explain the legend of Konigsberg's bridges (Gould, 1988). People of Konigsberg (presently called Kaliningrad which is situated in western Russia) believed there is no route across each of the seven bridges between the two islands and the river banks which one could cross each bridge exactly once and go back to its start position (see Figure 1). In graph theory, in honor of L. Euler, these kinds of routes are named after the word Euler or Eulerian.
Figure 1. The seven bridges of Konigsberg
The vertices of Konigsberg graph are the regions A through D and the edges are the seven bridges. Euler in 1736 generalized the legend and proved that the existence of such a route is dependent on the number of odd vertices. In this chapter some theorems will be introduced that shows a simple connected even graph possesses Euler tours and such graphs will be named Eulerian.
The existence of Eulerian tours and trails, is as much important as finding such tours and trails in graphs. Many real world applications of Euler tours and trails need to find such tours and trails for their problem. Therefore we need to provide polynomial time algorithms to be able to find Euler tours and trails in graphs.
Fortunately, finding Eulerian tours is solvable in polynomial time. Up to now, several algorithms have been developed for finding Eulerian tours in Eulerian graphs including Splitting Algorithm, Fleury’s Algorithm, Hierholzer’s Algorithm, and Tucker’s Algorithm (Fleischner, 1991).
In the next section, we review some of the most well known variations and applications of Eulerian tours and trails in the literature. In other sections we present exact definitions for the concept and introduce proper theorems about the existence of Euler tours and trails in graphs. Next, some example applications are presented in more detail. Then the well known algorithms in finding Eulerian tours and trails in graphs are studied. In the last part of the chapter, some famous problems which are related to Euler tours (trails) are discussed in detail.
TopBackground
Since the original work of L. Euler (Euler, 1736), several variations of Eulerian tour has been developed. Among them are Eulerian tours (trails) in directed (Vasudev, 2006) and mixed graphs (Martinez, 2003). Some other variations of Eulerian tours (trails) are as follows.
- •
Properly edge-colored Eulerian tour (trail): An Eulerian tour (trail) in a colored graph with distinct color of consecutive traversed edges (Lyra, 2009).
- •
Straight-ahead Eulerian tour (trail): At every vertex, during traversal, the opposite edge (i.e. the edge which has the same number of edges on its both sides) is selected (Pisanski, Tucker, & Zitnik, 2004).
- •
Stochastic Eulerian tour (trail): The requirement for traversal of each edge is probabilistic and hence; some of the edges should be skipped in a predefined manner. The objective is determination of a fixed Eulerian tour which has the minimum expected length (Mohan, Gendreau, & Rousseau, 2008, 2010).
- •
Dual-Eulerian tour: These tours are defined in plane graphs. If a plane graph contains an Eulerian tour in the manner that the order of edges also defines an Eulerian tour for the dual of the graph, it is called a dual-Eulerian graph and the tour is called dual-Eulerian (Freeman, 2003).
- •
Minimum (Maximum) Eulerian tour in directed graph of de Bruijn: The arcs are labeled and the objective is finding the Eulerian tour with lexicographically minimum (maximum) label (Matamala & Moreno, 2009).