Sete pontes de Königsberg
Origem: Wikipédia, a enciclopédia livre.
As sete pontes de Königsberg é um famoso problema histórico da matemática que foi uma das principais fundações da teoria dos grafos. O problema é baseado na cidade de Königsberg (Prússia até 1945, atual Kaliningrado, Rússia) que é cortado pelo Rio Pregolia onde há duas grandes ilhas que, juntas, formam um complexo que na época continha sete (7) pontes conforme mostra a figura ao lado. Das sete pontes originais uma foi demolida e reconstruída em 1935, duas foram destruídas durante a Segunda Guerra Mundial, outras duas foram demolidas para dar lugar a uma única via expressa. Atualmente apenas 2 pontes são da época de Leonard Euler.
Discutia-se nas ruas da cidade a possibilidade de atravessar todas as pontes, sem repetir nenhuma. Havia-se tornado uma lenda popular a possibilidade da façanha quando Leonhard Euler, em 1736, provou que não existia caminho que possibilitasse tais restrições.
Euler usou um raciocínio muito simples. Transformou os caminhos em retas e suas intersecções em pontos criando possivelmente o primeiro grafo da história. Então percebeu que só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse no máximo dois pontos de onde saia um número ímpar de caminhos. A razão de tal coisa é: de cada ponto deve haver um número par de caminhos, pois será preciso um caminho para "entrar" e outro para "sair". Os dois pontos com caminhos ímpares referem-se ao início e ao final do percurso, pois estes não precisam de um para entrar e um para sair, respectivamente.
[editar] Ver também
