Submitted by Nathália Faria da Silva (nathaliafsilva.ufv@gmail.com) on 2017-10-04T12:42:42Z No. of bitstreams: 1 texto completo.pdf: 13995495 bytes, checksum: 71c34a30f49b54385642ee42cdb41d72 (MD5) / Made available in DSpace on 2017-10-04T12:42:42Z (GMT). No. of bitstreams: 1 texto completo.pdf: 13995495 bytes, checksum: 71c34a30f49b54385642ee42cdb41d72 (MD5) Previous issue date: 2017-02-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / 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. / The Theory of Graphs is associated with situations that can be described by means of diagrams represented by a set of points (vertices) and lines that connect some pairs of these points (edges). Its beginning dates back to Leonhard Euler’s visit to the town of Königsberg in 1736, when he was presented with a challenge that intrigued the city’s residents. They wondered if it was possible to get out of the house, pass on each bridge only once, and return to the starting point. The diagram assembled by Euler represent the map of the city’s seven bridges is a graph diagram. The development and consolidation of Graph Theory provided significant contributions to Physics, Chemistry, Biology and Computer Science. The algorithms associated with minimum path, coloring, and minimum generation tree search algorithms are widely used in programming language practice. In this research, the minimum path problem and the minimum generation tree search are used to work with algorithms involving graphs with high school students in a school in Belo Horizonte. A didactic sequence with three sections was applied, being the first class on the introduction to the graph theory, the second class on algorithms and graphs and the third class with the implementation of these algorithms using the C programming language. The algorithms used were Dijkstra, Prim, Kruskal and Floyd. Results point to the possibility of including the Theory of Graphs in High School in view of the interactions with Combinatorial Analysis, Probability and Polyhedra. The study of graphs through algorithms and their application in programming language is a new approach to be considered for High School.