As pontes de Königsberg: grafos e o passeio de Euler

As pontes de Königsberg: grafos e o passeio de Euler

Na cidade de Königsberg, hoje Kaliningrado, havia sete pontes sobre o rio Pregel, ligando duas ilhas e as margens. A pergunta dos moradores era se seria possível fazer um passeio que atravessasse cada ponte exatamente uma vez e voltasse ao ponto de partida.

O problema em forma de grafo

Leonhard Euler percebeu que o detalhe das ruas não importava. Ele trocou cada região da cidade por um ponto e cada ponte por uma linha ligando dois pontos. Nasceu assim um grafo, que é a estrutura básica da teoria.

Na aula, as regiões são os vértices A (margem norte), B (margem sul), C (ilha Kneiphof) e D (região leste). As pontes são as arestas. Há duas pontes entre A e C, duas entre B e C, e uma entre cada um dos pares A–D, B–D e C–D. Como há mais de uma aresta entre o mesmo par, o objeto é um multigrafo.

A regra dos graus

O grau de uma região é o número de pontes que chegam a ela. Cada vez que o passeio entra e sai de uma região, usa duas pontes: uma para chegar e outra para sair. Por isso, para que o passeio exista, cada região precisa ter grau par, exceto possivelmente as de início e de fim.

No mapa de Königsberg, os graus são 3 (margem norte), 3 (margem sul), 5 (Kneiphof) e 3 (região leste). Todos são ímpares, e o passeio é impossível.

Euler publicou a solução em 1736. Ele mostrou também a recíproca: se um grafo conexo tem zero ou dois vértices de grau ímpar, existe um passeio que usa cada aresta exatamente uma vez. Com zero, o passeio é fechado (um circuito de Euler); com dois, começa em um deles e termina no outro.

Como usar a aula

• Desligue pontes com as caixas de seleção. Os graus e a classificação mudam na hora.
• Clique numa região para começar um passeio. Depois, clique numa ponte ainda não usada que saia da região atual para atravessá-la.
• Se você desligar uma ponte já usada, o passeio é apagado, porque deixou de existir.

Aplicações

• Roteamento: carteiros e varredores de rua precisam percorrer todas as ruas; o problema do carteiro chinês generaliza o passeio de Euler para grafos com pesos.
• Traçados: um desenho feito sem tirar a caneta do papel, passando por cada traço uma só vez, é um passeio de Euler.
• Redes: a análise de redes de computadores e de transporte começa pelos graus dos vértices.

Curiosidade

Várias pontes da cidade foram danificadas ou destruídas na Segunda Guerra Mundial, e a cidade mudou muito depois disso (os detalhes do que foi reconstruído variam nas fontes). O problema permanece como um marco da teoria dos grafos, publicado por Euler em 1736.

Perguntas de revisão

1. O que Euler representou por pontos e linhas?

Resposta: as regiões da cidade (pontos) e as pontes (linhas).

1. Por que o passeio pedido é impossível?

Resposta: porque as regiões têm um número ímpar de pontes.