Caminhos de Euler e de Hamilton

Caminhos de Euler e de Hamilton

Os dois problemas parecem parecidos, mas são de natureza muito diferente.

Euler: todas as arestas, uma vez cada

Um caminho de Euler passa por cada aresta exatamente uma vez. Um circuito de Euler é um caminho de Euler que volta ao início. Existe uma regra simples para decidir:

• Em grafo não dirigido e conexo, existe circuito se todos os vértices têm grau par; existe caminho (não circuito) se exatamente dois vértices têm grau ímpar, e o caminho vai de um ao outro.
• Em grafo dirigido, cada vértice deve ter entrada igual à saída (circuito), ou um vértice com uma saída a mais e outro com uma entrada a mais (caminho).

O algoritmo de Hierholzer constrói o percurso: anda por arestas livres até travar, empilha e, ao desempilhar, escreve o circuito de trás para frente. Quando as condições não valem, a construção trava antes de usar todas as arestas, e a animação mostra exatamente isso.

Königsberg

O problema das pontes da cidade de Königsberg pergunta se é possível cruzar as sete pontes exatamente uma vez cada. O predefinido representa as margens e as ilhas como vértices. Há quatro vértices de grau ímpar, então não existe percurso. A história completa do problema e a prova de Euler estão na aula As pontes de Königsberg.

Hamilton: todos os vértices, uma vez cada

Um caminho de Hamilton passa por cada vértice exatamente uma vez; um circuito volta ao início. Ao contrário de Euler, não há regra de grau que decida. O problema é NP-completo: não se conhece algoritmo rápido em geral. A aula faz uma busca com retrocesso, que testa caminhos e volta quando trava. Ela tem um orçamento de passos, e se o estourar mostra uma mensagem em vez de travar a página. Para grafos pequenos, a busca termina rápido.

Repare que o grafo de Petersen tem caminho de Hamilton, mas não tem circuito de Hamilton.