Caminhos em um grafo e o algoritmo de Dijkstra

Abstract

Este trabalho tem por objetivo apresentar um pouco da Teoria de Grafos para, com isto, termos uma fundamentação teórica que mostrará a viabilidade da aplicação no Ensino Médio, em destaque o Algoritmo de Dijkstra, onde o educando poderá modelar situações problemas num grafo, para obtenção do caminho mais curto. Este algoritmo tem uma vasta aplicação em diversas áreas do conhecimento, em especial na área de tecnologia, como por exemplo, em redes de comunicação. Proporcionando assim, uma oportunidade única de aplicações em problemas reais, atuais e do interesse do educando. Não só estudamos a questão do caminho mais curto, mas também consideramos o problema da conexidade em grafos e a existência de caminhos disjuntos, demonstrando o famoso teorema de Menger. Por exemplo, no caso de uma rede de comunicação é interessante saber qual é o ponto vulnerável do sistema e verificar a existência de um caminho alternativo, caso um destes pontos venha a falhar, uma aplicação imediata do Teorema de Menger.

Abstract : We give a brief presentation of Graph Theory in a way that a student without any knowledge in graphs can learn the basic definitions, examples and properties and can apply these in a real life situation. In particular, we study the Dijkstra algorithm, where the student can apply this algorithm to find the shortest path between nodes in a graph. This algorithm has a lot of real life applications, especially in technology such as paths in a network communication. This gives a unique opportunity of solving current real problems. Not only we study the problem of finding the shortest path, we also consider the problem of connectedness in a graph and the existence of different paths which do not intersect, proving the famous Menger's Theorem. For instance, in the case of a network communication, it is interesting to know the problem points where the system is vulnerable and of one these points fail, one can try to verify the existence of an alternative path, an immediate application of Menger's Theorem.