Sete pontes de Königsberg

 É um famoso problema histórico da matemática resolvido por Leonhard Euler em 1736, cuja solução negativa 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, 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 e outras duas foram demolidas para dar lugar a uma única via expressa. Atualmente apenas duas pontes são da época de Leonhard 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 Euler, em 1736, provou que não existia caminho que possibilitasse tais restrições.

Circuito e Caminho de Euler

Um Caminho Euleriano é um caminho num grafo que visita cada aresta apenas uma vez. Com caso especial, um Circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice.

Grafos que possuem um circuito Euleriano são chamados Grafos Eulerianos. Uma das principais condições para um grafo ser Euleriano é que todos os vértices precisam ser de grau par. Esta condição é também suficiente. Euler provou que uma condição necessária para a existência de circuitos eulerianos é de que todos os vértices tenham grau par, e afirmou, sem prova de que grafos conexos com todos os vértices pares tem um circuito Euleriano. A primeira prova completa desta última afirmação foi publicada em 1873 por Carl Hierholzer.

Há, ainda, grafos com caminhos Eulerianos se houver 2 vértices de grau ímpar. Nesse caso, ao se acrescentar uma aresta ligando estes dois vértices, o novo grafo passa a ser Euleriano.

Pode-se assim enunciar um corolário do Teorema de Euler para Grafos como sendo: Um grafo G conexo possui caminho euleriano se e somente se ele tem exatamente zero ou dois vértices de grau impar.

Não confundir com caminho hamiltoniano em que o caminho deve passar uma vez em cada vértice.

Dizemos que um grafo admite um circuito de Euler, quando admite um caminho a começar e acabar no mesmo vértice, que percorra todas as arestas e não mais do que uma vez qualquer delas.

Circuito e caminho de Hamilton

Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de um grafo G, não repetindo nenhum, ou, seja, passar por todos uma e uma só vez por cada. Caso esse caminho seja possível descrever um ciclo, este é denominado ciclo hamiltoniano (ou circuito hamiltoniano) em G. E, um grafo que possua tal circuito é chamado de grafo hamiltoniano.

O problema de decidir se um dado grafo é hamiltoniano é completo em NP, o que significa que é pouco provável que exista um algoritmo polinomial para o problema. Outro objetivo provavelmente ambicioso demais: obter uma boa condição necessária e suficiente para existência de ciclo hamiltoniano.

Um problema que envolve caminhos hamiltonianos é o problema do caixeiro viajante, em que um caixeiro deseja visitar um conjunto de N cidades (vértices), passando por cada cidade exatamente uma vez e retornando à cidade de origem, fazendo o caminho de menor tamanho possível.

Um ciclo Hamiltoniano, circuito Hamiltoniano, passeio em vértices ou grafo ciclo é um ciclo que visita cada vértice exatamente uma vez (exceto o vértice que é tanto o início quanto o fim, e portanto é visitado duas vezes). Um grafo que contémum ciclo Hamiltoniano é chamado de grafo Hamiltoniano.

Noções semelhantes podem ser definidas para grafos orientados, onde cada aresta (arco) de um caminho ou ciclo só pode ser atravessada em uma única direção (i.e., os vértices são conectados com as setas e as arestas atravessadas "da cauda para a ponta").

Uma decomposição Hamiltoniana é uma decomposição de arestas de um grafo em circuitos Hamiltonianos.