Caminhos mínimos em grafos: uma proposta para além da sala de aula

Abstract

O presente trabalho apresenta conceitos e resultados básicos acerca da Teoria dos Grafos e tem por objetivo fornecer a fundamentação teórica necessária para que o tema possa ser explorado e discutido com alunos do Ensino Médio. A partir da apresentação de um problema aparentemente simples e de fácil entendimento, O Problema de Caminho Mínimo em um Grafo, estuda-se dois algoritmos: o Algoritmo de Dijkstra e o Algoritmo de Floyd-Warshall. Com relação a esse último, é discutido um Problema de Alocação. Ao final do trabalho é apresentada uma proposta de oficina para alunos do Ensino Médio que tem por objetivo desenvolver os algoritmos citados ao longo do Trabalho, aplicando-os na resolução de um problema previamente sugerido. A intenção é que os alunos, a partir de uma situação concreta, construam um modelo matemático aplicando a Teoria de Grafos, utilizem um algoritmo, compreendam passo a passo o seu funcionamento, para assim obterem uma solução desejada.

This study presents concepts and basic results on the Graph Theory. Its main objective is to provide the necessary theoretical basis so that the theme can be explored and discussed with High School students. Starting from the presentation of an apparently simple and easily understandable problem, the Shortest Path in a Graph problem, we study two algorithms: the Dijkstra Algorithm and the Floyd-Warshall Algorithm. Concerning the latter, it is discussed the Allocation Problem. By the end of the study, it is presented a proposition of a workshop for High School students, which aims to develop the algorithms cited throughout the study, applying them to the solution of a previoulsy suggested problem. The intention is that the students, starting from a concrete situation, construct a mathematical model applying the Graph Theory, use an algorithm, understand each step of its operation, in order to obtain the desired solution.