proiectarea algoritmilor...8 proiectarea algoritmilor - curs 4 definitie se numeşte graf orientat o...

8

11

Lect. univ. dr. Adrian Runceanu

PROIECTAREA

ALGORITMILOR

8

22Proiectarea Algoritmilor - curs

Curs 8

Elemente de teoria

grafurilor

(partea III)

8


Conţinutul cursului

8.1. Grafuri orientate. Definiții.

8.2. Reprezentarea grafurilor orientate

8.3. Parcurgerea grafurilor orientate

8.4. Probleme rezolvate

8.5. Subiecte tip grilă

8


Definitie

Se numeşte graf orientat o pereche ordonată de

mulţimi G=(X,U), unde:

• X este o mulţime finită şi nevidă numită mulţimea

vârfurilor (nodurilor),

• iar U este o mulţime formată din perechi

ordonate de elemente distincte din X numită

mulţimea arcelor.

Daca eliminam o muchie, graful isi pierde

proprietatea de conexitate, iar daca adaugam o

muchie, apare un ciclu.

8


8.1. DefiniţiiExemplu:

X = {1, 2, 3, 4, 5};

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

1

2

3

4

5

8

66

Notatie

Orice arc se noteazăc cu u=(x,y) şi spunem

că x este extremitate iniţială şi y este extremitate

finală a arcului.

Definitie

Pentru graful G=(X,U) dacă există arcul u=(x,y)

spunem că vârfurile x şi y sunt adiacente şi

amândouă sunt incidente cu arcul u.

Observatie

Arcul (x,y) diferă de arcul (y,x).

Proiectarea Algoritmilor - curs

8



X = {1, 2, 3, 4, 5};

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

1

2

3

4

5

Vârfuri

adiacente

Arc incident cu

2 si 5

Extremitate

initiala

Extremitate

finala

8


8.1. Definiţii

Definitie Se numeşte grad exterior al

unui vârf x notat cu d+(x), numărul arcelor

de forma (x,y)U.

Definitie Se numeşte grad interior al

unui vârf x notat cu d-(x), numărul arcelor

de forma (y,x)U.

8


8.1. Definiţii

Exemplu:

X = {1, 2, 3, 4, 5};

U = {(1,2), (2,1), (2,3), (3,1), (2,5)};

2

13

4

5

d+(2)=3

d-(2)=1

d+(5)=0

d-(5)=1

5 - Nod terminal

d+(4)=0

d-(4)=0

4 - Nod izolat

8


Notatie

+(x)={yX|(x,y) U} - mulţimea succesorilor lui x

Notatie

-(x)={yX|(y,x) U} - mulţimea predecesorilor lui x

Notatie

ω+(x)={u=(x,y)| uU } – mulţimea arcelor ce ies din x

Notatie

ω-(x)={u=(y,x)| uU } – mulţimea arcelor ce intră in x

Observatie: Un vârf este izolat dacă are gradul

interior şi gradul exterior egale cu 0.

Observatie: Un vârf se numeşte terminal dacă are

gradul interior 1 şi gradul exterior 0.

8


Definitie Se numeşte lant o succesiune de arce

u1, u2 ... uk U, cu proprietatea ca oricare doua

arce (uk, uk+1) de pe pozitii consecutive au un

nod comun.

Observaţie: nu contează ordinea de parcurgere

Definitie Se numeşte drum o succesiune de

noduri x1, x2 ... xk X cu proprietatea că

(xi,xi+1) este arc.

Observaţie: contează ordinea de parcurgere

Dacă nodurile sunt distincte, drumul se numeşte

elementar.

8


8.1. Definiţii

Exemplu:

X = {1, 2, 3, 4, 5};

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

L1= (1,2), (2,3),(3,4)

L2= (1,5), (5,2),(2,3)

D1= {1,2,3,1,2}

drum neelementar

2

13

4

5

D2= {1,2,3,4}

drum elementar

8


Definitie Se numeşte circuit într-un graf

orientat un drum x1,x2 ... xk cu proprietatea

că x1 = xk şi arcele (xi,xi+1) să fie distincte

2 câte 2.

Definitie Un circuit în care toate nodurile

sunt distincte cu excepţia capetelor se

numeşte circuit elementar.

8


Definitie Un drum hamiltonian într-un graf

orientat este un drum care conţine toate vârfurile

grafului.

Definitie Intr-un graf orientat G=(X,U) se numeşte

circuit hamiltonian un circuit elementar care

conţine toate vârfurile grafului.

Definitie Intr-un graf orientat G=(X,U) se numeşte

circuit eulerian un circuit care conţine toate

arcele grafului.

Definitie Se numeşte graf eulerian un graf care

conţine un circuit eulerian.

8


8.1. Definiţii

Definitie Un graf parţial al grafului

orientat G=(X,U) este un graf G1=(X,V)

cu proprietatea că VU (este graful

însuşi sau se obţine din graful iniţial prin

eliminarea unor arce).

Se mai spune că graful parţial G1 este

indus de mulţimea de arce V.

8



X = {1, 2, 3, 4, 5};

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

V = {(2,1), (1,5), (3,1), (3,4), (2,3)};

2

13

4

5

2

1 3

4

5

8


8.1. Definiţii

Definitie Un subgraf al unui graf orientat

G=(X,U) este un graf H=(Y,V) astfel incât

YX şi V conţine toate arcele din U care au

ambele extremităţi în Y (poate fi graful însuşi

sau se obţine din acesta prin eliminarea unor

vârfuri şi a arcelor incidente cu acestea).

Spunem că subgraful H este indus de

mulţimea de vârfuri Y.

8


8.1. Definiţii

Exemplu:

X = {1, 2, 3, 4, 5};

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

Y = {1, 3, 4, 5};

V = {(1,5), (3,1), (3,4)};

13

4

5

2

1 3

4

5

8


Definitie Un graf orientat este complet dacă oricare

două vârfuri distincte ale sale sunt adiacente.

Observatii: Spre deosebire de grafurile neorientate unde graful

complet este unic, la grafurile orientate se pot construi

mai multe grafuri orientate complete cu n vârfuri.

Două vârfuri x şi y sunt adiacente într-un graf orientat

în oricare din situaţiile: există arcul (x,y) sau arcul (y,x)

sau arcele (x,y) şi (y,x).

Sunt n(n-1)/2 posibilităţi de a alege două vârfuri

distincte.

Pentru fiecare dintre acestea există 3 situaţii, deci în

total sunt 3n(n-1)/2 grafuri orientate complete cu n vârfuri.

8


Definitie Un graf este tare conex dacă

pentru oricare două vârfuri x, y X există un

drum de la x la y şi un drum de la y la x.

Definitie O componentă tare conexă a unui

graf orientat G=(X, U) este un subgraf

G1=(X1,Y1) al lui G care este tare conex şi

care este maximal în raport cu această

proprietate (adică oricare ar fi x X\X1,

subgraful lui G generat de X1{x} nu mai este

tare conex).

8


8.1. Definiţii

Exemplu:

3

1

2

4Graf tare conex

8


8.1. Definiţii

Exemplu:

Graf cu 2 componente

tare conexe

3

1

2

4

6

5

8


Definitie Fiecărei muchii a unui graf orientat i se

poate asocia o valoare care reprezintă costul

acelei muchii.

Definitie Un graf orientat în care fiecărei muchii i s-

a asociat o valoare se numeşte graf ponderat sau

graf valoric.

Definitie Fie un graf orientat G=(X, U) şi o funcţie

L: UR+, care asociază fiecărui arc uU lungimea

(costul sau ponderea) sa L(u).

Lungimea unui drum în acest graf este egală, prin

definiţie cu suma lungimilor asociate arcelor sale.

8


Definitie Un graf orientat cu proprietatea

că între oricare două vârfuri x şi y există

un arc şi numai unul se numeşte graf

turneu.

Definitie Numim transpusul unui graf

orientat G=(X, U) un graf G’=(X, U’) care

are aceeaşi mulţime de vârfuri ca şi graful

iniţial, arcele sale fiind cele ale grafului

iniţial dar având sens opus.

8



8.1. Grafuri orientate. Definiții





8


8.2 Reprezentari ale grafurilor orientate

Există mai multe moduri de reprezentare a grafurilor,

alegerea făcându-se în funcţie de tipurile de operaţii care

urmează să se efectueze:

1. Matricea de adiacenţă: face o asociere între

vârfuri şi indicii matricei. Este o matrice pătratică

cu nxn elemente, unde n este numărul de noduri.

1, dacă arcul (i,j) există

aij =

0, dacă arcul (i,j) nu există

8



Observatie

Matricea de adiacenţă a unui graf orientat nu este

simetrică faţă de diagonala principală.

Observatie

Numarul de valori “1” de pe linia “i” reprezintă

gradul exterior al nodului “i”.

Observatie

Numarul de valori “1” de pe coloana “i” reprezintă

gradul interior al nodului “i”.

8



2. Matricea de incidenţă (matricea vârfuri-arce): este o

matrice cu n linii şi m coloane, unde n este numărul de

vârfuri şi m este numărul de arce; pe linii se reţin vârfurile,

pe coloane se reţin muchiile; matricea are valorile 0, 1 şi -1.

1, dacă i este extremitate iniţială a arcului j

aij= -1, dacă i este extremitate finală a arcului j

0, dacă i nu este extremitate a arcului j

8


Observatie

Completarea matricei se face coloană cu

coloană. Pe fiecare coloană sunt două valori

diferite de 0 (1 pentru vârful iniţial, -1 pentru

vârful final) iar celelalte valori sunt 0.

Observatie

Numarul de valori “1” de pe linia “i” reprezintă

gradul exterior al nodului “i”.

Observatie

Numarul de valori “-1” de pe linia “i” reprezintă

gradul interior al nodului “i”.

8


3. Matricea drumurilor: este o matrice pătratică cu

nXn noduri unde n este numărul de vârfuri

1, dacă drumul de la i la j există

aij=

0, dacă drumul de la i la j nu există

Observatie

Matricea drumurilor se obţine din matricea de

adiacenţă prin aplicarea algoritmului lui Roy-

Warshall.

Se utilizează pentru a arăta dacă un graf este tare

conex sau nu.

Dacă în matrice sunt numai valori de 1, inseamnă

că graful este tare conex.

8



4. Matricea costurilor: pentru reprezentarea

grafurilor valorice. Este o matrice cu nXn elemente,

unde n este numărul de noduri.

costul arcului, dacă arcul (i,j) există

aij= 0, dacă arcul (i,j) nu există

∞ / -∞, dacă este o problemă de minim/maxim

Observatie

Matricea de costurilor unui graf orientat nu este

simetrică faţă de diagonala principală.

8


5. Liste de adiacenţă: Pentru fiecare nod se

memorează o listă a vecinilor săi.

Pentru întregul graf este necesar un vector de

liste (P) în care Pi este adresa primului element

al listei asociate lui i.

NodLista de adiacenţă

asociată

1 2,5

2 1,3

3 2

4 -

5 1

2

1

3

5

4

8








8



Prin algoritmul BF se realizeaza o parcurgere a

grafului „în lăţime“.

Se vizitează un vârf iniţial s, apoi vecinii

săi (vârfurile adiacente cu s), după

aceea vecinii vecinilor lui s (nevizitaţi

încă), etc.Observatie:

Dacă graful nu este conex nu se pot vizita

toate vârfurile.

8


Structuri de date necesare pentru implementare

sunt:

1. Matrice de adiacenţă (sau alte variante de

reprezentare): a

2. Coada (în care se memorează în ordinea

parcursă nodurile vizitate): c

– p, u - indicatorii primului şi ultimului element

din coadă

3. Vectorul nodurilor vizitate: viz

– viz[i]=1, dacă i a fost vizitat

– viz[i]=0, altfel

8



Parcurgerea BF(Breath First) se

efectuează prin utilizarea structurii numită

coadă, având grijă ca un nod să fie vizitat

o singură dată.

Atunci când un nod a fost introdus în

coadă, se marchează ca vizitat.

Observaţie: algoritmul se adaptează astfel

încât să poată fi luaţi în considerare toţi

vecinii unui nod.

8



Exemplu:

X = {1, 2, 3, 4, 5};

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

21

35

4

x = 1

Parcurgerea BF: 1, 2, 3, 4, 5

8



Algoritmul DF (Depth First) se

caracterizează prin faptul că realizează o

parcurgere a grafului „în adâncime“ atât cât

este posibil.

Parcurgerea începe cu un vârf s ales inițial.

Prelucrarea unui vârf conduce la

prelucrarea primului său vecin încă

nevizitat, apoi se prelucrează primul vecin

al acestuia care nu a fost încă vizitat, etc.

8



Structuri de date necesare implementării:

1. Matrice de adiacenţă (sau alte

variante): a

2. Stiva: s (în care se memorează nodurile

în ordinea parcurgerii). Dacă se

implementează varianta recursivă, se va

folosi stiva procesorului

3. Vectorul nodurilor vizitate: viz

8



Exemplu:

21

3

5

4

x = 10

Parcurgerea DF: 10, 4, 2, 1, 3, 6, 8, 7, 9, 5

6

7

8

9

10

8








8



Problema 1:

Determinati vecinii unui varf al unui graf orientat.

Exemplu:

Pentru varful 1, vecinii sunt: 2, 3 si 4

21

35

4

8



# include <iostream.h>

int main(void)

{

int n, a[50][50],i,j,x,v[50],k;

cout<<"Dati nr. de varfuri ale grafului orientat n = ";

cin>>n;

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

for(j=1;j<=n;j++){

cout<<"a["<<i<<“]["<<j<<"]=";

cin>>a[i][j];

}

8



cout<<"\n graful citit are "<<n<<" noduri! ";

cout<<"\n matricea sa de adiacenta este:\n";

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

{

for(j=1;j<=n;j++) cout<<" "<<a[i][j];

cout<<"\n";

}

cout<<"Dati varful ai carui vecini doriti sa-i

aflati: ";

cin>>x;

8



k=0;

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

if (a[i][x]==1 || a[x][i]==1)

{

k++;

v[k]=i;

}

cout<<"\n vecinii lui "<<x<<" sunt : ";

for(i=1;i<=k;i++) cout<<" "<<v[i];

}

8



Problema 2:

Determinati gradele exterioare si interioare ale

varfurilor unui graf, gradul exterior minim, gradul

exterior maxim, gradul interior minim si gradul

interior maxim.

Exemplu:

Pentru varful 1:

d+(1)= 2, d-(1)= 2

min d+(3,5)= 0, max d+(1,2)= 2

min d-(4)= 0, max d-(1)= 2

21

35

4

8



# include <iostream.h>

int minim(int v[50], int n)

{

int i, min=v[1];

for(i=2; i<=n; i++)

if(v[i] < min) min=v[i];

return min;

}

8



int maxim(int v[50],int n)

{

int i, max=v[1];

for(i=2; i<=n; i++)

if (v[i] > max) max=v[i];

return max;

}

8



int main(void)

{

int n, a[50][50],i,j,x, grad_e[50], grad_i[50];

cout<<"Dati nr. de varfuri ale grafului orientat

n = ";

cin>>n;

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

for(j=1;j<=n;j++){

cout<<"a["<<i<<"]["<<j<<"]=";

cin>>a[i][j];

}

8



cout<<"\n graful citit are "<<n<<" noduri!";

cout<<"\n matricea sa de adiacenta este: \n";

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

{

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

cout<<" "<<a[i][j];

cout<<"\n";

}

8



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

{

grad_e[i]=0; grad_i[i]=0;

}

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

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

if (a[i][j]==1) grad_e[i]++;

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

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

if(a[j][i]==1) grad_i[i]++;

8



for(i=1;i<=n;i++){

cout<<"\n pentru varful : "<<i;

cout<<"\n grad exterior = "<<grad_e[i];

cout<<"\n grad interior = "<<grad_i[i];

}cout<<"\n gradul exterior minim este " << minim(grad_e,n);

cout<<"\n gradul exterior maxim este " << maxim(grad_e,n);

cout<<"\n gradul interior minim este " << minim(grad_i,n);

cout<<"\n gradul interior maxim este " << maxim(grad_i,n);

}

8








8


8.5. Subiecte tip grila

1. Graful neorientat cu 60 de noduri, numerotate de la 1 la

60, are numai muchiile [1,60], [60,20], [20,30] si [4,3].

Numarul componentelor conexe ale grafului este egal

cu:

a) 3 b) 56 c) 54 d) 0

Raspuns: b) 56

Avem 4 muchii intre 6 noduri formand 2 componente

conexe.

Din 60 scadem cele 6 noduri si raman 54 de noduri izolate

adica 54 de componente conexe

Deci sunt 54 + 2 = 56 componente conexe

8



2. Se considera graful neorientat cu 7 noduri

numerotate de la 1 la 7 si muchiile [1,2], [1,3],

[2,3], [2,4], [2,5], [2,6], [4,6], [5,7], [6,7].

Care este numarul minim de muchii care trebuie

eliminate pentru ca acest graf sa contina 3

componente conexe?

8



Raspuns: 3

Raman 2 noduri izolate(1 si 3) si o componenta conexa

(2,4,5,6,7) 3 componente conexe

1 2

3 4

5

6

7

8



3. Se considera graful neorientat din figura alaturata. Care este

numarul minim de muchii ce se pot elimina astfel incat graful

partial obtinut sa aiba exact 3 componente conexe?

a) 2 b) 4 c) 1 d) 3

Raspuns: b) 4

4 raman 2 noduri

izolate + 1 componenta

conexa

3 componente conexe

1 2

543

8



4. Care este numarul maxim de componente

conexe pe care le poate avea un graf neorientat

cu 20 de noduri si 12 muchii?

a) 6 b) 12 c) 10 d) 15

Raspuns: d) 15Trebuie sa adaugam 12 muchii intre cat mai putine noduri.

Folosim formula: n(n-1)/2, n-numarul de noduri (formula ne ajuta sa aflam

numarul muchiilor dintr-un graf neorientat complet)

6(6-1)/2=15 intre 6 noduri putem adauga 15 muchii avem 6 noduri care

formeaza o componenta conexa si 14 noduri izolate

1+14 = 15 componente conexe

8



5. Se considera graful orientat reprezentat prin

listele de adiacenta alaturate. Cate noduri au

gradul extern mai mare decat gradul intern?

a) 3

b) 2

c) 1

d) 4

NodLista de adiacenţă

asociată

1 2,6,5

2 3

3 1

4 6

5 6

6 2

8



6. Se considera un graf orientat cu 6 noduri care

are urmatoarele proprietati:

- Suma gradelor externe ale tuturor varfurilor

grafului este egala cu 6.

- Sunt numai 3 varfuri care au gradul intern egal

cu 1

Care este valoarea maxima pe care o poate avea

gradul extern al unui varf din graful dat?

8



7. Se considera graful orientat reprezentat prin

matricea de adiacenta alaturata. Care este

lungimea maxima a unui drum de la varful 4

pana la varful 6 format din varfuri distincte doua

cate doua (lungimea unui drum este egala cu

numarul de arce care compun acel drum)?

a) 4

b) 3

c) 1

d) 5

8



8. Un graf orientat este reprezentat prin matricea

de adiacenta alaturata. Care dintre varfurile

grafului au gradul exterior un numar impar?

a) 1,3,4,5

b) 2,3,4,5

c) 1,4,5,6

d) 2,3,5

8



9. Se considera graful orientat din figura alaturata.

Care este numarul minim de arce care trebuie

adaugate si care sunt aceste arce, astfel incat

oricare doua varfuri din graf sa fie unite prin

drumuri elementare?1

4 3

2

8



10. Care este numarul minim de arce care trebuie

adaugate in graful orientat din figura laturata

astfel incat fiecare varf sa apartina unui circuit?

a) 1

b) 2

c) 3

d) 4

1

4 3

2

8


Întrebări?

proiectarea algoritmilor...8 proiectarea algoritmilor - curs 4 definitie se numeşte graf orientat o...

Documents