Cammino hamiltoniano
Da Wikipedia, l'enciclopedia libera.
Nel campo matematico della teoria dei grafi, un cammino hamiltoniano è un cammino in un grafo non orientato che visita tutti i vertici una e una sola volta. Determinare se questo cammino esista è un problema NP-completo.
Si ha un ciclo hamiltoniano quando in un cammino hamiltoniano esiste un arco che collega l'ultimo vertice con il primo, realizzando così un ciclo che visita tutti i vertici per poi ritornare al punto di partenza.
Un grafo che contenga almeno un ciclo hamiltoniano viene detto grafo hamiltoniano.
Questi particolari cammini hanno preso il nome da William Rowan Hamilton che inventò un gioco da tavolo, il puzzle di Hamilton o icosian game, che consisteva nel trovare un cammino chiuso sul bordo di un dodecaedro.
[modifica] Proprietà
Il teorema di Dirac fornisce una condizione sufficiente (ma non necessaria) affinché un grafo con n vertici sia hamiltoniano: se il grado di ogni vertice (cioè il numero di spigoli adiacenti) è maggiore o uguale a n / 2, allora il grafo è hamiltoniano.
