Eulerian Trails and Tours
Mehdi Iranpoor, Davood Mohammaditabar · IGI Global eBooks · 2012
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.