Cammino hamiltoniano

Nel campo matematico della teoria dei grafi, un cammino in un grafo (orientato o non orientato) è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta. Determinare se questo cammino esista è un problema NP-completo. In termini rigorosi, la determinazione di un cammino hamiltoniano è la ricerca di una permutazione ${\displaystyle (p_{0},p_{1},...,p_{n-1})}$ dei nodi tale che ${\displaystyle (p_{i},p_{i+1})\in E}$ per ogni ${\displaystyle 0\leq \ i\leq \ n-2}$ dove con E si intende l'insieme di archi del Grafo.

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.

Teorema di Bondy-Chvátal[modifica | modifica wikitesto]

Il migliore risultato relativo ai cicli hamiltoniani è dovuto a Bondy e Chvátal che nel 1976 provarono l'omonimo teorema che generalizza i risultati precedenti di Dirac e di Ore. L'enunciato utilizza la definizione di chiusura di un grafo che viene di seguito richiamata.

Chiusura di un grafo[modifica | modifica wikitesto]

Sia ${\displaystyle G}$ un grafo di ${\displaystyle n}$ vertici. La chiusura di ${\displaystyle G}$, ${\displaystyle [G]}$, si costruisce aggiungendo degli archi a ${\displaystyle G}$ che permettano di connettere due vertici non adiacenti ${\displaystyle v}$ e ${\displaystyle w}$ e tali che ${\displaystyle deg(v)+deg(w)\geq n}$. L'aggiunta di archi continua ricorsivamente finché non è possibile più trovare dei vertici che soddisfino la relazione sopra scritta.

Enunciato[modifica | modifica wikitesto]

Un grafo ${\displaystyle G}$ è Hamiltoniano se e solo se la sua chiusura ${\displaystyle [G]}$ è Hamiltoniana.

Corollari[modifica | modifica wikitesto]

• Il teorema di Ore fornisce una condizione sufficiente ma non necessaria affinché un grafo abbia un ciclo hamiltoniano; in particolare afferma che dato un grafo ${\displaystyle G}$ con ${\displaystyle n\geq 3}$ vertici, se per ogni coppia di vertici non adiacenti ${\displaystyle v}$ e ${\displaystyle w}$ vale ${\displaystyle deg(v)+deg(w)\geq n}$ allora il grafo è Hamiltoniano. Esso è un caso speciale del teorema di Bondy e Chvátal in quanto se vale ${\displaystyle deg(v)+deg(w)\geq n}$ per ogni coppia di vertici non adiacenti di ${\displaystyle G}$, allora ${\displaystyle [G]=K_{n}}$, dove ${\displaystyle K_{n}}$ rappresenta un grafo completo di ${\displaystyle n}$ vertici e ${\displaystyle K_{n}}$ è ovviamente Hamiltoniano.
• Il teorema di Dirac è, a sua volta, un corollario del teorema di Ore e afferma che un grafo ${\displaystyle G}$ di ${\displaystyle n\geq 3}$ vertici, tale che ${\displaystyle deg(v)\geq {\frac {n}{2}}}$ per ogni ${\displaystyle v\in G}$, è hamiltoniano.

Bibliografia[modifica | modifica wikitesto]

• Martin Gardner, Il gioco dell'icosaedro e la torre di Hanoi, in Enigmi e giochi matematici, Milano, Rizzoli, 2001 [1959], ISBN 88-17-12747-7.
• Andrian Bondy M. Ram Murty, Graph Theory, Springer, 2011, ISBN 978-1-84628-969-9.

Voci correlate[modifica | modifica wikitesto]

• Cammino euleriano

Altri progetti[modifica | modifica wikitesto]

• Wikimedia Commons contiene immagini o altri file su cammino hamiltoniano

Collegamenti esterni[modifica | modifica wikitesto]

• (EN) Hamilton circuit, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Cammino hamiltoniano, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica