Reprezentarea grafurilor

1. Punerea în evidenţă a vectorului de muchii.
De exemplu pentru figura de mai jos. V={1,2,3,4,5,6}
U={[1,5],[1,6],[3,6],[3,5],[3,4],[6,5]}

2. Lista de adiacenţă: pentru fiecare nod punem în evidenţă mulţimea nodurilor cu are formează muchii. Pentru exemplul din figura de mai sus, lista de adiacenţă corespunzătoare grafului este:

3. Matricea de adiacenţă: un graf poate fi memorat printr-o matrice pătratică booleană, de dimensiune egală cu numărul de noduri, în care o poziţie a[i,j] va fi 1 dacă există arcul (xi,xj) şi 0 în caz contrar, numită matricea adiacenţelor directe.

Observaţii:
1. Numărul de elemente din lista de adiacenţă corespunzătoare unui nod i este acelşi cu gradul vârfului
2. Matricea de adiacenţă este o matrice simetrică faţă de diagonala principală
3. Suma elementelor dintr-o matrice de adiacenţă este 2m.
4. Pe linia i şi pe coloana i avem un număr de elemente 1 egal cu d(i).
5. Pe diagonala principală a unei matrice de adiacenţă corespunzătoare unui graf neorientat sunt numai elemente 0