Graful hamiltonian

Un graf neorientat 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.

Un graf hamiltonian poate avea mai multe cicluri hamiltoniene.

Graf hamiltonian

  Ciclurile evidențiate trec prin toate nodurile grafului, o singură dată, astfel îndeplinind proprietatea de cicluri hamiltoniene. Graful este un graf hamiltonian.

Proprietăți ale grafului hamiltonian

Un graf completGraful complet este graful care are toate muchiile posibile. este hamiltonian.

Putem considera graful complet ca fiind un poligon și vom alege ciclul hamiltonian mergând pe „contur”.

Graf complet și hamiltonian

Cel mai simplu graf hamiltonian cu n noduri poate fi reprezentat grafic printr-un poligon cu n vârfuri.

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.

Reciproca teoremei nu este valabilă.