Qual è la differenza tra un cammino hamiltoniano e un ciclo hamiltoniano?
Il titolo dice tutto. Ho visto definizioni confuse di questo e apprezzerei se qualcuno potesse chiarirlo brevemente con definizioni ed esempi.
Risposte
Il ciclo inizia e finisce nello stesso vertice, ma il percorso no.
Il percorso hamiltoniano è un percorso in un grafo non orientato o diretto che visita ogni vertice esattamente una volta che il ciclo hamiltoniano è un percorso hamiltoniano che è un ciclo e un ciclo è un percorso chiuso in cui il "primo vertice = ultimo vertice" è l'unico vertice che è ripetuto.
Per maggiori informazionihttps://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
https://en.wikipedia.org/wiki/Hamiltonian_path
Ciclo hamiltoniano = un ciclo (percorso che termina nello stesso vertice da cui inizia) che visita ogni vertice ($ n $bordi);
Cammino hamiltoniano= un cammino che visita ogni vertice ($ n - 1 $bordi).
Nel grafico rappresentato dalla matrice di adiacenza:
01001
10100
01010
00101
10010
Abbiamo 1 - 2 - 3 - 4 - 5cammini 1 - 5 - 4 - 3 - 2hamiltoniani. Inoltre, 1 - 2 - 3 - 4 - 5 - 1è un ciclo hamiltoniano.