Definitie: Se numeste graf orientat sau digraf (G) o pereche ordonata de multimi (X,U), unde X este o multime finita si nevida de elemente , iar U o multime de perechi ordonate formate cu elemente distincte din multimea X.
Scurt istoric: Graful este la origine un concept matematic. Teoria grafurilor are o vechime mult mai mare comparativ cu informatica. În informatică graful este privit ca o structură de date. O particularitate a grafurilor în informatică este faptul că de fiecare dată sunt considerate grafuri finite (cu număr finit de noduri). Informatica a preluat noţiunile teoriei grafurilor imaginând o multitudine de situaţii concrete rezolvabile cu algoritmi ce prelucrează structuri asimilate grafurilor.
În matematică și informatică, teoria grafurilor studiază proprietățile grafurilor. Un graf este o mulțime de obiecte (numite noduri) legate între ele printr-o mulțime de muchii cărora le pot fi atribuite direcții (în acest caz, se spune că graful este orientat). Un graf poate fi reprezentat geometric ca o mulțime de puncte legate între ele prin linii (de obicei curbe).
Grafurile au o importanță imensă în informatică, de exemplu:
- în unele problemele de sortare și căutare - elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri într-un graf;
- schema logică a unui program se poate reprezenta printr-un graf orientat în care o instrucțiune sau un bloc de instrucțiuni este reprezentat printr-un nod, iar muchiile direcționate reprezintă calea de execuție;
- în programarea orientată pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentată printr-un graf în care fiecare nod reprezintă o clasă, iar muchiile reprezintă relații între acestea (derivări, agregări).
Exemplu de graf orientat intalnit in viata de zi cu zi: Cel mai bun exemplu de aplicatie practica in viata reala a grafurilor neorientate sunt hartile rutiere. Putem afla astfel cel mai scurt drum pana intr-un anumit punct sau care puncte de pe harta sunt cel mai usor accesibil.Nodurile pot fi considerate orase, iar muchiile drumuri; grafurile orientate pot reprezente drumuri cu sens unic intre cladiri.
