Pontes de Königsberg

A antiga cidade de Königsberg, Prússia, que hoje é Kaliningrado, Rússia, possui uma geografia interessante: o rio Prególia, que atravessa a cidade, bifurca e forma duas ilhas, Kneiphof (centro da imagem abaixo) e Lomse.

Havia sete pontes interligando as ilhas e as cidades; quatro que ligavam Kneiphof ao resto da cidade, duas conectando Lomse e uma entre as duas ilhas. Este formato peculiar gerou uma pergunta, que eventualmente se tornou muito famosa: “Qual caminho passa por todas as pontes, mas apenas uma vez em cada?” Será que você consegue respondê-la?

Tente desenhar o caminho na simulação abaixo. Comece escolhendo a região de partida e, em seguida, selecione a ponte pela qual passará seu caminho.

Caso não tenha conseguido, não se sinta triste! Quem escreveu este texto também não conseguiu. Sabemos a resposta graças ao ilustre matemático Leonhard Euler, que resolveu o problema em 1736.

O primeiro passo é “isolar” o problema: Euler percebeu que não importava o tamanho de cada ilha, da cidade, ou sequer das pontes, apenas por qual delas seu caminho está atravessando; sabendo disso, podemos reconstruir o problema de forma abstrata – mas que deixe mais claro o problema – montando o que chamamos de grafo.

Já que a dimensão não importa, podemos pensar em cada localidade como um ponto: K é o vértice representando a ilha de Kneiphof, L para Lomse, e N e S representam respectivamente a parte “norte” e “sul” da cidade (veja a marcação na Fig. 2). Além disso, as linhas que os vértices representam as pontes que conectam os lugares representados.

Feito isso, apenas um pensamento simples do matemático foi capaz de resolver o problema: para passar apenas uma vez por cada aresta, cada vértice “no meio do caminho” deve estar conectado a um número par de arestas, pois para cada aresta “de entrada”, devemos ter uma “de saída”. Agora, os vértice inicial e final do caminho devem ter um número ímpar, já que o vértice que partimos não precisa ter uma entrada, e da mesma forma, o final não precisa de uma saída. A conclusão de Euler para Königsberg é que não existe o caminho desejado, porque todos os vértices possuem um número ímpar de arestas!

É importante notar que a abstração é uma ferramenta poderosa: Euler não só resolveu o problema das pontes de Königsberg, como também nos deu uma maneira de resolver qualquer problema semelhante de existência de caminhos, desde que possam ser representados em algum grafo!