Топ-100
Indietro

ⓘ Cammino hamiltoniano. Nel campo matematico della teoria dei grafi, un cammino in un grafo è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una ..




Cammino hamiltoniano
                                     

ⓘ Cammino hamiltoniano

Nel campo matematico della teoria dei grafi, un cammino in un grafo è 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 } dei nodi tale che ∈ E {\displaystyle \in E} per ogni 0 ≤ i ≤ n − 2 {\displaystyle 0\leq \ i\leq \ n-2} dove con E si intende linsieme di archi del Grafo.

Si ha un ciclo hamiltoniano quando in un cammino hamiltoniano esiste un arco che collega lultimo 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.

                                     

1. Teorema di Bondy-Chvátal

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

Chiusura di un grafo

Sia G {\displaystyle G} un grafo di n {\displaystyle n} vertici. La chiusura di G {\displaystyle G}, =K_{n}}, dove K n {\displaystyle K_{n}} rappresenta un grafo completo di n {\displaystyle n} vertici e K n {\displaystyle K_{n}} è ovviamente Hamiltoniano.

  • Il teorema di Dirac è, a sua volta, un corollario del teorema di Ore e afferma che un grafo G {\displaystyle G} di n ≥ 3 {\displaystyle n\geq 3} vertici, tale che d e g v ≥ n 2 {\displaystyle degv\geq {\frac {n}{2}}} per ogni v ∈ G {\displaystyle v\in G}, è hamiltoniano.
                                     
  • topologico X Cammino casuale Cammino euleriano Cammino hamiltoniano Cammino libero medio Cammino libero medio anaelastico Cammino minimo Cammino spirituale
  • la nozione di cammino euleriano si può definire per varie strutture relazionali. Un cammino euleriano sopra un multigrafo è un cammino che tocca tutti
  • Lagrangiana Hamiltoniano in meccanica quantistica, operatore hermitiano corrispondente all energia totale di un sistema fisico Hamiltoniano in meccanica
  • Dato un grafo diretto ponderato e un intero K, c è un cammino hamiltoniano o ciclo hamiltoniano se il commesso deve ritornare a casa con un peso totale
  • Petersen ha un cammino hamiltoniano ma nessun ciclo hamiltoniano È il più piccolo grafo cubico privo di ponti senza cicli hamiltoniani È ipohamiltoniano
  • della biologia molecolare per risolvere un istanza del problema del cammino hamiltoniano su un grafo orientato PPHO Questa è stata la prima volta che un
  • problemi a quelli di cammini minimi e forniscono un esempio specifico di una riduzione dal problema NP - completo del cammino hamiltoniano Se un grafo contiene
  • cammino hamiltoniano nella teoria dei grafi. Similmente, trovare un percorso del cavallo chiuso è un esempio del problema del ciclo hamiltoniano
  • un multidigrafo connesso, privo di cappi e dotato di un cammino euleriano, cioè di un cammino che tocca tutti i suoi archi una e una sola volta. Si pone
  • finali e poi si trova il cammino tra esse, come se il sistema sapesse in qualche maniera dove sta andando. L integrale sui cammini è un modo di capire perché
  • esistenza di cammini hamiltoniani colorabilità, planarità e connettività dei diversi tipi. All opposto, i problemi riguardanti i cammini euleriani riguardano