O problema do menor caminho em grafos eulerianos.

Abstract

This monograph visits the Theory of Graphs to present the so-called Euler or Eulerian graphs. The study aims to identify the necessary and / or sufficient conditions for a graph to be said to be Eulerian and to show how to calculate minimum paths in this peculiar graph. To this end, it presents the fundamental concepts of the Theory of Graphs, exposes the necessary theory for the identification of an Eulerian graph and indicates the Fleury algorithm for the detection or construction of an Euler cycle in Eulerian graphs and, with the aid of the algorithm of Dijkstra, in semieulerianos. As for the method, the research has an exploratory, bibliographic, data acquisition, and qualitative approach to the problem. The results indicate that a graph is Eulerian if all its vertices are pairs and semieulerians if it has at most two odd vertices. If any of these conditions are verified in a graph, the Fleury algorithm can be implemented and the problem of the smallest path in an Eulerian graph solved.