Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza
Upload





loading...
















































Reprezentarea grafurilor neorientate

Informatica


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

                                                                                  0   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        2                                                                 0   1     0     0 1

         2        1, 3, 4                                                         1    0    1     1   2          

         3        2, 4                                              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;.


loading...




Document Info


Accesari: 1154
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.




Coduri - Postale, caen, cor

Copyright © Contact (SCRIGROUP Int. 2017 )