O problema de Euler – Grafos

Em 1736, o matemático Leonhard Paul Euler ao visitar a cidade de Konigsberg (Kaliningrad) tomou conhecimento de um problema que estava sendo discutido, embora parecesse simples, ainda não tinha sido resolvido.

Num rio que cort a cidade havia duas ilhas que, na epoca, eram ligadas entre si por uma ponte. As duas ilhas se ligavam as margens por mais seis pontes.

O problema consistia em encontrar um percurso para um passeio que partisse de uma margem e, atravessando uma única vez cada ponte, retornasse à margem de partida.

Euler percebeu que o número de passagens de cada margem era sempre ímpar (indicando que se pode passar mas não retornar). Foi demonstrado que, para o passeio desejado fosse possível, cada magem deveria se ligar à outra por um número par de pontes.

Para Euler o desafio das pontes não passou de um simples problema sem importância, não estudou mais afundo, nem procurou desenvolvê-lo ou achar aplicações.

Fonte: Boaventura Netto, P. O. e Jurkiewicz, S., Grafos: Introdução e prática. São Paulo: Blucher, 2017, Segunda Edição.