Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/11612/5184| Autor(a): | SILVA, Rute Ferreira da |
| Orientador: | JUNIOR, José Carlos de Oliveira |
| Título: | O problema do menor caminho em grafos eulerianos. |
| Palavras-chave: | Grafos,;Euler,;Menor caminho,;Algoritmo de Fleury,;Algoritmo de Dijkstra,;Graphs,;Euler,;Shortest Path,;Fleury’s Algorithm,;Dijkstra’s Algorithm. |
| Data do documento: | 21-Mar-2023 |
| Editor: | Universidade Federal do Tocantins |
| Citação: | 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. |
| 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 |
| Aparece nas coleções: | Matemática |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| RUTE FERREIRA DA SILVA - TCC - MATEMÁTICA.pdf | 1.02 MB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.