Resumo: Na cidade de  Königsberg em 1764, o rio Pregel cortava a cidade, que possuía duas ilhas além das terras à sua margem. Como forma de facilitar o deslocamento das pessoas entre as diferentes zonas, sete pontes foram construídas. Após certo tempo, começou-se a se questionar se seria possível passar pelas sete pontes uma única vez e retornar para o ponto de partida. Procurando solucionar o problema, Euler tratou cada região da cidade como vértices distintos e cada ponte como arestas que ligavam esses vértices. Devido à maneira como se encontravam dispostas, cada vértice funcionava como ponto de partida para um número ímpar de caminhos, de modo a tornar impossível a saída e o retorno a mesma localização passando somente uma vez por cada aresta. O problema se mostrou sem solução, porém caracterizou uma nova forma de abordar problemas: a partir de um conjunto finito de vértices conectados por arestas direcionadas ou não, também conhecido como grafos. Após essa abordagem inicial de Euler, nos séculos seguintes, a teoria dos grafos passou a ser um ramo da matemática bastante estudado, devido a suas diversas aplicações. Atualmente, existem diversos situações onde a utilização da teoria dos grafos facilita a modelagem matemática de um evento real, como, as rotas utilizadas por aviões, transmissão de dados por redes com fluxo de informações, futebol de robôs e ainda problemas clássicos, como, problema do caixeiro viajante, problema do carteiro chinês, coloração de arestas. Para a apresentação, selecionamos alguns problemas, como o problema das três casas, problema das pontes de Königsberg, coloração de mapas, problema relacionando o algoritmo de Dijkstra com futebol de robôs e um enigma, que permitiram abordar tópicos da teoria dos grafos, como, coloração de vértices e aresta, caminhos eulerianos, caminhos hamiltonianos e grafos planares. Com o objetivo de esclarecer os tópicos abordados, o grupo desenvolveu softwares utilizando a linguagem de programação C++ e a Game Engine Unity que permitirão uma visualização de uma modelagem matemática com a utilização de grafos e do Algoritmo de Dijkstra de uma situação em uma partida de futebol de robôs, onde um robô deve desviar dos obstáculos de modo mais ágil possível. Além disso, os tópicos escolhidos não necessitam de uma abordagem matemática muito profunda, permitindo uma abrangência no público alvo.

Palavras-chave: Teoria dos grafos, Caminhos Eulerianos, Caminhos Hamiltonianos, Coloração de vértices, Algoritmo de Dijkstra.

Referências:

SOUZA, Michel Guerra de. Possibilidades em grafos Hamiltonianos. Rio de Janeiro, 2014.