Caminho hamiltoniano

O caminho vermelho é hamiltoniano.

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: mostrar que o problema está em co-NP, ou seja, 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.

Em 2009 conseguiu-se uma resolução para este problema utilizando-se de bactérias na implementação do algoritmo, que historicamente costuma ter um custo de tempo de computação exponencial.

Definições

Um caminho Hamiltoniano (em preto) sobre um grafo (em azul).

Um caminho Hamiltoniano ou caminho rastreável é um caminho que visita cada vértice exatamente uma vez. Um grafo que contém um caminho Hamiltoniano é chamado um grafo rastreável. Um grafo é Hamilton-conectado se para cada par de vértices existe um caminho Hamiltoniano entre os dois vértices.

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ém um 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.

Exemplos

Um ciclo Hamiltoniano em um dodecaedro. Como todos os sólidos platônicos, o dodecaedro é Hamiltoniano.

• Um grafo completo com mais de dois vértices é Hamiltoniano
• Todo grafo ciclo é Hamiltoniano
• Todo torneio tem um número ímpar de caminhos Hamiltonianos
• Todo sólido platônico, considerado como um grafo é Hamiltoniano

Propriedades

Um caminho hamiltoniano no grafo de Mycielski.

Qualquer ciclo hamiltoniano pode ser convertido para um caminho Hamiltoniano, removendo-se uma de suas arestas, mas um caminho Hamiltoniano só pode ser estendido para um ciclo hamiltoniano se suas extremidades são adjacentes.

O grafo linha de um grafo Hamiltoniano é Hamiltoniano. O grafo linha de um grafo Euleriano é Hamiltoniano.

Um torneio (com mais de 2 vértices) é Hamiltoniano se e somente se ele é fortemente conectado.

Um ciclo Hamiltoniano pode ser usado como base de uma prova com zero conhecimentos.

Número de diferentes ciclos hamiltonianos para um grafo completo = (n-1)! / 2.

Número de diferentes ciclos hamiltonianos para um grafo orientado completo = (n-1)!.

Ver também

• Problema de Roteamento de Veículos
• Problema do caixeiro viajante
• Caminho euleriano

Ligações externas

• «Solução do problema utilizando bactérias»