Início / Matemática / As pontes de Königsberg e os grafos
Matemática · 1 min de leitura
As pontes de Königsberg e os grafos
O problema que Euler resolveu em 1736 e que deu origem à teoria dos grafos.
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.
A regra dos graus
Cada vez que o passeio entra e sai de uma região, usa duas pontes. Por isso, para que o passeio exista, cada região precisa ter um número par de pontes, exceto possivelmente os pontos de início e fim. No mapa de Königsberg, as quatro regiões tinham um número ímpar de pontes. Logo, o passeio é impossível.
Euler publicou a solução em 1736, e ela é considerada o início da teoria dos grafos. O mesmo raciocínio serve hoje para roteamento, circuitos e redes.