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

78 bytes removidos ,  01h41min de 30 de junho de 2016
sem resumo de edição
[[Ficheiro:Hamilton path.svg|thumb|O caminho vermelho é hamiltoniano.]]
Um '''caminho hamiltoniano''' é um caminho inicialmente pensado por Diego Wendel de Oliveira Ferreira para a aula de PAA 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 (complexidade)|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.
Utilizador anónimo