LABORATOR 1

~Conversia reprezentarii grafelor~

I. Cerinta:

Sa se realizeze conversia unui graf din lista predecesorilor, cu ajutorul vectorilor a si b, in matricea de incidenta A.

II. Notatii:

Fie G= ( X,U ) graf, unde:

X mulţimea vârfurilor grafului , n=X|

U mulţimea arcelor grafului, m=U

X = {1,2,…,n}

U = {1,2,…,m}

n – numarul de noduri

m- numarul de muchii

a – indica adresa (indicele) din tabloul b

b – lista in care sunt inregistrati predecesorii

A – matricea de incidenta

III. Modelarea problemei:

a) Definirea listei predecesoriilor a are dimensiunea de n+1

b are dimensiunea m (pentru grafuri orientate) sau 2*m (pentru grafuri neorientate)

Pentru fiecare varf i X , a(i) indica adresa (indicele) din tabloul b de unde sunt inregistrati predecesorii sai.Predecesorii varfului I se afla, deci, in tabloul b intre pozitiile a(i) si a(i+1)-1 inclusiv. Daca a(i)=a(i+1), atunci varful I nu are nici un predecessor.

b) Definirea matricei de incidenta

AM n x m; elementele matricei de incidenta se definesc astfel:

A i u = 1 , kX: u=( i, k)

-1 , kX: u=( k, i) , iX, uU

0 , în rest

IV. Descrierea algoritmului Pseudocod

DATE: n, m, ( a i , i=1,…,n+1), ( bi, i=1,…,m )

REZULTATE: ( A i j, i=1,…,n, j=1,…,n)

Fiecare element din b va genera o coloana in matricea A. In aceasta coloana pe linia i trebuie sa fie plasata valoare -1, iar pe linia p valoarea 1 daca p=b(j) cu a(i)<= j<=a(i+1)-1, deoarece varful i este predecesor al varfului p = b(j)

Citeste n, (a(i), i=1,n+1); //se citeste numarul de noduri si apoi elementele din vectorul a

Citeste m,(b(i),i=1,m); //se citeste numarul de muchii si apoi elementele din vectorul b

Pentru i:=1,n executa

Pentru j:=1,m executa

A i j:=0; // se initializeaza toate elementele matricei A cu valoarea 0

sfPentru;

sfPentru;

u:=0;// contor pentru coloanele din A

pentru j:=1,n executa

pentru j:=a(i),a(i+1)-1,executa

u:=u+1; //creste dupa fiecare element introdus in matrice

A i u:=-1; // i->linia pe care se va pune valoarea -1

p:=b(j) //retine linia pe care se va pune valoarea 1

A p u:=1;

sfPentru

sfPentru;

Pentru i:=1,n executa

Pentru j:=1,m executa

afiseaza A i u

sfPentru;

sfPentru;

V. Codul Sursa in C++

#include <iostream>using namespace std;

int main() {int a[100],b[100],A[100][100],n,m,i,j,u,p;

cout<<"Dati numarul de noduri:";cin>>n;cout<<"Dati numarul de arce:";cin>>m;

cout<<"Dati elementele listei a:";for(i=1; i<=n+1; i++)

cin>>a[i];

cout<<"Dati elementele listei b:";for(i=1; i<=m; i++)

cin>>b[i];

for(i=1; i<=n; i++)for(j=1; j<=m; j++)

A[i][j] = 0;

u = 0;for(i=1; i<=n+1; i++)

for(j=a[i]; j<=a[i+1]-1; j++){

u = u+1;A[i][u] = -1;p = b[j];A[p][u] = 1;

}

cout<<"Matricea de incidenta este:"<<endl;for(i=1; i<=n; i++){

for(j=1; j<=m; j++)cout<<A[i][j]<<" ";

cout<<endl;}

return 0;}

VI. Date de test

a)Pentru Graful

n = 4 nr de varfuri

m = 5 nr de arce

Lista de predecesori

a = 1, 3, 4, 4, 6

b = 2, 4, 1, 1, 2

Matricea de incidenta

-1 -1 1 1 0A= 1 0 -1 0 1

0 0 0 0 00 1 0 -1 -1

b)Pentru Graful

n = 5 nr de varfuri

m = 6 nr de arce

Lista de predecesori

a = 1, 1, 3, 4, 5, 7

b = 1, 5, 1, 1, 1, 4

Matricea de incidenta

1 0 1 1 1 0-1 -1 0 0 0 0

A= 0 0 -1 0 0 00 0 0 -1 0 10 1 0 0 -1 -1

Studenta:

Daniela Stircu, grupa2 15