resumo heuristica

Sete pontes de Königsberg é um problema histórico, resolvido por Leonhard Euler em 1736, cuja solução originou a teoria dos grafos.
O problema é baseado na cidade de Königsberg (território da Prússia até 1945, atual Kaliningrado), que é cortada pelo Rio Prególia, onde há duas grandes ilhas que, juntas, formam um complexo que na época continha sete pontes.
Discutia-se os moradores da cidade a possibilidade de atravessar todas as pontes sem repetir nenhuma, tornado uma lenda popular a possibilidade da façanha quando Euler provou que não existia caminho que possibilitasse tais restrições.
Euler transformou os caminhos em retas arestas; arcos e suas intersecções em pontos vértices, criando possivelmente o primeiro grafo da história.
Um grafo admite um Passeio de Euler, se existe neste grafo um caminho, do qual fazem parte todas as arestas do grafo, Isto significa que um ponto móvel pode passear pelas arestas do gráfico, percorrendo todas elas, passando somente uma vez por de cada uma. 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. A razão de tal coisa é que 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. Se não houver pontos com número ímpar de caminhos, pode e deve, iniciar e terminar o trajeto no mesmo ponto, podendo esse ser qualquer ponto do grafo. Isso não é possível quando temos dois pontos com números ímpares de caminhos, sendo obrigatoriamente um o início e outro o fim.