Caminho hamiltoniano: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
JAnDbot (discussão | contribs)
TXiKiBoT (discussão | contribs)
m Bot: Adicionando: sk:Hamiltonovská kružnica
Linha 30: Linha 30:
[[pl:Graf hamiltonowski]]
[[pl:Graf hamiltonowski]]
[[ru:Гамильтонов граф]]
[[ru:Гамильтонов граф]]
[[sk:Hamiltonovská kružnica]]
[[sl:Hamiltonova pot]]
[[sl:Hamiltonova pot]]
[[sr:Хамилтонов пут]]
[[sr:Хамилтонов пут]]

Revisão das 08h03min de 29 de maio de 2008

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 com 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.

Veja Também

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.