¿Cuál es la diferencia entre un camino hamiltoniano y un ciclo hamiltoniano?
El título lo dice todo. He visto definiciones confusas de esto, y agradecería si alguien puede aclarar esto de manera sucinta con definiciones y ejemplos.
Respuestas
El ciclo comienza y termina en el mismo vértice, pero el camino no.
El camino hamiltoniano es un camino en un gráfico dirigido o no dirigido que visita cada vértice exactamente una vez El ciclo hamiltoniano es un camino hamiltoniano que es un ciclo, y un ciclo es un camino cerrado en el que el "primer vértice = último vértice" es el único vértice que es repetido.
Para más informaciónhttps://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
https://en.wikipedia.org/wiki/Hamiltonian_path
Ciclo hamiltoniano = un ciclo (camino que termina en el mismo vértice que comienza) que visita todos los vértices ($ n $bordes);
camino hamiltoniano = un camino que visita todos los vértices ($ n - 1 $bordes).
En el gráfico representado por la matriz de adiacencia:
01001
10100
01010
00101
10010
Tenemos 1 - 2 - 3 - 4 - 5o 1 - 5 - 4 - 3 - 2caminos hamiltonianos. Además, 1 - 2 - 3 - 4 - 5 - 1es un ciclo hamiltoniano.