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 varfurilor 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 varfurile 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 varfuri 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 varfuri Y.
Un graf complet cu n varfuri si care se noteaza cu Kn este un graf pentru care oricare doua varfuri sunt adiacente.
Un graf G se numeste graf bipartit daca exista o partitie a multimilor varfurilor, astfel incat fiecare muchie a grafului uneste un varf din X1 cu un varf din Xn.
Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U),unde X este multimea varfurilor 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 varfuri Y. Deci, un subgraf H al unui graf orientat G este graful G insusi sau se obtine din G prin suprimarea anumitor varfuri si a tuturor arcelor incidente cu acestea. Vom spune ca subgraful H este indus sau generat de multimea de varfuri Y.
Un graf orientat este complet daca oricare doua varfuri sunt adiacente.
GRAFURI HAMILTONIENE
Grafurile Hamiltoniene sunt grafuri neorientate.
Un ciclu elementar al unui graf G care trece prin toate varfurile 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 varfuri se intalnesc cate 3 muchii. Fiecare varf 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 intoarca in orasul din care a plecat.
Problema revine la gasirea unui ciclu hamiltonian in graful format cu varfurile si muchiile dodecaedrului.O problema mai generala este aceea a voiajorului comercial, care are urmatorul enunt:
Ne pare rau, pe moment serviciile de acces la documente sunt suspendate.
