Graful hamiltonian
Un graf este graf hamiltonian dacă are un ciclu hamiltonian în interiorul său.
Se numește ciclu hamiltonian un ciclu elementar care conține toate vârfurile grafului.
Prin urmare, numim hamiltonian un graf care conține un ciclu elementar ce parcurge toate nodurile grafului.
Exemplu de graf hamiltonian și cicluri hamiltoniene:
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 noduri în care gradul fiecărui nod este mai mare sau egal cu (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 în ciclu.
Se poate forma astfel un ciclu hamiltonian care generează un graf hamiltonian.
Reciproca teoremei nu este valabilă.
Particularitate implicată
Din teorema anterioară, se poate defini următoarea particularitate:
Un graf complet este hamiltonian.
Cel mai simplu graf hamiltonian cu noduri poate fi reprezentat grafic printr-un poligon cu vârfuri.