Detalhes - Dissertação do PROFMAT

Aluno: DÁRCIO COSTA NOGUEIRA JÚNIOR

UFV - Universidade Federal de Viçosa - Florestal - MG

Dissertação

Título
Grafos e problemas de caminhos
Resumo
NOGUEIRA JUNIOR, Dárcio Costa, M.Sc., Universidade Federal de Vi ?cosa, fevereiro de 2017. Grafos e problemas de caminhos. Orientador: Luís Felipe Gonçalves Fonseca. Coorientador: Luis Alberto D’Afonseca. 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 a cidade de Konigsberg, 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çõao á 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.
[Download TCC]

---