Diferenças entre edições de "Caminho hamiltoniano"

1 410 bytes adicionados ,  11h49min de 13 de novembro de 2010
sem resumo de edição
m (Bot: Adicionando: lt:Hamiltono maršrutas)
Em [[2009]] conseguiu-se uma resolução para este problema utilizando-se de [[bactéria]]s<ref>[http://tecnologia.terra.com.br/interna/0,,OI3896704-EI4801,00-Computador+feito+com+bacterias+resolve+problemas+matematicos.html Computador feito com bactérias resolve problemas matemáticos] Terra Tecnologia, acessado em 31 de julho de 2009</ref> na implementação do algoritmo, que historicamente costuma ter um custo de tempo de computação [[expoente|exponencial]].
 
==Definições==
{{ref-section}}
[[Imagem:Hamiltonian path.svg|right|thumb|Um ciclo Hamiltoniano em um [[dodecaedro]]. Como todos os [[sólido platônico|sólidos platônicos]], o dodecaedro é Hamiltoniano.]]
[[Imagem:Hamilton path.gif|right|frame|Um caminho Hamiltoniano (em preto) sobre um grafo (em azul).]]
 
Um ''caminho Hamiltoniano'' ou ''caminho rastreável'' é um [[caminho (teoria dos grafos)|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 (teoria dos grafos)|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 ''[[grafo orientado|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.
 
{{Referências}}
 
=={{Ver também}}==