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















Reprezentarea grafurilor neorientate

Informatica



loading...








ALTE DOCUMENTE

Servicii XP-Optimizare
Problema
Acoustica CDDVD Label Maker 2
Conceptul de baza de date
Macromedia Dreamweaver
Interfata seriala in PC
Schema de preluare date statice MFG din fisiere Excel, prin conversie in fisiere CIM
Cercetarea informatiilor
MULTIMEDIA
Calculatorul


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;.


Document Info


Accesari: 948
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.

 


Copyright © Contact (SCRIGROUP Int. 2014 )