O problema do menor caminho em grafos eulerianos.

SILVA, Rute Ferreira da

Please use this identifier to cite or link to this item: http://hdl.handle.net/11612/5184

Authors:	SILVA, Rute Ferreira da
metadata.dc.contributor.advisor:	JUNIOR, José Carlos de Oliveira
Title:	O problema do menor caminho em grafos eulerianos.
Keywords:	Grafos,;Euler,;Menor caminho,;Algoritmo de Fleury,;Algoritmo de Dijkstra,;Graphs,;Euler,;Shortest Path,;Fleury’s Algorithm,;Dijkstra’s Algorithm.
Issue Date:	21-Mar-2023
Publisher:	Universidade Federal do Tocantins
Citation:	KNOWLEDGE, Mathematical. O PROBLEMA DO MENOR CAMINHO EM GRAFOS EULERIANOS. 2017. 46 f. TCC (Graduação) - Curso de Matemática, Universidade Federal do Tocantins, Araguaína, 2017.
metadata.dc.description.resumo:	Esta monografia visita a Teoria dos Grafos para apresentar os denominados grafos de Euler ou eulerianos. O estudo objetiva identificar as condições necessárias e/ou suficientes para que um grafo seja dito euleriano e mostrar como se calcula caminhos mínimos neste grafo peculiar. Para tal fim, apresenta os conceitos fundamentais da Teoria dos Grafos, expõe a teoria necessária para a identificação de um grafo euleriano e indica o algoritmo de Fleury para detecção ou construção de um ciclo de Euler em grafos eulerianos e, com o auxílio do algoritmo de Dijkstra, em semieulerianos. Quanto ao metodo, a pesquisa tem caráter exploratório, bibliográfico, à obtenção dos dados, e qualitativo, quanto a abordagem do problema. Os resultados apontam que um grafo e euleriano se todos os seus vértices são pares e semieulerianos se possui no máximo dois vértices ímpares. Se qualquer uma destas condições for verificada em um grafo, o algoritmo de Fleury pode ser implementado e o problema do menor caminho em um grafo euleriano solucionado.
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.
URI:	http://hdl.handle.net/11612/5184
Appears in Collections:	Matemática

Files in This Item:

File	Description	Size	Format
RUTE FERREIRA DA SILVA - TCC - MATEMÁTICA.pdf		1.02 MB	Adobe PDF	View/Open

Show full item record