Sete Pontes de Königsberg
As Sete Pontes de Königsberg é um problema historicamente famoso na matemática. Leonhard Euler resolveu o problema em 1735. Isto levou ao início da teoria dos gráficos. Isto então levou ao desenvolvimento da topologia.
A cidade de Königsberg na Prússia (agora Kaliningrado, Rússia) estava situada em ambos os lados do rio Pregel. Ela incluía duas grandes ilhas que estavam ligadas uma à outra e ao continente por sete pontes.
O problema era encontrar uma maneira de atravessar a cidade atravessando cada ponte uma e apenas uma vez. As ilhas não podiam ser alcançadas por nenhum outro caminho que não fossem as pontes. Cada ponte deve ter sido atravessada por completo todas as vezes. A caminhada não precisava começar e terminar no mesmo local. Euler provou que o problema não tem solução.
Mapa de Königsberg na época de Euler mostrando o layout real das sete pontes, destacando o rio Pregel e as pontes
Análise de Euler
Primeiro, Euler apontou que a escolha da rota dentro de cada massa terrestre não importa. A única propriedade importante de uma rota é a ordem na qual as pontes são atravessadas. Portanto, ele mudou o problema para termos abstratos. Isto lançou as bases da teoria dos gráficos. Ele removeu todas as características, exceto a lista das massas de terra e as pontes que as ligavam. Na linguagem da teoria gráfica, ele substituiu cada massa de terra por um "vértice" ou nó abstrato. Depois ele substituiu cada ponte por uma conexão abstrata, uma "borda". Uma borda (estrada) registrou quais dois vértices (massas de terra) estavam conectados. Desta forma, ele formou um gráfico.
→ → 
O gráfico desenhado é uma imagem abstrata do problema. Portanto, as bordas podem ser unidas de qualquer maneira. Somente se dois pontos estão conectados ou não são importantes. Mudar a imagem do gráfico não muda o gráfico em si.
Em seguida, Euler observou que (exceto nos pontos finais da caminhada), sempre que se entra num vértice por uma ponte, sai-se do vértice por uma ponte. Em qualquer caminhada do gráfico, o número de vezes que se entra em um vértice é igual ao número de vezes que se sai dele. Se cada ponte foi atravessada exatamente uma vez, segue-se que, para cada massa terrestre (exceto para as escolhidas para o início e o fim), o número de pontes que tocam essa massa terrestre deve ser uniforme. Isto porque, se houver n pontes, ela é atravessada exatamente 2n vezes. Entretanto, todas as quatro massas de terra do problema original são tocadas por um número ímpar de pontes (uma é tocada por 5 pontes, e cada uma das outras três é tocada por 3). Há no máximo duas massas que podem ser os pontos finais de uma caminhada. Portanto, a proposta de uma caminhada que atravessa cada ponte uma vez leva a uma contradição.
Em linguagem moderna, Euler mostra que a possibilidade ou não de um passeio através de um gráfico cruzando cada borda uma vez depende dos graus dos nós. O grau de um nó é o número de arestas que o tocam. Euler mostra que uma condição necessária para a caminhada é que o gráfico esteja conectado e tenha exatamente zero ou dois nós de grau ímpar. Este resultado declarado por Euler foi provado mais tarde por Carl Hierholzer. Tal caminhada é agora chamada de caminho Euler ou caminhada Euler. Se houver nós de grau ímpar, então qualquer caminho Euleriano começará em um deles e terminará no outro. Como o gráfico que representa o histórico Königsberg tem quatro nós de grau ímpar, ele não pode ter um caminho Euleriano.
O trabalho de Euler foi apresentado à Academia de São Petersburgo em 26 de agosto de 1735. Foi publicado como Solutio problematis ad geometriam situs pertinentis (A solução de um problema relativo à geometria da posição) na revista Commentarii academiae scientiarum Petropolitanae, em 1741. Está disponível em inglês no The World of Mathematics.
A importância na história da matemática
Na história da matemática, a solução de Euler do problema da ponte de Königsberg é considerada como o primeiro teorema da teoria gráfica. A Teoria dos Gráficos é um assunto agora geralmente considerado como um ramo da combinatória.
Estado atual das pontes
Duas das sete pontes originais foram destruídas durante o bombardeio de Königsberg na Segunda Guerra Mundial. Duas outras foram demolidas mais tarde. Elas foram substituídas por uma rodovia moderna. As outras três pontes permanecem, embora apenas duas delas sejam da época de Euler (uma foi reconstruída em 1935). Assim, a partir de 2000, existiam cinco pontes em Kaliningrado.
Em termos de teoria gráfica, dois dos nós agora têm grau 2, e os outros dois têm grau 3. Portanto, um caminho Euleriano é agora possível, mas como deve começar em uma ilha e terminar na outra, é impraticável para os turistas.
Páginas relacionadas
- Jogo Icosiano
- Caminho Hamiltoniano
- Água, gás e eletricidade
- Problema do caixeiro-viajante
Perguntas e Respostas
Q: O que é o problema das Sete Pontes de Königsberg?
R: O problema das Sete Pontes de Königsberg é um famoso problema matemático que envolve encontrar uma maneira de caminhar pela cidade cruzando cada uma de suas sete pontes uma vez e somente uma vez.
P: Quem resolveu o problema das Sete Pontes de Königsberg?
R: Leonhard Euler resolveu o problema das Sete Pontes de Königsberg em 1735.
P: A que levou a solução do problema das Sete Pontes de Königsberg?
R: A solução do problema das Sete Pontes de Königsberg levou ao início da teoria dos grafos, que por sua vez levou ao desenvolvimento da topologia.
P: Onde está localizada Königsberg?
R: Königsberg está localizada na Prússia, que agora faz parte de Kaliningrado, na Rússia.
P: Qual era o layout de Königsberg?
R: Königsberg foi projetada em ambos os lados do rio Pregel e incluía duas grandes ilhas que eram conectadas entre si e ao continente por sete pontes.
P: Quais eram os requisitos para resolver o problema das Sete Pontes de Königsberg?
R: O problema exigia encontrar uma maneira de atravessar a cidade cruzando cada ponte uma vez e somente uma vez, com cada ponte sendo cruzada completamente todas as vezes. As ilhas não poderiam ser alcançadas por nenhuma outra rota além das pontes, e a caminhada não precisava começar e terminar no mesmo ponto.
P: Euler provou que o problema das Sete Pontes de Königsberg tem uma solução?
R: Não, Euler provou que o problema das Sete Pontes de Königsberg não tem solução.
