Análise computacional do problema das sete pontes de Königsberg

uma abordagem utilizando teoria de grafos e algoritmos de Euler

Resumo

O presente trabalho apresenta uma análise computacional do clássico problema das sete pontes de Königsberg, utilizando teoria de grafos e implementação em Python com a biblioteca NetworkX. O problema, historicamente considerado o marco inicial da teoria de grafos moderna, foi modelado como um multigrafo não-direcionado onde os vértices representam as regiões geográficas da cidade e as arestas representam as pontes. Através da aplicação dos critérios de Euler para caminhos e circuitos eulerianos, verificou-se computacionalmente a impossibilidade de percorrer todas as sete pontes exatamente uma vez, confirmando a solução histórica proposta por Leonhard Euler em 1736. O algoritmo implementado determinou que o grafo possui quatro vértices de grau ímpar (L: grau 5, T: grau 3, B: grau 3, R: grau 3), violando a condição necessária para a existência de trilhas eulerianas. Os resultados obtidos demonstram a eficácia da abordagem matemática de Euler, validando computacionalmente sua demonstração teórica e evidenciando a relevância contemporânea dos fundamentos da teoria de grafos em problemas de otimização de rotas e análise de redes.