Na Folha: Lições das pontes de Königsberg servem à internet
Cidade de Kalingrado, antiga Königsberg | Foto: Valdis Pilskalns – Wikimedia Commons
Reprodução da coluna de Marcelo Viana na Folha de S. Paulo
No início do século 18, a cidade prussiana de Königsberg dividia-se em quatro regiões separadas por braços do rio Pregel: as duas margens, a ilha de Kneiphof, e o bairro de Lomse. Ligando-as, havia sete pontes: Kneiphof tinha duas pontes para cada margem, Lomse tinha uma para cada margem, e a sétima ponte ligava Kneiphof a Lomse.
Não sabemos como nem quando surgiu a pergunta: é possível fazer um passeio pelas quatro regiões cruzando cada ponte apenas uma vez? O grande Leonhard Euler resolveu o problema, em 1735, do seguinte modo:
De cada vez que o passeio passa por uma das regiões, são cruzadas duas pontes: uma para entrar, outra para sair. Então, tirando as regiões de partida e de chegada, todas as demais precisam ser servidas por um número par de pontes. Mas em Königsberg todas as regiões tinham um número ímpar de pontes: 5 em Kneiphof e 3 em cada uma das outras. Logo, não podia existir o passeio solicitado.
Leia mais: Lista preliminar de classificados para 2ª fase da OBMEP publicada
Projeto de IA do Centro Pi é destaque na FAPERJ
‘Gosto de equações e problemas complexos’, diz Henrique
Um aspecto crucial do raciocínio de Euler é a abstração: os detalhes são irrelevantes, tudo o que importa são as regiões, que podemos representar como pontos, e as pontes, que podemos representar como linhas ligando esses pontos. Tais configurações, formadas por um certo número de pontos ligados, aos pares, por linhas, são chamados “grafos”.
