Teoria dos grafos no ensino básico e secundário

Abstract

Nesta dissertação apresentam-se algumas noções gerais sobre Teoria dos Grafos e apresentam-se alguns problemas desta teoria, abordados em atividades nos diferentes níveis de ensino básico e secundário, bem como algoritmos para a sua resolução. Os problemas abordados são: o problema do caminho mais curto, o problema da árvore abrangente de custo mínimo, determinação de um circuito de Euler ou de um ciclo hamiltoniano, nos quais se enquadram os problemas do carteiro chinês e do caixeiro viajante, e as colorações de grafos. Por último, apresentam-se algumas aplicações da Teoria dos Grafos em tarefas apresentadas aos alunos do ensino básico e secundário e é feita uma análise sobre a importância da sua inclusão no programa da disciplina de Matemática nos diferentes ciclos de ensino.

In this dissertation we present some general notions of graph theory and some well known problems of this theory as well as algorithms to solve them. The problems considered here are: the shortest path problem, the minimum spanning tree, the determination of eulerian circuits and hamiltonian cycles, in particular, the problems of the Chinese postman and the travelling salesman, and the colorations of graphs. By last, some applications of graph theory such as problems given to students of different stages of education are presented and the importance of including theory of graphs in the program of mathematics in the different stages of education is highlighted.