Problema das Sete Pontes de Königsberg
Contexto
O problema das Sete Pontes de Königsberg surgiu a partir de um quebra-cabeça popular na cidade de Königsberg, na Prússia (hoje Kaliningrado).
A cidade era cortada pelo rio Pregel, formando duas grandes ilhas e duas margens, todas conectadas por um total de sete pontes.
Problema
A questão era se um cidadão poderia planejar um passeio que começasse em qualquer uma das regiões, cruzasse cada uma das sete pontes exatamente uma vez e retornasse ao ponto de partida.
Apesar de muitas tentativas, ninguém conseguiu encontrar tal percurso, mas também não conseguiam provar que era impossível.
Solução
A solução foi apresentada pelo matemático Leonhard Euler em 1736 e sua abordagem foi o que fundou a Teoria dos Grafos.
Euler teve a sacada genial de que os detalhes geográficos do mapa (como o tamanho das ilhas ou o comprimento das pontes) eram irrelevantes. O que realmente importava era a relação de conectividade.
Ele simplificou o problema, representando as quatro regiões de terra como pontos (vértices) e as sete pontes como linhas (arestas) que conectavam esses pontos.
Essa abstração transformou um problema do mundo real em um modelo matemático simples, um grafo.
Conclusão
Analisando esse grafo, Euler provou que o percurso era impossível. Ele descobriu que, para entrar e sair de uma região de terra por pontes diferentes, essa região precisaria ter um número par de pontes conectadas a ela. Como todas as quatro regiões de Königsberg tinham um número ímpar de pontes, era impossível realizar o trajeto desejado.
Essa prova é considerada o primeiro teorema da Teoria dos Grafos, estabelecendo um campo da matemática focado no estudo de redes e conexões, que hoje é fundamental para áreas como ciência da computação, logística e redes sociais.