Qual é a diferença entre um caminho hamiltoniano e um ciclo hamiltoniano?

Question

O título diz tudo. Eu vi definições confusas disso e gostaria que alguém pudesse esclarecer isso sucintamente com definições e exemplos.

Answer 1

O ciclo começa e termina no mesmo vértice, mas o caminho não.

Answer 2

Caminho hamiltoniano é um caminho em um grafo não direcionado ou direcionado que visita cada vértice exatamente uma vez. repetido.
Para mais informaçõeshttps://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
https://en.wikipedia.org/wiki/Hamiltonian_path

Answer 3

Ciclo hamiltoniano = um ciclo (caminho que termina no mesmo vértice em que começa) que visita todos os vértices ($ n $arestas);
caminho hamiltoniano = um caminho que visita todos os vértices ($ n - 1 $arestas).

No gráfico representado pela matriz de adiacência:

01001
10100
01010
00101
10010

Temos 1 - 2 - 3 - 4 - 5ou 1 - 5 - 4 - 3 - 2caminhos hamiltonianos. Além disso, 1 - 2 - 3 - 4 - 5 - 1é um ciclo hamiltoniano.