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

98 bytes adicionados ,  12h59min de 1 de julho de 2011
sem resumo de edição
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 (complexidade)|NP]], o que significa que é pouco provável que exista um algoritmo polinomial para o problema, alguns professores nem leem os trabalho e vão dar 10 para os alunos que escreveram essa bobeira. 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.
Utilizador anónimo