Există mai multe moduri de reprezentare a grafurilor,alegerea
făcându-se în funcţie de tipurile de operaţii care urmează să se
efectueze:
1.Matricea de adiacenţă: face o asociere întrevârfuri şi indicii matricei. Este o matrice pătratică cu nxn elemente, unde n este numărul de noduri.
Observatie!
- Matricea de adiacenţă a unui graf orientat nu este simetrică faţă de diagonala principală.
Observatie!
- Numarul de valori “1” de pe linia “i” reprezintă gradul exterior al nodului “i”.
Observatie!
- Numarul de valori “1” de pe coloana “i” reprezintă gradul interior al nodului “i”.
2. Matricea de incidenţă (matricea vârfuri-arce): este o matrice cu n linii şi m coloane,unde n este numărul de vârfuri şi m este numărul de arce; pe linii se reţin vârfurile,
pe coloane se reţin muchiile; matricea are valorile 0, 1 şi -1.
Observatie !
- Completarea matricei se face coloană cu coloană. Pe fiecare coloană sunt două valori diferite de 0 (1 pentru vârful iniţial, -1 pentru vârful final) iar celelalte valori sunt 0.
Observatie !
- Numarul de valori “1” de pe linia “i” reprezintă gradul exterior al nodului “i”.
Observatie !
- Numarul de valori “-1” de pe linia “i” reprezintă gradul interior al nodului “i”.
3.Matricea drumurilor: este o matrice pătratică cu nXn noduri unde n este numărul de vârfuri.
Observatie !
- Matricea drumurilor se obtine din matricea de adiacenta algoritmului lui Roy Warshall.
Observatie !
- Se utilizează pentru a arăta dacă un graf este tare conex sau nu.
- Dacă are în matrice numai valori de 1, inseamnă
că graful este tare conex.
4. Matricea costurilor: pentru reprezentarea grafurilor valorice. Este o matrice cu nXn elemente, unde n este numărul de noduri.
Observatie !
- Matricea de costurilor unui graf orientat nu este simetrică faţă de diagonala principală.
5. Liste de adiacenţă: Pentru fiecare nod se memorează o listă a vecinilorsăi. Pentru întregul graf este necesar un vector de liste (P) în care Pi este adresa primului element al listei asociate lui i.
Niciun comentariu:
Trimiteți un comentariu