Caminho 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 em G. E, um grafo que possua tal circuito é chamado de grafo hamiltoniano.
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 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ém um ciclo Hamiltoniano é chamado de grafo Hamiltoniano. Noções semelhantes podem ser definidas para 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.
Qualquer ciclo hamiltoniano pode ser convertido para um caminho Hamiltoniano, removendo-se uma de suas arestas, mas um caminho Hamiltoniano só pode ser estendido para um ciclo hamiltoniano se suas extremidades são adjacentes. O grafo linha de um grafo Hamiltoniano é Hamiltoniano. O grafo linha de um grafo Euleriano é Hamiltoniano. Um torneio (com mais de 2 vértices) é Hamiltoniano se e somente se ele é fortemente conectado. Um ciclo Hamiltoniano pode ser usado como base de uma prova com zero conhecimentos. Número de diferentes ciclos hamiltonianos para um grafo completo = (n-1)! / 2. Número de diferentes ciclos hamiltonianos para um grafo orientado completo = (n-1)!.
