Reprezentarea grafurilor neorientate
Consideram un graf neorientat G=(X,U) cu m muchii si n vârfuri numerotate 1, 2,.....,n.
Cele mai cunoscute forme de reprezentare ale unui astfel de graf, sunt: matricea de adiacent 828g61i 9;, listele vecinilor.
A. Matricea de adiacent 828g61i 9;
Este o matrice a cu n linii si n coloane, în care elementele a[i,j] se definesc astfel:
a[i,j]=1, daca muchia [i,j] cu i j
a[i,j]=0, în caz contrar
Exemplu:
Pentru graful G=(X,U) din figura 2, matricea de adiacent 828g61i 9; este:
Figura 2.
Coloana 1 2 3 4
1 0 0 1
1 0 1 1 2
A= 0 1 0 1 3 linia
0 1 1 0 4
Elementul a[2,3] (de pe linia 2 si coloana 3) va fi 1, întrucât exista în graf muchia (2,3). Dar aceasta muchie este identica cu muchia (3,2), deci si a[3,2] este 1. Analog neexistând muchia (1,4) respectiv (4,1), vom avea a[1,4]=a[4,1]=0.
Pe caz general, a[i,j]=a[j,i] oricare ar fi i,j , cu i j. Ce înseamna aceasta? Ca pentru orice graf neorientat, matricea de adiacenta este simetrica fata de diagonala principala.
B. Listele vecinilor
Pentru fiecare nod i (cu i=1, 2 , 3 ,......,n), formam lista vecinilor lui i. Aceasta cuprinde toate nodurile care sunt extremitati ale muchiilor ce trec prin nodul i.
Exemplu:
Pentru graful G=(X,U) din figura 2, prezentam listele vecinilor si alaturat matricea de adiacent 828g61i 9; pentru a face o comparatie:
nodul lista vecinilor Coloana 1 2 3 4
1 1 0 0 1
1 0 1 1 2
A= 0 1 0 1 3 linia
4 2, 3 0 1 1 0 4
Observam ca fiecare linie i din listele vecinilor contine indicii coloanelor pe care se gasesc valori de 1 în linia i a matricei de adiacent 828g61i 9;.
|
