*Grafuri Orientate

*Cuprins

*Notiuni generale

*Matricea drumurilor. Algoritmul lui Roy Warshall.

*Matricea drumurilor

*Matricea costurilor minime. Algoritmul lui Roy Floyd.

*Algoritmul lui Djikstra

*Notiuni generale

*Se numeste graf orientat G perechea de multimi X,U, unde X este multimea varfurilor, iar U este multimea arcelor.

*Fiecare arc din aceasta multime are o orientare (un sens).

Inapoi

Un exemplu de graf orientat este: reţeaua de străzi a unui oraş. Străzile sunt muchii în graf, iar intersecţiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui oraş” este neorientat.

Cu totul altfel stau lucrurile în ceea ce priveşte conducătorii auto, pentru că în orice oraş există străzi cu sens unic. Pentru un şofer străzile trebuie să primească în graf o anumită orientare. Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă. Am ajuns astfel la noţiunea de graf orientat.

Inapoi

G = (X,U)

X={1,2,3,4}

U={(1,2),(1,3),(2,3),(2,4),(4,2),(4,3)}

1

2 3

4

Inapoi

*Se numeste lant intr-un graf orientat o succesiune de noduri adiacente.

Exemplu lant : 1,3,4

*Se numeste drum intr-un graf orientat o succesiune de noduri adiacente la care arcele au toate aceeasi orientare.

Exemplu drum : 1,2,4,2

*Lantul elementar este lantul in care nodurile sunt distincte 2 cate 2 (ex : 1,2,3).

*Drumul elementar este drumul in care nodurile sunt distincte 2 cate 2 (ex: 1,2,4,3).

1

2 3

4

Inapoi

1

2

3

4

5

6

G=(X,U)U={(1,2),(1,4),(1,5),(2,3),(3,4),(4,6),(5,6)}X={1,2,3,4,5,6}

Inapoi

*Graful partial

*Se da un graf G format din multimea varfurilor X si multimea muchiilor U.

*Se numeste graf partial graful G1, format din perechea (X1,U1), unde X1=X,U1<=U.

*Graful partial se obtine din graful initial prin suprimarea unor muchii ale acestuia.

Inapoi

G1=(X1,U1)X1={1,2,3,4,5,6}U1={(1,2),(1,4),(2,3),(5,6)}

1

2

3

4

5

6

Inapoi

*Subgraful

*Se numeste subgraf al grafului G un graf G2, format din perechea (X2,U2), unde X2<=X,U2<=U.

*Un subgraf se obtine din graful initial prin suprimarea unor varfuri si a tuturor muchiilor adiacente cu acesta.

Inapoi

G2=(X2,U2)

X2={1,2,3,5}

U2={(1,2),(1,5),(2,3)}

21

3

5

Inapoi

Exista 2 tipuri de grade :

*Grad interior g+/-(i)= numarul de arce care intra in nodul i.

*Grad exterior g+(i) = numarul de arce care ies din nodul i.

i 1 2 3 4

g-(i) 0 2 3 1

g+(i) 2 2 0 2

1

2 3

4

Inapoi

*Matricea drumurilor. Algoritmul Roy-Warshall.

*Se numeste drum intr-un graf neorientat o succesiune de drumuri

*Matricea drumurilor este o matrice binara (la fel ca cea de adiacenta), patratica (n x n), in care fiecare element

*d[i][j] = 1, drum intre i si j

= 0, altfel

Inapoi

*Matricea drumurilor

i/j 1 2 3 4

1 0 1 1 0

2 0 0 1 1

3 0 0 0 0

4 0 1 1 0

i/j 1 2 3 4

1 0 1 1 1

2 0 0 1 1

3 0 0 0 0

4 0 1 1 0

Inapoi

Algoritmul Roy-Warshall

for(i=1;i<=n;i++)for(j=1;J<=n;j++)for(k=1;k<=n;k++)if(a[i][j]==0&&i!=j&&i!=k&&j!=k) a[i][j]=a[i][k]*a[k][i];

Inapoi

*Matricea costurilor minime. Algoritmul lui

Roy Floyd. *Matricea costurilor minime este o matrice

binara (la fel ca cea de adiacenta), patratica (n x n), in care fiecare element

*c[i][j] = cost muchie (i,j)

= 0, i=j

= ∞, nu muchia (i,j)

Inapoi

1

2 3

4

24 21

34

52

46

09

Inapoi

Algoritm matricea costurilor minime (Roy-Floyd)

for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(c[i][k]+c[k][j]<c[i][j])c[i][j]=c[i][k]+c[k][j];for(i=1;i<=n;i++){for(j=1;j<=n;j++)cout<<“c[i][j]<<“ “;cout<<endl;}f.close();}

Inapoi

*Matricea costurilor minime

i/j 1 2 3 4

1 0 52 46 ∞

2 ∞ 0 34 24

3 ∞ ∞ 0 ∞

4 ∞ 60 21 0

i/j 1 2 3 4

1 0 1 1 0

2 0 0 1 1

3 0 0 0 0

4 0 1 1 0

Inapoi

*Algoritmul lui Dijkstra

Se da un graf orientat (sau neorientat) reprezentat prin matricea costurilor si se cere sa se determine pentru oricare 2 noduri x si y lungimea minima a drumului intre x si y. Prin lungimea unui drum se intelege suma costurilor arcelor care il alcatuiesc. Algoritmul foloseste urmatoarele structuri de date:

*Vectorul S (numit vector caracteristic) – are n componente si valori de 0 si 1: 0 daca nodul nu a fost vizitat si 1 daca nodul a fost vizitat.

Inapoi

*Vectorul tatilor – vectorul in care , pentru nodul I, se retine nodul precedent pe unde trece drumul de la nodul de pornire la i.

*Vectorul drumurilor – care retine pe pozitia I costul drumului gasit la un moment dat de la nodul de pornire la i.

*Vectorul drumurilor –care retine pe pozitia I costul drumului gasit la un moment dat de la nodul de pornire la i.

Inapoi

Algoritmul lui DijkstraCitire Programul principal Afisare

#include<iostream.h>#include<fstream.h>float a[50],d[50],min;int s[50], t[50], n, i, j, r, poz;void drum(int i){if(t[i]) drum(t[i]);cout<<i<<“ “;}

void main(){fsteam f(“matrice.txt”;ios::in);f>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)f>>a[i][j];cout<<“r=“;cin>>r;s[r]=1;for(i=1;i<=n;i++){d[i]=a[r][i];if(i!=r)if(d[i]<3200)

t[i]=r;}for(i=1;i<=n-1;i++){min=32000;for(j=1;i<=n;j++){if(s[j]==0)if(d[j]<min){min=d[j];poz=j;}s[poz]=1;for(j=1;j<=n;j++)if(s[j]==0)if(d[j]>d[poz]+a[poz][j]){d[j]=d[poz]+a[poz][j];t[j]=poz;}}

for(i=1;i<=n;i++)if(i!=r)if(t[i]){cout<<“distranta de la”<<r<<“la”<<i<<“este”<<d[i]<<endl;drum(i);cout<<endl;}elsecout<<“nu exista drum de la “<r<<“la”<<i<<endl;f.close();}

Inapoi

1

2

4

5

3

44

34

53

3163

i/j 1 2 3 4 5

1 0 34 ∞ 44 ∞

2 ∞ 0 31 ∞ 53

3 ∞ ∞ 0 ∞ ∞

4 ∞ 63 ∞ 0 ∞

5 ∞ ∞ ∞ ∞ 0

* Algoritmul lui Dijkstra

Inapoi

*Realizat de:

*Dima Teodor

*Dutu Razvan

*Ionescu Costin

*Ivan Alexandru

*Nicola Eduard

*Panait Beatrice