Caminho 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[1] na implementação do algoritmo, que historicamente costuma ter um custo de tempo de computação exponencial.
Definições
editar
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
editar
- 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
editar
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)!.
Referências
- ↑ Computador feito com bactérias resolve problemas matemáticos Terra Tecnologia, acessado em 31 de julho de 2009
