Ande como um Euleriano: as pontes de Königsberg
Como um enigma envolvendo um rio, duas ilhas e sete pontes levou um matemático a lançar as bases para a teoria dos grafos
Leonhard Euler (1707-1783) foi um dos matemáticos mais importantes do mundo e certamente é um candidato ao mais prolífico: somente em 1775, ele escreveu uma média de um artigo matemático por semana. Durante sua vida, ele publicou mais de 500 livros e artigos. Suas obras coletadas preencheriam até 80 volumes in-quarto.
Euler fez contribuições importantes para campos tão diversos como ótica, teoria dos gráficos, dinâmica de fluidos e astronomia. A lista de funções, teoremas, equações e números com o nome de Euler é tão longa que alguma piada que eles realmente deveriam ter o nome da primeira pessoa após Euler para descobri-los (1).
Um conto apócrifo mostra Euler, um cristão devoto, silenciando o livre-pensador filósofo francês Diderot com uma fórmula matemática que prova a existência de Deus (2). Mas talvez a contribuição mais lembrada de Euler para a ciência seja sua solução para o chamado Problema das Sete Pontes de Königsberg. Talvez porque envolva um mapa facilmente compreensível, em vez de fórmulas algébricas confusas.
A cidade prussiana de Königsberg (3) se estendia pelas duas margens do rio Pregel, que banha o Kneiphof, uma pequena ilha no centro da cidade e uma ilha maior imediatamente a leste. Sete pontes conectavam os bancos e as ilhas entre si. Um passatempo popular entre os cidadãos de Königsberg era tentar uma solução para um problema aparentemente intratável: como atravessar as duas margens e as ilhas cruzando cada uma das sete pontes apenas uma vez. Os nomes das pontes, de oeste a leste e de norte a sul, são:
Hohe Brücke ao sul do Fähre (balsa), fora deste mapa. Para o mapa completo de Königsberg em 1905, consulte aqui .
Em 1735, Euler reformulou o enigma em termos abstratos - e de uma vez por todas provou que o problema da ponte de Königsberg era de fato insolúvel. Euler reformulou a localização real como um conjunto de nós (vértices) conectados por elos (arestas). O layout exato do terreno não importava, contanto que os nós permanecessem ligados da maneira original. Ele então resolveu o problema analiticamente, em vez de listar exaustivamente todas as permutações possíveis:
“Todo o meu método depende da maneira particularmente conveniente como a travessia de uma ponte pode ser representada. Para isso, uso as letras maiúsculas A, B C, D, para cada uma das áreas de terra separadas pelo rio. Se um viajante vai de A para B pela ponte a ou b, escrevo como AB, onde a primeira letra se refere à área de saída do viajante e a segunda se refere à área a que ele chega após cruzar a ponte. Assim, se o viajante sai de B e cruza para D pela ponte f, este cruzamento é representado por BD, e os dois cruzamentos AB e BD combinados denotarei pelas três letras ABD, onde a letra B do meio se refere a ambas as áreas que é inserido no primeiro cruzamento e para aquele que é deixado no segundo cruzamento. ”
Mapa do artigo de Euler sobre o problema. Observe que os nomes das pontes não correspondem aos do mapa acima.
Euler provou que o problema das pontes só poderia ser resolvido se todo o grafo tivesse zero ou dois nós com conexões ímpares e se o caminho (4) iniciasse em uma dessas conexões ímpares e terminasse em outra. Königsberg tem quatro nós de grau ímpar e, portanto, não pode ter um Caminho Euleriano.
A solução analítica de Euler para o problema de Königsberg é vista como o primeiro teorema da teoria dos grafos, um estágio importante no desenvolvimento da topografia e um texto fundador da ciência de redes.
Infelizmente, a topografia original para esse problema praticamente desapareceu. Aqueles que tentam uma peregrinação matemática às Sete Pontes de Kaliningrado ficarão profundamente desapontados. Duas pontes foram destruídas por bombardeios no final da Segunda Guerra Mundial, outras duas foram demolidas e substituídas por uma rodovia soviética. Dos outros três originais, um outro foi reconstruído em 1935. Portanto, dos cinco restantes, apenas dois datam da época de Euler.
A configuração soviética mais recente torna possível cruzar todas as pontes apenas uma vez? Droga, devíamos ter prestado mais atenção na aula de matemática. Para um tratamento mais extenso do artigo de Euler, incluindo a conclusão de que deve ser capaz de resolver o enigma mais recente, consulte esse documento no Mathematical Association of America .
Google Maps mostrando o Knaypkhof hoje, incluindo o túmulo de Immanuel Kant.
Salvo indicação em contrário, as imagens para esta postagem foram tiradas de Complexidade visual: mapeamento de padrões de informação , de Manuel Lima. O livro discute e demonstra a visualização de redes, em grande parte um campo moderno, novamente com Euler como um de seus primeiros pioneiros.
Mapas Estranhos # 536
Tem um mapa estranho? Me avisa em estranhosmaps@gmail.com .
(1) Uma lista impressionantemente longa aqui . Não incluídos estão os chamados quadrados mágicos , Quebra-cabeças de grade de 81 quadrados que alguns consideram ser as primeiras versões do sudoku.
(dois) Para a pequena história : (a + b ^ n) / n = x - embora Euler provasse principalmente que Diderot não sabia o suficiente sobre álgebra para responder na mesma moeda.
(3) Atualmente a cidade russa de Kaliningrado, situada entre a Polônia e a Lituânia.
(4) Essas rotas são chamadas de Caminhadas de Euler ou Caminhos de Euler em homenagem ao matemático.
Compartilhar: