As 7 pontes de Königsberg

     Sou estudante de Ciência da Computação, e estou pagando a disciplina de Teoria dos Grafos, matéria esta muito interessante que surgiu na cidade de Konigsberg,  atual Kaliningrado. A cidade é cortada pelo rio Prególia onde há duas grandes ilhas que juntas formam um grande complexo com 7 pontes na época.

     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 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 (arestas) e suas intersecções em Pontos (vértices), 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 exatamente zero ou dois pontos de onde saísse um número ímpar de caminhos.

     

Posted in: Ciência da Computação