| |
| Acadêmico(a): Anderson de Borba |
| Título: FURB Graphs: uma aplicação para teoria dos grafos |
| |
| Introdução: |
A teoria dos grafos vem desde muito tempo sendo um instrumento para resolver problemas do dia a dia através da modelagem de problemas do cotidiano para grafos. A mais antiga menção ao assunto ocorreu no trabalho de Euler, no ano de 1736 (RABUSKE, 1992, p. 3). O trabalho de Euler consistia em resolver uma dúvida do cotidiano da época que mais tarde ficou conhecido como “problema das pontes de Königsberg” (BOAVENTURA NETTO, 1996, p. 1). O problema é baseado na cidade de Königsberg que é cortada pelo Rio Prególia, onde há duas ilhas que juntas formavam uma cidade que continha sete pontes (Figura 1). O problema consistia em saber se havia possibilidade de atravessar todas as pontes da cidade sem repetir nenhuma. Na Figura 1, as linhas verdes representam as pontes (arestas) e os círculos vermelhos representam um ponto da cidade (vértice).
Tal dúvida assombrava os moradores da época. Euler conseguiu provar através da modelagem do problema para grafos que não é possível realizar tal caminho. Caminho que ficou conhecido posteriormente como “caminho euleriano”.
Atualmente teoria dos grafos é ensinada nos cursos de graduação em Ciência da Computação, sendo um assunto bastante complexo para ser lecionado devido à sua essência algorítmica. Segundo Santos e Costa (2006), assimilar as propriedades e entender os nuances da execução dos algoritmos são as principais dificuldades enfrentadas pelos alunos.
Diante deste contexto, percebe-se a importância de se ter uma aplicação voltada para o ensino de algoritmos em grafos. Para melhor compreensão e assimilação do aluno de grafos, propõe-se neste trabalho a extensão do framework para grafos desenvolvido por Zatelli (2010), adicionando uma interface gráfica na qual o aluno poderá visualizar e verificar propriedades por si mesmo, além de executar algoritmos relacionados à teoria dos grafos, caracterizando assim, uma aplicação para aprendizagem de grafos. |
| |
|
