Grafos e problemas de caminhos

• Ano de defesa: 2017
• Autor(a) principal: Nogueira Júnior, Dárcio Costa
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Viçosa
• Palavras-chave em Português: Teoria dos grafos; Matemática - Ensino Médio; Algortmos - Processamento de dados; Ciências exatas e da Terra; Matemática
• Link de acesso: http://www.locus.ufv.br/handle/123456789/11869

A Teoria dos Grafos está associada a situações que podem ser descritas por meio de diagramas representados por um conjunto de pontos (vértices) e linhas que ligam alguns pares destes pontos (arestas). Seu inı́cio remonta a visita de Leonhard Euler à cidade de Königsberg, em 1736, quando foi apresentado a ele um desafio que intrigava os moradores da cidade. Eles se perguntavam se era possı́vel sair de casa, passar em cada ponte, apenas uma vez, e retornar ao ponto inicial. O diagrama montado por Euler para representar o mapa das sete pontes da cidade é um esquema de grafo. O desenvolvimento e a consolidação da Teoria dos Grafos proporcionou significativas contribuições para a Fı́sica, Quı́mica, Biologia e Ciência da Computação. Os algoritmos associados a problemas de caminho mı́nimo, coloração e busca de árvore geradora mı́nima são amplamente utilizados na prática de linguagem de programação. Nessa pesquisa, o problema de caminho mı́nimo e a busca da árvore geradora mı́nima são usados para o trabalho de algoritmos envolvendo grafos com alunos do Ensino Médio em uma escola de Belo Horizonte. Uma sequência didática com três aulas foi aplicada, sendo a primeira aula sobre a introdução à teoria dos grafos, a segunda aula sobre algoritmos e grafos e a terceira aula com a implementação desses algoritmos usando a linguagem de programação C. Os algoritmos utilizados foram Dijkstra, Prim, Kruskal e Floyd. Resultados apontam para a possibilidade de inclusão da Teoria dos Grafos no Ensino Médio tendo em vista as interações com Análise Combinatória, Probabilidade e Poliedros. O estudo de grafos por meio de algoritmos e sua aplicação em linguagem de programação é uma nova abordagem a ser considerada para o Ensino Médio.