Euler's Eyes
2026-10-10
As pontes de Königsberg e o nascimento dos grafos
A cidade de Königsberg (hoje Kaliningrado, na Rússia) era cortada pelo rio Pregel, que formava duas ilhas. Sete pontes ligavam as quatro regiões da cidade. Os moradores se perguntavam se era possível dar um passeio atravessando cada ponte exatamente uma vez.
Antes de ler a resposta, tente você mesmo:
Euler percebeu que o formato das ruas, o tamanho das ilhas e o comprimento das pontes não importavam. Só importava quais regiões estão ligadas a quais. Ele trocou o mapa por um desenho com pontos (as regiões) e linhas (as pontes). Hoje isso se chama grafo:
Hoje desenhamos o mesmo problema assim:
Agora a dedução. Num passeio, toda vez que você passa por uma região (sem começar nem terminar nela), usa uma ponte para entrar e outra para sair. Então as pontes de uma região intermediária vêm sempre em pares: o número de pontes que chegam nela tem de ser par. Só a região de partida e a de chegada podem ter um número ímpar de pontes.
Conclusão: o passeio só é possível se no máximo duas regiões tiverem um número ímpar de pontes.
Contando em Königsberg:
| Região | Pontes | Par ou ímpar? |
|---|---|---|
| Ilha Kneiphof | 5 (a, b, c, d, e) | ímpar |
| Margem norte | 3 (a, b, f) | ímpar |
| Margem sul | 3 (c, d, g) | ímpar |
| Ilha Lomse | 3 (e, f, g) | ímpar |
São quatro regiões ímpares, então o passeio é impossível. Euler apresentou o argumento em 1735, e ele é considerado o primeiro resultado da teoria dos grafos, área que hoje está por trás de GPS, redes sociais e rotas de entrega.
Todos os tópicos de Leonhard Euler · ← A mola e as equações diferenciais · $V - A + F = 2$ e a bola de futebol →