Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Mehdi Iranpoor (Amirkabir University of Technology, Iran) and Davood Mohammaditabar (Islamic Azad University, South Tehran Branch, Iran)

Source Title: Graph Theory for Operations Research and Management: Applications in Industrial Engineering

Copyright: © 2013
|Pages: 15
DOI: 10.4018/978-1-4666-2661-4.ch007

Chapter Preview

TopProbably 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.

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.

TopSince 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).

Search this Book:

Reset