A cidade de Königsberg, atual Kaliningrado (Rússia, desde 1946), era cortada pelo rio Prególia, que envolvia duas ilhas e ligava quatro regiões distintas por meio de sete pontes. Essa configuração urbana despertava a curiosidade dos moradores:
Seria possível realizar um percurso que atravessasse cada uma das sete pontes apenas uma vez, sem repeti-las?
Figura 1 – As
sete pontes de Königsberg
Fonte: Foto do Acervo do LEM – UNESPAR/Campo Mourão
Esse problema,
aparentemente simples, chamou a atenção do matemático e físico suíço Leonhard
Euler, que, em 1736 demonstrou que tal travessia era impossível. Sua
investigação deu origem ao que hoje conhecemos como a Teoria dos Grafos.
Euler propôs representar o problema da seguinte forma
- Cada ilha ou margem do rio foi representada como um vértice (ponto).
- Cada ponte foi representada como uma aresta (linha ou curva) conectando dois vértices.
Figura
2 – Grafo
O
desafio passou a ser: percorrer todas as sete arestas exatamente uma vez, iniciando
e finalizando em vértices do grafo, ou seja, desenhar o grafo inteiro sem levantar
o lápis do papel e sem repetir caminhos.
- Ao analisar os vértices, Euler observou uma propriedade fundamental: Sempre que se passa por um vértice intermediário, é necessário que ele esteja ligado a um número par de arestas, uma para entrar e outra para sair.
- Apenas os vértices de início e de fim do percurso podem ter um número ímpar de arestas, já que um deles será o ponto de partida (sem entrada) e o outro, o ponto final (sem saída).
No
entanto, o grafo que representa as sete pontes de Königsberg, nenhum vértice
possuía grau par (grau igual ao número de arestas ligadas ao vértice). Todos os
quatro vértices tinham grau ímpar o que torna impossível a realização do
percurso desejado.
O raciocínio de Euler não apenas desmentiu a lenda urbana de que seria possível atravessar todas as pontes sem repeti-las, mas também fundou a Teoria dos Grafos, um campo matemático com aplicações em diversas áreas, como:
- Rotas de transporte;
- Redes de comunicação;
- Organização de dados e
algoritmos computacionais.
Essa
lógica é aplicada ainda hoje em jogos matemáticos, que desafiam os
participantes a resolver problemas de percurso e de otimização de caminhos.
Referência
ARAÚJO, Adérito. As pontes de Königsberg. Departamento de Matemática da Universidade de Coimbra. Disponível em: https://periodicos.unesc.net/ojs/index.php/sulcomp/article/view/2072/1963. Acesso em: 30 jul. 2024.
Nenhum comentário:
Postar um comentário