Grafos

Um caminho hamiltoniano num grafo e um
Caminho onde ocorrem todos os vértices do
Grafo exatamente uma vez. Analogamente, um ciclo hamiltoniano ´e um ciclo que contém todos os vértices do grafo exatamente uma vez, com exceção dos vértices inicial e final que tem de coincidir. Um grafo diz-se hamiltoniano se possuir algum ciclo hamiltoniano.
Se retirarmos a ultima aresta a um ciclo hamiltoniano
Obtemos um caminho hamiltoniano, logo todo o grafo hamiltoniano possui caminhos hamiltonianos. No entanto, o recíproco desta afirmação não ´e verdadeiro, como o seguinte exemplo mostra.
O que é um grafo 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
Definições
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