O PROBLEMA DAS SETE PONTES DE KÖNIGSBERG

  

Conta-se que, no século XVIII, havia sete pontes cruzando o rio Pregel, que banhava a pequena cidade universitária prussiana de Königsberg, hoje Kaliningrad, Rússia. Quatro delas ligavam as margens opostas a uma pequena ilha formada nesse rio, outras duas ligavam as margens opostas a uma outra ilha, próxima à primeira, e a última ponte ligava as duas ilhas, conforme a figura. Os habitantes de Königsberg costumavam passear na sua cidade nas tardes ensolaradas de Domingo, mas nunca tinham conseguido dar um passeio especial: sair de casa, atravessar todas as pontes uma só vez e regressar a casa. No entanto a dúvida quanto à possibilidade persistia.

Euler, em 1735, conseguiu provar, com clareza, que não era possível dar o tal passeio. Para demonstrar esta impossibilidade apresentou à Academia de Ciências Russa de São Petersburgo um diagrama em que fazia a seguinte analogia: à terra, representada pelas duas margens, e às duas ilhas, associou quatro pontos; às sete pontes, associou sete linhas. O diagrama era algo parecido com o da figura:

Feita tal associação, o problema das sete pontes ficou restrito a traçar o diagrama descrito, com um movimento contínuo, sem levantar o lápis do papel e sem traçar uma linha mais de uma vez.

A, B, C e D são os pontos associados à terra, que é representada pelas duas margens e as duas ilhas.

1, 2, 3, 4, 5, 6 e 7 são linhas associadas às sete pontes

Um diagrama desse tipo é simplesmente um esquema consistindo num número finito de pontos, chamados vértices, e num determinado número de linhas.

Os vértices são as extremidades das linhas e nenhuma linha tem qualquer ponto comum com uma outra, excepto o vértice comum.

Um vértice é par ou ímpar, conforme o número de linhas que o formam seja par ou ímpar.

Um diagrama é atravessado passando-se por todas as linhas exactamente uma vez.

Euler baseou-se nas seguintes descobertas que fez:

  1. Se um diagrama contém somente vértices pares, ele pode ser atravessado começando e acabando no mesmo ponto.
  2. Se um diagrama contém, no máximo, dois vértices ímpares, ele também pode ser atravessado, mas não é possível voltar ao ponto de partida.
  3. Se o diagrama contém 2n vértices ímpares, onde n é um número inteiro qualquer, para atravessá-lo será necessário n passagens distintas por uma mesma linha.

No diagrama da figura, que representa o passeio pelas sete pontes de Königsberg, os quatro vértices são todos ímpares, pois são extremidades de um número ímpar de linhas. Assim, como 2n = 4, n = 2 e serão necessárias duas passagens do lápis por uma das linhas para atravessar o diagrama.

Pelo que não é possível efectuar o referido passeio, de modo a passar por todas as sete pontes, saindo de um ponto e retornando lá, sem cruzar mais de uma vez a mesma ponte.

Adaptado de http://www.msb.com.br/pro-ciencia/vol1num1/problema/problema.htm

 

 

OUTRAS INFORMAÇÕES RELEVANTES

 

SOBRE O PROBLEMA DAS PONTES

Outras Formulações

http://www.math.usouthal.edu/~brick/teaching/math110/konig.html

http://www.inf.ufsc.br/grafos/problema/konigsbg.htm

O mesmo problema transposto para Espanha

http://www.imsa.edu/edu/math/journal/volume4/webver/eulpath.html

Escolha o ponto de partida e veja que pontes pode atravessar

http://www.ux1.eiu.edu/~cfprc/webbing/Games/Kbp/kbp.htm

Página interessante com um quadro para desenho de grafos com contagem automática do número de vértices (pares e ímpares) e de arestas

http://www.cut-the-knot.com/do_you_know/graphs.html

 

CONCEITOS (LIÇÕES) DE TEORIA DE GRAFOS

http://www.math.lsa.umich.edu/~mathsch/summ97/graph/

http://www.utm.edu/departments/math/graph/

http://leibniz.imag.fr/GRAPH/english/definitions.html

http://www.lsi.usp.br/usp/rod/text/topology.txt