Moduri de reprezentare a unui graf

A. O prima modalitate de reprezentare este listarea efectiva a tuturor nodurilor si a arcelor sale.

B. Putem reprezenta graful dand pentru fiecare nod multimea nodurilor cu care formeaza arce in care el este pe prima pozitie.

C. Putem reprezenta geometric graful, printr-un desen in plan, reprezentand fiecare nod printr-un punct(cerculet) si fiecare arc printr-un segment de curba care are ca extremitati nodurile arcului si pe care este trecuta o sageata orientata de la nodul initial spre cel final.

D. Putem folosi o reprezentare geometrica in care nodurile sunt reprezentate de doua ori, in doua siruri paralele, de la fiecare nod din unul din siruri plecand sageti spre nodurile cu care formeaza arce in care el este pe prima pozitie, de pe al doilea sir (reprezentarea prin corespondenta).

E. Un graf poate fi reprezentat printr-o matrice patratica booleana, de dimensiune egala cu numarul de noduri, in care o pozitie aij va fi 1 daca exista arcul (xi,xj) si 0 in caz contrar, numita matricea adiacentelor directe.

F. Un graf poate fi reprezentat printr-o matrice patratica latina, de dimensiune egala cu numarul de noduri, in care pe o pozitie aij va fi xixj daca exista arcul (xi,xj) si 0 in caz contrar.

Exemplu: Daca in reprezentarea A avem graful G = (X,U), unde X = si U = , atunci in celelalte reprezentari vom avea:

D (reprezentarea prin corespondenta)