9 As Sete Pontes de Königsberg

Por muito tempo os moradores da cidade de Königsberg (atualmente Kaliningrado, na Rússia) perguntavam-se se era possível fazer um passeio na cidade cruzando todas as sete pontes que cortavam o rio Pregel, passando apenas uma vez por cada ponte, retornando ao ponto de partida, ou seja, percorrendo um caminho fechado.

Figura 1 – Mapa de Königsberg de 1652

Fonte: adaptada de WIKIPEDIA

Muitos tentaram fazer um percurso, mas as tentativas foram sempre falhas. Até que o matemático suíço Leonhard Euler (1707-1783), usando argumentos muito simples, provou em 1736 que não era possível realizar tal feito. Ele usou um diagrama, chamado de grafo , para reproduzir os principais elementos do mapa, onde desenhou pontos (vértices) representando as porções de terra e linhas (arestas) representando os percursos pelas sete pontes, conforme a Figura 2.

Figura 2 – Grafo construído por Euler

Fonte: elaborada pelo autor

Daí Euler percebeu que só seria possível fazer o trajeto passando uma única vez em cada ponte e retornando ao ponto de partida, se houvesse, partindo de cada vértice, um número par de arestas, isto é, todos os vértices deveriam ser de grau par. Assim, esse famoso problema matemático tornou-se ponto de partida para o desenvolvimento da Teoria dos Grafos.

Da mesma forma, outras situações reais podem ser representadas por grafos como, por exemplo: esquemas de circuitos integrados; rotas otimizadas para empresas de transporte; sistemas de engenharia de tráfego; distribuição de serviços de energia, água, e telefone. Além disso, também é possível modelar relações de hierarquia, amizade e trabalho.

Figura 3 – Mapa do transporte metropolitano de São Paulo

Fonte: Metrô-SP

Sabendo disso, visite Kaliningrado e resolva variações do problema das sete pontes seguindo as instruções das etapas de 1, 2 e 3.

Etapa 1 – Construindo grafos: usando a ideia de Euler (ver Figuras 1 e 2), construa um grafo considerando apenas cinco das sete pontes, desconsiderando as que foram destruídas durante a segunda guerra mundial, pontes 2 e 6; com essa configuração, verifique se é possível realizar um percurso e retornar ao ponto de partida passando pelas cinco pontes sem repetir nenhuma; agora, verifique se é possível realizar um percurso partindo de um vértice qualquer, passando pelas cinco pontes sem repetir nenhuma e sem retornar ao ponto inicial; caso seja possível, em alguma das hipóteses acima, liste os percursos.

Etapa 2 – As oito pontes de Kaliningrado: faça um grafo que represente a atual configuração de pontes na cidade, considerando as oito pontes que ligam as duas ilhas e o continente (pontes 1, 3, 4, 5, 7, 8, 9 e 10); com essa configuração, verifique se é possível realizar um percurso e retornar ao ponto de partida passando pelas oito pontes sem repetir nenhuma; agora, verifique se é possível realizar um percurso partindo de um vértice qualquer, passando pelas oito pontes sem repetir nenhuma e sem retornar ao ponto inicial; e caso seja possível, em alguma das hipóteses acima, cite um percurso.

Etapa 3 – Otimizando percurso: use as coordenadas geográficas para localizar o Centro de Exposições (54 42'21.18"N, 20°30'55.68"E), o Centro Cultural (54 42'17.73"N, 20 30'25.16"E), a Catedral de St. Nicholas (54 42'22.42"N, 20 30'42.32"E) e o Museu de História e Arte de Kaliningrado (54 42'48.52"N, 20 31'6.64"E); use quantas pontes quiser, sem repetir nenhuma, e trace com a ferramenta caminho o menor percurso partindo Centro de Exposições, passando pelo Centro Cultural, a Catedral de St. Nicholas e o Museu de História e Arte, e retornando ao Centro de Exposições, não necessariamente nesta ordem.

Faça as anotações necessárias para resoluções das etapas da atividade na folha do aluno.

Arquivos para download: guia, folha do aluno, mapa e solução.
Propostas de atividades interdisciplinares: Immanuel Kant e Crítica da Pura Razão (KANT).