~ info project ~

Mai 5, 2010

Reprezentarea grafurilor orientate

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:45 pm
Tags: , , , , , , , ,

Considerăm un graf orientat G= (X,U) cu m arce şi n noduri.

Cele mai cunoscute forme de reprezentare sunt: matricea de adiacenţă, matricea vârfuri – arce, matricea drumurilor şi listele vecinilor.

Matricea de adiacenţă

Are aceeaşi semnificaţie ca în cazul grafurilor neorientate: fiecare element a[i,j], cu i,j ε {1,2,…,n}, este: 1 dacă există arcul (i,j), respectiv 0 în caz contrar.

Datorită orientării, aşa cum am mai spus, arcul (i,j) nu este totuna cu arcul (j,i). Prin urmare, a[i,j] ≠ a[j,i]. Aşadar matricea de adiacenţă nu mai este simetrică faţă de diagonala principală, aşa cum se întâmpla în cazul grafurilor neorientate.

Exemplu:

Pentru graful G=(X,U) din figura 5, matricea de adiacenţă este:

Continuăm cu câteva aplicaţii.

Aplicaţie:

Citirea de la tastatură şi afişarea matricei de adiacenţă

Prin citirea matricei de adiacenţă de la tastatură, putem memora arcele existente între nodurile unui graf. În cazul grafurilor neorientate, citeam doar “porţiunea” de deasupra diagonalei principale în matrice, deoarece matricea este simetrică. Acum trebuie să citim toate elementele matricei. Avem de-a face cu algoritmii banali de citire şi afişare a unei matrice cu n linii şi n coloane (unde n este numărul de noduri) în două cicluri for, deci nu considerăm că mai sunt necesare alte explicaţii. Prezentăm în continuare procedurile citire_matrice şi afişare_matrice.

Procedure citire_matrice;

{citeşte matricea de adiacenţă a de la tastatură}

var i,j: integer;

begin

writeln(‘Nr. Noduri: ‘); readln(n);

for i:=1 to n do

for j:=1 to n do

begin

write(‘[‘,i,’,’,j,’]=’);

readln(a[i,j]);

end;

end;

Procedure afişare_matrice;

{afişează matricea de adiacenţă a}

var i,j: integer;

begin

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j],’ ‘);

writeln();

end;

end;

Aplicaţie:

Citirea matricei de adiacenţă dintr-un fişier text

Aceasta este absolut similară cu cea prezentată la grafuri neorientate, unde a fost explicată pe larg. De fapt, este vorba despre algoritmul de citire a unei matrice oarecare dintr-un fişier text. Plecăm de la presupunerea că fişierul conţine pe primul rând valoarea lui n, apoi pe fiecare din următoarele n rânduri elementele unei linii a matricei separate de spaţii.

Procedure cit_matr_fis;

{citeşte numărul de noduri si matricea de adiacenta a din fişierul text cu descriptorul f}

var i,j: integer; nume_fis: string;

begin

write(‘Daţi numele fişierului ‘); readln(nume_fis);

assign(f,nume_fis); reset(f);

readln(f,n);

for i:=1 to n do

begin

for j:=1 to n do read(f,a[i,j]);

readln(f);

end;

close(f);

end;

Aplicaţie:

Construirea matricei de adiacenţă prin citirea “arcelor” de la tastatură

Se citesc de la tastatură m perechi de numere întregi de forma (x,y) reprezentând extremităţile celor m arce ale grafului, şi se construieşte matricea de adiacenţă a, cu n linii şi n coloane.

Mai întâi citim m şi n (numărul de arce respectiv numărul de noduri), şi iniţializăm toată matricea de adiacenţă cu 0, în două cicluri for. Apoi, într-un alt ciclu for, cu k de la i la m, citim cele m perechi de întregi (x,y).

–         Citirea fiecărei perechi (x,z) se face cu validare: repetă citirea lui x şi y până când ambele valori sunt în intervalul [1,n].

repeat

readln(x,y);

until (x>=1) and x(<=n) and (y>=1) and (y<=n) and (x<>y);

–         Pentru fiecare (x,y), marcăm în matricea de adiacenţă existenţa arcului (x,y), prin atribuirea a[x,y]:=1. Spre deosebire de grafurile neorientate, nu se mai face şi atribuirea a[y,x]:=1, deoarece arcul (x,y) nu e identic cu arcul (y,x).

Algoritmul prezentat a fost inclus în procedura citire_graf.

Procedure citire_graf;

var i, j, k, x, y: integer;

begin

write(‘Nr. Arce:’); readln(m);

write(‘Nr. Vârfuri’); readln(n);

{iniţializează cu 0 toata matricea de adiacenta}

for i:=1 to n do

for j:=1 to n do

a[i,j]:=0;

{citeşte m perechi (x,y) reprezentând arcele grafului}

for k:=1 to m do

begin

write(‘Muchia ‘,k,’: ‘);

repeat

readln(x,y);

until (x>=1) and x(<=n) and (y>=1) and (y<=n) and (x<>y);

{pentru fiecare pereche, marchează arcul in matricea de adiacenta}

a[x,y]:=1;

end;

end;

Aplicaţie:

Determinarea gradului exterior şi a gradului interior ale unui nod oarecare x

Scriem o funcţie {d_plus(x:integer):integer;} care returnează, gradul exterior al nodului x (notat d*(x)).

Gradul exterior al unui nod x este numărul arcelor care ies din nodul x, adică numărul arcelor de forma (x,j), cu j ε {1, 2, … , n}. Luăm ca exemplu graful cu n=4 noduri de mai jos, împreună cu matricea sa de adiacenţă:

Analizăm gradul exterior al nodului 2. Arcele care ies din nodul 2 sunt: (2,1), (2,3), (2,4) (nu şi (4,2)). Urmare a existenţei acestor arce, în matricea de adiacenţă vom avea a[2,1] = a[2,3] = a[2,4] = 1. Unde se găsesc în matricea de adiacenţă toate valorile de 1 corespunzătoare arcelor ce ies din nodul 2? Pe linia 2! Pe caz general, valorile de 1 de pe linia x în matricea de adiacenţă, reprezintă arcele care ies din nodul x. Deci gradul exterior al nodului x, adică numărul arcelor care ies din nodul x este egal cu numărul valorilor de 1 de pe linia x a matricei.

Aşadar algoritmul implementat în funcţia d_plus este foarte simplu:

Iniţializăm cu 0 o variabilă nr. în care numărăm valorile de 1 de pe linia x a matricei. Într-un ciclu, parcurgem coloanele j=1, 2, …, n ale liniei x. Pentru fiecare valoare a lui j, testăm elementul a[x,j] de pe linia x şi coloana j. Dacă aceasta are valoarea 1, atunci incrementăm nr. În final funcţia va returna ultima valoare a variabilei nr.

Function d_plus(x:integer):integer;

{returnează gradul exterior d* pentru un nod x; acesta este numărul valorilor de 1 de pe linia x a matricei de adiacenta}

var nr.,j: integer;

begin

nr.:=0;

for j:=1 to n do

if a[x,j] = 1 then nr:=nr + 1;

d_plus:=nr;

end;

Observaţie:

Destul de asemănător este şi algoritmul pentru determinarea gradului interior al nodului x (d- (x) ). Acesta reprezintă numărul arcelor care intră în nodul x, adică numărul arcelor de forma (i,x), cu i ε {1, 2, …, n}. Să vedem unde se regăsesc în matricea de adiacenţă arcele care intră în nodul x, luând ca exemplu x=4 pentru graful anterior. Arcele care intră în nodul 4 sunt (3,4) şi (2,4). Rezultă că în matrice avem a[3,4] = a[2,4] = 1. Am “reperat” astfel valorile de 1 de pe coloana 4 a matricei de adiacenţă. În acest moment putem concluziona că gradul interior al unui nod oarecare x reprezintă numărul valorilor de 1 de pe coloana x a matricei. Se poate scrie o funcţie asemănătoare cu cea de mai sus, care să returneze câte valori de 1 se găsesc pe coloana x.

function d_minus(x: integer): integer;

{returnează gradul interior d- pentru un nod x; acesta este numărul valorilor de 1 de pe coloana x a matricei de adiacenta}

var nr, i: integer;

begin

nr:=0;

for i:=1 to n do

if a[i,x]=1 then nr:=nr+1;

d_minus:=nr;

end;

Lasă un comentariu »

Niciun comentariu până acum.

RSS feed for comments on this post. TrackBack URI

Lasă un răspuns

Completează mai jos detaliile despre tine sau dă clic pe un icon pentru autentificare:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

Creează un sit web gratuit sau un blog la WordPress.com.

%d blogeri au apreciat asta: