Graf hamiltonian
Un graf este graf hamiltonian dacă are un ciclu hamiltonian în interiorul său.
Se numește ciclu hamiltonian un ciclu elementarÎntr-un ciclu elementar un nod este parcurs o singură dată. care conține toate vârfurile grafului.
Prin urmare, numim hamiltonian un graf care conține un ciclu elementar ce parcurge toate nodurile grafului.
Iată un exemplu de graf hamiltonian și 2 cicluri hamiltoniene diferite:
Un graf hamiltonian poate avea mai multe cicluri hamiltoniene.
Ciclurile din exemplu trec prin toate nodurile grafului, o singură dată, astfel îndeplinind proprietatea de cicluri hamiltoniene.
Proprietățile grafului hamiltonian
Teoremă (suficientă)
Un graf neorientat cu n noduri în care gradulGradul unui nod reprezintă numărul de muchii incidente cu acesta. fiecărui nod este mai mare sau egal cu n/2 (jumătate din totalul de noduri) este graf hamiltonian.
Intuiția teoremei apare din observația că un grad peste jumătate din numărul de noduri asigură că pentru fiecare nod avem o muchie care nu a fost folosită deja.
Se poate forma astfel un ciclu hamiltonian care generează un graf hamiltonian.
Reciproca teoremei nu este valabilă.
Cu implicație de la teorema prezentată anterior, putem defini următoarea proprietate.
Un graf completGraful complet este graful care are toate muchiile posibile. este hamiltonian.
Cel mai simplu graf hamiltonian cu n noduri poate fi reprezentat grafic printr-un poligon cu n vârfuri.