Teoria dos grafos na resolução de problemas do 2º Ciclo do Ensino Básico

Abstract

Nesta dissertação apresenta-se uma introdução ao estudo da Teoria dos Grafos com algumas noções gerais e alguns problemas resolvidos à luz desta teoria, bem como os algoritmos utilizados para a sua resolução. São apresentados alguns problemas, como o do caminho mais curto, da árvore abrangente de custo mínimo, determinação de um circuito euleriano ou de um ciclo hamiltoniano, nos quais se enquadram alguns problemas clássicos como o problema do carteiro chinês, do caixeiro-viajante e da coloração de grafos. Segue-se a aplicação na resolução de problemas em sala de aula a alunos do segundo Ciclo do Ensino Básico. Por fim é referida a importância da inclusão da Teoria dos Grafos no programa da disciplina de Matemática em ciclos iniciais do ensino básico.

This dissertation presents an introduction to the study of Graph Theory with some general concepts and some problems solved with this theory, as well as the algorithms for its resolution. Some problems, such as, the shortest path problem, the minimum spanning tree problem, the determination of an Euler circuit or a Hamiltonian cycle are presented, which include some classic problems like Chinese postman problem, the traveling salesman problem and graph coloring problem. Then, its application is carried out in the resolution of problems in the classroom to students of the second cycle of elementary school. Finally, the importance of Graph Theory inclusion in the mathematics program in cycles of primary education is mentioned.