Grafos Eulerianos e Hamiltonianos: fundamentos e aplicações da teoria dos grafos

Abstract

This work aims to present the fundamentals of Graph Theory, with an emphasis on Eulerian and Hamiltonian graphs, highlighting their main properties, theorems, and practical applications. Beginning with the analysis of the Königsberg bridge problem, it introduces the origins and foundational concepts that gave rise to Graph Theory. Eulerian graphs are studied based on Euler’s Theorem and Fleury’s Algorithm, while hamiltonian graphs are studied through theorems, especially Ore’s Theorem, as well as other relevant criteria. In the final section, classical applications are discussed, such as the shortest path problem, the Chinese postman problem, and the traveling salesman problem, demonstrating the practical relevance of Graph Theory in everyday contexts. The study seeks to consolidate understanding of these concepts and encourage further exploration in the field.