Grafuri

In informatica grafurile pot fi: neorientate si orientate.Un graf neorientat G este o pereche ordonata de multimi (X,U),unde X este o multime finita, iar U este formata din perechi neordonate de elemente din X. Vom nota G=(X,U).

Multimea X se numeste multimea vârfurilor sau a nodurilor grafului G si multimea U se numeste multimea muchiilor grafului G.

O muchie, fiind un element din U, ea este o multime cu doua elemente din X, deci are forma {x,y},unde x,y sunt din X.Vom nota muchia {x,y} prin [x,y] si spunem ca ea uneste vârfurile x si y.

Tipurile de grafuri neorientate sunt:

-graf partial;

-subgraf;

-graf complet;

-graf bipartit;

-graf bipartit complet;

Un graf partial al unui graf G=(X,Y) este un graf G1=(X,V), care are aceeasi multime de vârfuri cu G, iar VU.

Un subgraf al unui graf G=(X,U) este un graf U=(Y,V),unde YX, iar muchiile din multimea V sunt toate muchiile din U, care au ambele extremitati in multimea de vârfuri Y.

Un graf complet cu n vârfuri si care se noteaza cu Kn este un graf pentru care oricare doua vârfuri sunt adiacente.

Un graf G se numeste graf bipartit daca exista o partitie a multimilor vârfurilor, astfel încât fiecare muchie a grafului uneste un vârf din X1 cu un vârf din Xn.

Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U),unde X este multimea vârfurilor sau a nodurilor grafului.Multimea U este formata din perechi ordonata de elemente distincte din X, numite arce. Orice arc u din U va fi notat prin u=(x,y), cu x,y din X si x<>y.

Tipuri de grafuri orientate sunt:

-graf partial;

-subgraf;

-graf complet;

Un graf partial al unui graf orientat G=(X,U) se defineste in acelasi mod ca si in cazul celui neorientat.El este un graf G=(X,V), unde VU, deci este graful G insusi sau se obtine din G prin suprimarea anumitor arce.

Un subgraf al lui G este un graf H=(Y,V) unde YX, iar arcele din V sunt toate arcele din U, care au ambele extremitati in multimea de vârfuri Y. Deci, un subgraf H al unui graf orientat G este graful G insusi sau se obtine din G prin suprimarea anumitor vârfuri si a tuturor arcelor incidente cu acestea. Vom spune ca subgraful H este indus sau generat de multimea de vârfuri Y.

Un graf orientat este complet daca oricare doua vârfuri sunt adiacente.

GRAFURI HAMILTONIENE

Grafurile Hamiltoniene sunt grafuri neorientate.

Un ciclu elementar al unui graf G care trece prin toate vârfurile grafului se numeste ciclu hamiltonian.

Un graf G care are un ciclu hamiltonian se numeste graf hamiltonian.

Originea acestui termen se gaseste intr-un joc inventat in anul 1857 de matematicianul William Hamilton.Partea sa principala este un dodecaedru regulat facut din lemn.

Acesta este un poliedru cu 12 fete care sunt toate pentagoane regulate, in fiecare din cele 20 de vârfuri se întâlnesc cate 3 muchii. Fiecare vârf al dodecaedrului lui Hamilton era marcat cu numele unui oras.Jocul consta in gasirea unui drum de-a lungul muchiilor dodecaedrului, care sa treaca prin fiecare din cele 20 de orase,exact la data si sa se întoarca in orasul din care a plecat.

Problema revine la gasirea unui ciclu hamiltonian in graful format cu vârfurile si muchiile dodecaedrului.O problema mai generala este aceea a voiajorului comercial, care are urmatorul enunt: