Liceul Teoretic Dunarea

Galati

Grafuri orientate

ElevElev:Lepădatu Alexandru Profesor Profesor indrumatorindrumatorClasaClasa a-XII-a E Burlacu Cătălina

کک PROMOTIA 2015PROMOTIA 2015 کک

1

CUPRINS

1. Motivatia lucrarii....................................................................32. Grafuri orientate-notiuni de baza...........................................4 a) Notiunea de graf orientat..................................................4 b) Definitie............................................................................63. Graful unui varf......................................................................6 a) Multimile Γ si ω................................................................64. Graf partial si subgraf............................................................75. Reprezentarea grafurilor orientate.........................................86. Matricea de adiacenta............................................................9

a) Citirea de la tastatura si afisarea matricei de adiacenta.............................................................................9

b)Citirea matricei de adiacenta dintr-un fisier text..............11 c)Construirea matricei de adiacenta prin citirea arcelor de la tastatura....................................................11

d)Determinarea gradului exterior si a gradului interior al unui nod oarecare x......................................137. Matricea varfurilor-ace .......................................................168. Listele vecinilor...................................................................189. Reprezentarea grafului ca un vector de muchii...................1910. Nodurile izolate intr-un graf orientat..................................1911. Celebritate..................................................................2212. Interpretarea datelor............................................................2313. Drumuri si circuite in grafuri orientate...............................2514. Matricea drumurilor............................................................2715. Algoritmul Roy-Warshall de determinare a matricei

drumurilor...........................................................................2816. Bibliografie.........................................................................35

2

Motivatia lucrarii

Un graf este o submultime de obiecte (numite noduri) legate intre ele printr-o multime de muchii carora le pot fi atribuite directii (in acest caz, se spune ca graful este orientat). Vizual, un graf poate fi reprezentat ca o multime de puncte legate intre ele prin linii (de obicei curbe). Grafurile au fost studiate intensiv de numerosi matematicieni si fizicieni precum Cayley, pe care l-au interesat aplicatiile lor in chimia organica, sau Kirchhoff, care a studiat aceasta categorie pornind de la studiul retelelor electrice. Grafurile au o importanta imensa in informatica, de exemplu: in unele probleme de sortare si cautare elementele multimii pe care se face sortarea sau cautarea se pot reprezenta prin noduri intr-un graf; schema logica a unui program se poate reprezenta printr-un graf orientat in care o instructiune sau un bloc de instructiuni este reprezentat printr-un nod, iar muchiile directionate reprezinta calea de executie; in programarea orientata pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentata printr-un graf in care fiecare nod reprezinta o clasa, iar muchiile reprezinta relatii intre acestea (derivari, agregari). De asemenea m-a captivat acest capitol al informaticii si de aceea am ales aceasta tema.

3

2.Grafuri orientate – noţiuni de bază

a) Noţiunea de graf orientat

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.

4

Numim graf orientat, o pereche ordonată

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

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

mulţimea nodurilor (vârfurilor);

U este o mulţime formată din perechi ordonate

de elemente ale lui X,

numită mulţimea arcelor (muchiilor)

Observaţii:

Prin noţiunea de perechi

ordonate nu trebuie să

înţelegem că o muchie este

mai mare decât alta, ci pur şi

simplu că facem deosebire

între o muchie de forma (x,z)

şi o alta de forma (y,x). Cu

alte cuvinte muchiile sunt

diferenţiate prin ordinea de

scriere a simbolurilor.

Arcul (x,y) nu este tot una cu

arcul (y,x).

Exemplu:

Pentru graful G=(X,U) din figura 1 avem: X={1, 2, 3, 4}

şi U={u1, u2, u3, u4, u5, u6, u7,}= {(1,1), (2,1), (3,2),

(2,3), (2,4), (3,4), (3,4)}

arc va fi de forma u= (x,y), unde x se numeşte

extremitate iniţială, iar y se numeşte extremitate finală

a arcului. Cu alte cuvinte, “arcul iese din nodul x şi intră

în nodul y”. La fel ca la grafurile neorientate, vom

spune că nodurile x şi y sunt adiacente, iar arcul u şi

nodul x sunt incidente (la fel arcul x şi nodul y). Nodul y

se numeşte succesor al lui x, iar nodul x se numeşte

predecesor al lui y. Un arc de forma (x,x), care iese din

nodul x şi intră tot x, se numeşte buclă.

5

Figura1

U3

U2

U4

U5

U6

U1

U7

3

4

1

2

Exemplu:

În graful din figura 1, avem bucla (1,1).

Într-un graf putem avea două sau mai multe arce

identice.

Exemplu :

În graful din figura 1, există două arce identice, u6 = u7

= (3,4)

b) Definiţie

3. Gradul unui vârf

a) Mulţimile Γ şi ω

Gradul exterior al unui vârf x, notat d*(x), reprezintă

numărul arcelor care ies din nodul x, adică numărul

arcelor de forma (x,z) ε U.

Analog, se defineşte gradul interior al unui vârf x, notat

d-(x), ca fiind numărul arcelor care intră în nodul x (de

forma (y,x) ε U).

Exemplu:

În graful reprezentat în figura 1, pentru nodul x=2,

avem:

6

Se numeşte p- graf , un graf orientat în care numărul

arcelor identice este mai mic sau egal cu o valoare dată

p.

În cele ce urmează vom analiza numai 1-grafuri fără

bucle.

d*(2) =3 → există trei arce care ies din nodul 2, şi

anume : u2=(2,1), u4=(2,3) şi u5 = (2,4).

d-(2) =1 → în nodul 2 intră un singur arc, în speţă arcul

u3=(3,2).

Se mai definesc următoarele mulţimi:

→ mulţimea nodurilor ce constituie

extremităţi finale ale arcelor care pleacă din nodul x. Pe

scurt, mulţimea succesorilor lui x;

→ mulţimea nodurilor ce constituie

extremităţi iniţiale ale arcelor care pleacă din nodul x.

Pe scurt, mulţimea predecesorilor lui x;

Exemplu:

În graful din figura 1, pentru nodul x=2, avem:

- Γ+(2) = {1,3,4} → urmare a faptului că muchiile care

pleacă din nodul 2 sunt (2,1), (2,3) şi (2,4), putem

spune că mulţimea succesorilor nodului 2 este {1,3,4}.

- Γ-(2) = {3} → în nodul 2 intră doar muchia (3,2), deci

mulţimea predecesorilor lui 2 conţine doar nodul 3.

ω+(x) = {u = (x,y)| u ε U} → mulţimea arcelor care ies

din nodul x;

ω-(x) = {u = (y,x)| u ε U} → mulţimea arcelor care intră

în nodul x;

Exemplu:

În graful din figura 1, pentru nodul 2, avem:

ω+(x) = {(2,1), (2,3), (2,4)}, ω-(x) = {(3,2)}

4. Graf parţial şi subgraf

7

Fie graful G = (X,U). Un graf parţial al lui G, este un graf

G1= (X,V), cu . Altfel spus, un graf parţial G1 al lui

G, este chiar G, sau se obţine din G păstrând toate

vârfurile şi suprimând nişte muchii.

Fie graful G = (X,U). Un graf parţial al lui G, este un graf

G1= (Y,T), unde şi , iar T va conţine numai

muchiile care au ambele extremităţi în Y. Altfel spus, un

graf parţial G1 al lui G, se obţine din G eliminând nişte

vârfuri şi păstrând doar acele muchii care au ambele

extremităţi în mulţimea vârfurilor rămase.

Exemplu:

Se consideră graful G = (X,U) din figura 2, în care X =

{1,2,3,4,5,6} şi U={u1, u2, u3, u4, u5, u6, u7}.

Construim graful parţial G1 = (X,V), unde X =

{1,2,3,4,5,6} şi V = { u2, u3, u4, u6, u7} (figura 3) din

graful G au fost eliminate arcele u1 şi u5.

Construim subgraful G2 = (Y,T), unde Y = {3,4,5,6} şi T

= {u4, u5, u6, u7} (figura 4) din graful G au fost

eliminate nodurile 1 şi 2 precum şi arcele u1, u2 şi u3

8

1 2

43

5

6

u2

u1u3

u4 u5

u7 u6

1 2

43

5

6

u2

u3

u4

u7 u6

43

5

6

u4 u5

u7 u6

Figura 2Figura 3

Figura 4

care au o extremitate în afara mulţimii nodurilor

rămase.

5. Reprezentarea grafurilor orientate

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.

6. 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:

coloana 1 2 3 4

A= 0 0 0 0 1

1 0 1 1 2

9

coloana 1 2 3 4

0 0 0 1 3

0 1 0 0 4

Aplicaţie:

a)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.

int citire_matrice() //citeşte matricea de adiacenţă a de

la tastatură

10

1

2 3

4

Figura 5

Aplicaţie:

b) 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.

11

int citire_matrice() //citeşte matricea de

adiacenţă a de la tastatură

{int i,j;

cout<<”Nr. Noduri”; cin>>n;

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

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

{cout<<”[“<<i<<”<<”<<j<<”]=”);

cin>>a[i][j];}}}

int afişare_matrice() //afişează matricea de

adiacenţă a

{int i,j;

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

{

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

Cout<<a[i][j]

cout<<endl;}}}

void cit_matr_fis() //citeşte numărul de noduri si

matricea de adiacenta a //din fişierul text cu

descriptorul f

Aplicaţie:

12

{int i,j;

char nume_fis;

{

Cout<<”Daţi numele fişierului “; cin>>nume_fis;

Cin>>i>>j;

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

{

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

Cin>>f;

}

end;

c)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].

do

cin>>x;cin>>y;

while (x>=1) || x(<=n)|| (y>=1) || (y<=n) || (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).

Void citire_graf()

{int i, j, k, x, y;

Cout<<”Nr. Arce:”;cin>>m;

Cout<<”nr.varfuri:”;cin>>n;

13

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

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

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

a[i,j]=0;

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

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

{

Cout<<’”Muchia “<<k<<”: “;

cin>>x;cin>>y;

while ((x>=1) || x(<=n)|| (y>=1) || (y<=n) || (x<>y))

{pentru fiecare pereche, marchează arcul in matricea

de adiacenta}

a[x][y]=1;

}

}

Aplicaţie:

d)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ţă:

A= 1 2 3 4

0 0 0 0 1

14

A=

1 2 3 4

1 0 1 1 2

0 0 0 1 3

0 1 0 0 4

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,

15

1

2 3

4

atunci incrementăm nr. În final funcţia va returna

ultima valoare a variabilei nr.

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

16

int d_plus(int x);

{returnează gradul exterior d* pentru un nod x; acesta

este numărul valorilor de 1 de pe linia x a matricei de

adiacenta}

{int nr,j;

Nr=0;

if (a[x,j] = =1) nr=nr + 1;

d_plus=nr;

}

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

7. Matricea vârfuri – arce

Este o matrice b cu n linii şi m coloane, în care fiecare

element b[i,j] este:

1, dacă nodul i este o extremitate iniţială a arcului uj;

-1, dacă nodul i este o extremitate finală a arcului uj;

0, dacă nodul i nu este o extremitate a arcului uj.

Exemplu:

17

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}

{Int nr, i;

nr=0;

Nr=0;

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

if (a[x,j] = =1) nr=nr- 1;

d_plus=nr;

}

Pentru graful de mai jos cu n=4 noduri şi m=5 arce,

matricea vârfuri – arce este:

1 0 0 0 0

-1 -1 -1 0 0

0 1 0 1 -1

0 0 1 -1 1

Pentru a exemplifica construcţia matricei, vom deduce

elementele liniei 3:

a[3,1]= 0 pentru că nodul 3 nu este o extremitate a

arcului u1. Analog, a[3,3]= 0 deoarece nodul 3 nu

este extremitate a arcului u3.

a[3,5]= -1 pentru că nodul 3 este o extremitate

finală a arcului u5.

a[3,2]= 1 şi a[3,4]= 1 întrucât nodul 3 este o

extremitate iniţială a arcului u2 respectiv u4.

Observaţii:

Pe fiecare coloană j (aferentă arcului uj), avem exact

două elemente nenule: un 1 (linia i pe care se află

2

3

1

4

u3u2

u1

u4

u5

Figura 6

18

reprezintă extremitatea iniţială a arcului uj) şi un -1

(linia i pe care se află reprezintă extremitatea finală a

arcului uj)

Numărul valorilor de 1 de pe linia i, reprezintă gradul

exterior al nodului i (numărul arcelor ce au ca

extremitate iniţială pe i), iar numărul valorilor de -1 de

pe linia i reprezintă gradul interior al nodului i (numărul

arcelor care au ca extremitate finală pe i).

8. Listele vecinilor

Pentru fiecare nod x se construiesc două liste ale

vecinilor săi:

L*(x) → lista vecinilor succesori; conţine nodurile ce sunt

extremităţi finale ale arcelor care ies din nodul x.

L-(x) → lista vecinilor predecesori; conţine nodurile ce

sunt extremităţi iniţiale ale arcelor care intră în nodul x.

Exemplu:

În graful din figura 6 de mai sus, pentru nodul x=4

avem:

arcele care ies din nodul 4 sunt (4,2) şi (4,3). În

consecinţă, lista vecinilor succesori L*(4) conţine

nodurile 2 şi 3;

în nodul 4 intră un singur arc, şi anume (3,4), motiv

pentru care lista vecinilor predecesori L-(4) conţine

doar nodul 3.

Prezentăm în continuare aceste liste ale vecinilor

pentru graful din figura 6.

19

9.

Reprezentarea grafului ca un vector de muchii

Fiecare arc al grafului poate fi privit ca o înregistrare cu

două componente, în speţă cele două noduri care

constituie extremităţile arcului:

nod_in -> nodul din care iese arcul (“nodul de

început” al arcului);

nod_sf -> nodul în care intră arcul (“nodul de

sfârşit” al arcului);

Putem defini tipul de date ARC, astfel:

Graful în ansamblul său, este o mulţime de arce, adică o

mulţime de elemente de tipul ARC. În consecinţă,

definim graful ca un “vector de arce”, adică un vector

de elemente de tipul ARC:

Numărul real de elemente este numărul de arce m.

Astfel, elementele efectiv folosite ale vectorului vor fi

v[1], v[2],..., v[m]. Fiecare element {1, 2, ..., m}) este

de tipul ARC şi reprezintă unv[i] (cu i arc al grafului,

având două componente:

v[i].nod_in şi v[i].nod_sf -> nodurile extremităţi ale

arcului.

10. Nodurile izolate într-un graf orientat

Se citesc de la tastatură m perechi de numere întregi

(x,y) reprezentând extremităţile arcelor unui graf

Nodul x L*(x) L-(x)

1 2 vidă

2 vidă 1,3,4

3 2,4 4

4 2,3 3

20

orientat cu n noduri şi m arce. Să se stabilească dacă în

graful astfel definit există noduri izolate (prin care să

nu treacă nici un arc).

Întreaga rezolvare este cuprinsă în procedura

{noduri_izolate;} fără parametri.

Mai întâi citim numărul de noduri n şi numărul de arce

m. Definim doi vectori:

dp va conţine gradele exterioare (d*) ale tuturor

nodurilor;

dm va conţine gradele interioare (d-) ale tuturor

nodurilor.

Astfel, dp[i] şi dm[i] vor fi gradul exterior respectiv

gradul interior al nodului i, pentru i=1, 2, ..., n.

Iniţializăm cu 0 toate gradele exterioare şi interioare

ale tuturor nodurilor: într-un ciclu cu i de la 1 la n,

facem atribuirile dp[i]:=0 şi dm[i]:=0

Pentru a citi cele m arce, parcurgem un ciclu k de la 1 la

m, şi la fiecare pas:

citim o pereche de numere întregi (x,y), cu validarea

valorilor introduse: repetă (reia) citirea lui x şi y, până

când ambele valori sunt >= 1 şi >= n. Fiecare pereche

va reprezenta care iese din nodul x şi intră în nodul y.

întrucât arcul (x,y) iese din nodul x şi intră în nodul y,

rezultă că:

gradul exterior al nodului x (numărul arcelor care ies

din nodul x) va creşte cu 1;

gradul interior al nodului y (numărul arcelor care intră

în nodul y) va creşte cu 1.

21

Deci se fac atribuirile dp[x]= dp[x]+1 şi dm[y]= dm[y]

+1.

Aşadar la citirea fiecărui arc am actualizat gradele

nodurilor – extremităţi ale sale. Astfel, după încheierea

citirii vectorii dp şi dm vor conţine gradele exterioare

respectiv interioare ale tuturor nodurilor.

Un nod x se numeşte izolat dacă prin el nu trece nici un

arc. Altfel spus, nu iese nici un arc din el şi nu intră nici

un arc în el, adică dp[x]=dm[x]=0. În continuare, vom

număra nodurile izolate în variabila nr, pe care o

iniţializăm cu 0. Parcurgem “în paralel” cei doi vectori

ai gradelor dp şi dm, într-un ciclu cu i=1, 2, 3, ..., n. La

fiecare pas, testăm dacă nodul i este izolat, adică dacă

dp[i]=0 şi dm[i]=0; în caz afirmativ afişăm respectivul

nod i şi incrementăm numărul nr al nodurilor izolate.

După încheierea acestei parcurgeri, dacă numărul

vârfurilor izolate este diferit de 0 atunci îl afişăm, iar în

caz contrar tipărim un mesaj din care să rezulte că

graful nu are noduri izolate.

22

nr=0;

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

if(dp[i]=0) || (dp[i]=0) then

{

Cout<<i<<” ”;

nr=nr+1;

}

23

Int Vect[20],n,m,a[20][20];

Int dp,dm;

Void noduri_izolate()

{int i,j,k,x,y,nr;

Cout<<”Nr.arce : “; cin>>m;

Cout<<”Nr.noduri : “; cin>>n;

{iniţializează cu 0 vectorii gradelor dp şi dm}

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

{

dp[i]=0; dm[i]=0;

}

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

for(k=1;k<=m;k++)

11. Celebritate

Se dă un grup format din n persoane, care se cunosc

sau nu între ele. De la tastatură se introduc m perechi

de numere întregi (x,y) cu semnificaţia ”persoana x

cunoaşte pe persoana y”. relaţia de cunoştinţă nu este

neapărat reciprocă. Numim celebritate, o persoană care

este cunoscută de către toate celelalte persoane din

grup, dar ea nu cunoaşte pe nici un alt membru al

grupului. Să se determine dacă din grup există o astfel

de celebritate.

24

{Cout<<”Arcul”<<k<<”: “;

do

cin>>x;cin>>y;

while (x>=1) || x(<=n)|| (y>=1) || (y<=n) || (x<>y);

{pentru fiecare arc (x,y), incrementează gradul exterior

al lui x şi gradul interior al lui y}

dp[x]=dp[x]+1; dm[y]=dm[y]+1;}

Cout<<endl;nr=0; {nr=numărul nodurilor izolate}

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

{dacă ambele grade ale lui i sunt 0,am găsit un vârf

izolat, pe care-l afişăm şi incrementăm nr}

if (dp[i]=0) || (dm[i]=0) then

{Cout<<”i”<<” ”; nr=nr+1;}

Cout<<endl;

if (nr!=0) cout<<”Graful are “<<nr<< “ noduri izolate”;

else cout<<”Graful nu are noduri izolate”;}

{noduri_izolate;}

12. Interpretarea datelor

Problema poate fi modelată într-un graf orientat, în

care nodurile sunt persoanele 1,2,3...n, iar arcele sunt

relaţiile de cunoştinţă între aceste persoane. O relaţie

de cunoştinţă este de forma (x,y) cu semnificaţia

“persoana x o cunoaşte pe persoana y”. De exemplu,

dacă grupul are n=4 persoane, iar cele m=5 “relaţii de

cunoştinţă” sunt (1,3), (2,3), (4,3), (1,2), (1,4), atunci

graful şi matricea sa de adiacenţă arată astfel:

Să analizăm persoana

reprezentată prin nodul 3:

există relaţiile de cunoştinţă (1,3), (2,3) şi (4,3), adică

persoana 3 este cunoscută de către 1,2 şi 4.

Mai exact, persoana 3 este cunoscută de către toate

celelalte persoane din grup;

nu există nici o relaţie de cunoştinţă de forma (3,p). Cu

alte cuvinte, persoana 3 nu cunoaşte pe nimeni.

În concluzie, persoana 3 este ceea ce numim

celebritate. În graf, existenţa celebrităţii se

interpretează astfel:

în nodul 3 intră arce “ieşite” din toate celelalte noduri;

din nodul 3 nu iese nici un arc.

25

3

1 4

2

Rezolvare

În procedura citire_graf 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 constituie

matricea de adiacenţă a, cu n linii * n coloane.

Algoritmul de căutare a celebrităţii cuprins în

procedura celebritate.

Pentru început, vom căuta o persoană pe care o vom

numi în continuare candidat la celebritate. Memorăm

acest candidat în variabila candid. Presupunem că

iniţial candidatul este persoana 1 (candid:=1).

“Cercetăm” celelalte persoane, într-un ciclu cu i de la 2

la n. Pentru fiecare persoană i, trebuie să facem o

testare. În cazul în care candidatul “actual” candid o

cunoaşte i (a[candid,i] este 1) candid nu mai poate fi

celebritate (celebritate nu trebuie să cunoască nici o

altă persoană din grup !). În această situaţie, noul

candidat la celebritate devine i (candid:=1).

La finele parcurgerii de mai sus, în variabila candid vom

avea aşadar un candidat la celebritate. Mai rămâne să

vedem dacă acest candidat este cunoscut de către

celelalte persoane.

În exemplul de mai sus, urmare a faptului că persoana

3 este celebritate, avem relaţiile (1,3), (2,3) şi (4,3),

adică a[1,3]=a[2,3]=a[4,3]=0. În consecinţă, pe coloana

3 avem n-1 valori de 1. Pe caz general, trebuie să

numărăm valorile de 1 de pe coloana candid în matricea

26

de adiacenţă, în adiacenţă, iar dacă găsim n-1 valori,

atunci persoana candid este într-adevăr celebritate.

27

Int n, m, a[20] [20] ;

void citire_graf()

{int i, j, k, x, y;

Cout<<”Nr.arce : “; cin>>m;

Cout<<”Nr.noduri : “; cin>>n;

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

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

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

a[i][j]=0;

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

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

{Cout<<”Arcul “<<k<<”:”);

13.

Drumuri si

circuite in

grafuri

orientate

Se numeşte

lanţ intr-un graf orientat, o mulţime de arce

L={u1,u2,...,uk}, cu proprietatea ca oricare doua arce

vecine in mulţime au o extremitate comuna.

28

do

cin>>x;cin>>y;

while (x>=1) || x(<=n)|| (y>=1) || (y<=n) || (x<>y);

{pentru fiecare pereche marchează arcul in

matricea de adiacenta}

a[x][y]=1;}}

Un lanţ este de fapt un traseu care uneşte prin arce

doua noduri numite extremităţile lanţului, fără a tine

cont de orientarea arcelor componente.

Se numeşte drum în graful G, un şir de noduri D={z1, z2,

z3, …, zk}, unde z1, z2, z3, …, zk aparţin lui x, cu

proprietatea că oricare două noduri consecutive sunt

adiacente, adică există arcele [z1, z2], [z2, z3], …, [zk-1,zk]

aparţin lui U.

Practic, un drum poate fi privit ca un traseu în care

toate arcele au aceeaşi orientare, dată de sensul de

29

Int celebritate;

Int i, j, candid, nr ;

{candid:=1; {candid va reprezenta candidatul la

celebritate, care iniţial este persoana 1}

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

{daca candidatul îl cunoaşte pe i, el nu mai poate fi

celebritate noul candidat devine i}

if (a[candid][ i]==1) candid=i;

nr=0; {numaram in nr cate persoane îl cunosc pe

candidatul candid}

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

if (a[i][candid]=1) nr=nr+1;

{verificam daca intr-adevăr candid este celebritate}

if (nr=n-1) cout<<”Persoana “<<candid<<” este

celebritate”;

else

cout<<”Nu exista celebritate in grup”;}

{citire_graf; celebritate;}

deplasare de la z1 la zk. Dacă nodurile z1, z2, z3, …, zk

sunt distincte două câte două, drumul se numeşte

elementar. În caz contrar, drumul este ne-elementar.

Asemenea uni lanţ într-un graf neorientat, un drum într-

un graf orientat este de fapt un traseu pe care l-am

parcurge între două noduri deplasându-ne de-a lungul

unor arce şi trecând prin nişte noduri intermediare.

Deosebirea unui drum faţă de un lanţ constă în faptul

că de-a lungul unui arc ne putem deplasa numai în

sensul dat de orientarea arcului.

Se numeşte circuit într-un graf, un lanţ L={z1, z2, z3, …,

zk} cu proprietatea că z1=zk şi arcele [z1, z2], [z2, z3], …,

[zk-1,zk] sunt distincte două câte două.

Dacă într-un circuit, toate nodurile cu excepţia primului

şi ultimului sunt distincte două câte două, atunci

circuitul se numeşte elementar. În caz contrar, el este

ne - elementar .

14. Matricea drumurilor

Este o matrice d cu n linii şi n coloane, în care fiecare

element d[i,j] este :

1 2

43

5

6

u2

u1u3

u4 u5

u7 u6

Figura 8

30

1, dacă există drum de la nodul i la nodul j în graf;

0, în caz contrar.

15. Algoritmul Roy-Warshall de determinare a

matricei drumurilor

Matricea drumurilor se obţine aplicând matricei de

adiacenţă transformări succesive. Vom spune că există

drum de la nodul i la nodul j, dacă găsim un nod k

(diferit de i, j) cu proprietatea că există drum de la i la k

şi drum de la j la k. Astfel:

un element a[i, j] care este 0, devine 1, dacă există un

nod k astfel încât a[i, k]=1 şi a[k, j]=1.

Pentru a găsi arcele nodului k, trebuie parcurse pe rând

în varianta k toate nodurile 1, 2, …, n.

Atribuirea a[i][ j]=a[i][k]*a[k][ j] este o scriere elegantă

a regulii de mai sus:

în cazul în care unul din elementele a[i][k], a[k][ j] este

0, a[i][ j] va rămâne 0;

dacă a[i, k]=1 şi a [k, j]=1, atunci a[i, j] devine 1.

31

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

for(i=1;i<=n;i++) {i≠k}

for(j=1;j<=n;j++){j≠k}

if (a[i][ j]=0) || (i<>k) || (j<>k) a[i]

[j]=a[i][k]*a[k][ j];

Problema rezolvata : Un CD valoros

Într-un grup sunt n elevi, băieţi şi fete, pe care-i

numerotăm 1, 2, … , n. Fiecare elev cunoaşte o parte

dintre ceilalţi elevi. Relaţia de cunoştinţă nu este

neapărat reciprocă (dacă x îl cunoaşte pe y, asta nu

înseamnă că şi y trebuie să îl cunoască pe x).

Unul dintre elevi are un CD foarte valoros, cu multe

jocuri demonstrative, pe care toţi membri grupului vor

să-l aibă fie şi pentru scurt timp, pentru a şi-l copia pe

calculatorul propriu.

CD-ul circulă printre membrii grupului în felul următor:

fiecare elev după ce l-a primit de la altcineva îl dă mai

departe, dar numai unui elev pe care îl cunoaşte, pentru

că nu doreşte să ajungă în mâna unor persoane în care

nu poate avea încredere. Determinaţi o modalitate

(dacă există) prin care CD-ul să circule exact o singură

dată pe la fiecare elev, transmiterea lui făcându-se

numai către o cunoştinţă, iar în final CD-ul să ajungă din

nou la proprietarul său.

Interpretarea datelor

Relaţiile de cunoştinţă din cadrul grupului pot fi

reţinute într-o matrice a cu n linii şi n coloane, în fiecare

element a[i, j] este: 1 dacă elevul i îl cunoaşte pe elevul

j, respectiv 0 în caz contrar.

Cu datele problemei putem construi un graf în care

nodurile sunt elevii 1, 2, 3,…, n, iar arcele sunt relaţiile

de cunoştinţă din grup. Astfel, va exista arc de la nodul

32

x la nodul y dacă elevul x în cunoaşte pe elevul y.

Întrucât în enunţ se precizează că relaţiile de cunoştinţă

nu sunt neapărat reciproce („x cunoaşte pe y” nu

implică „y cunoaşte pe x”), rezultă că avem de-a face cu

un graf orientat. Matricea a definită mai înainte este

tocmai matricea de adiacenţă a grafului.

"Traseul" pe care îl parcurge CD-ul pleacă dintr-un nod

(proprietarul său), trecând prin fiecare nod (pe la

fiecare elev) o singură dată. Transmiterea se face numai

către o cunoştinţă. Astfel, de la elevul x va ajunge la

elevul y numai dacă există arc (cunoştinţă) de la x la y.

În final, traseul se încheie în nodul de unde a plecat

(CD-ul se întoarce la proprietarul iniţial). Un traseu care

respectă condiţiile de mai sus nu este altceva decât un

circuit elementar care trece prin toate nodurile grafului:

drum deoarece poate trece de la un nod la altul numai

printr-un arc, elementar deoarece nu trece de două ori

prin acelaşi nod, şi în sfârşit circuit pentru că revine în

nodul de plecare.

Rezolvare :

Folosim metoda backtracking. Fiecare astfel de circuit

elementar care trece prin toate nodurile grafului, va fi o

soluţie memorată în vectorul stivă st. Aşadar

elementele vectorului st sunt noduri ale grafului.

O soluţie (st[1], st[2], …, st[p] ) este finală dacă

33

conţine n nivele, adică p=n (au fost „puşi pe stivă”

toţi cei n elevi, adică toate cele n noduri)

st[n]=x (pentru a fi ciclu trebui să revină în nodul

de plecare, adică „elevul de pe ultimul nivel”, st[n],

trebuie să fie proprietarul memorat iniţial în x).

Procedura {citire_matrice;} citeşte matricea de

adiacenţă (relaţiile de cunoştinţă). În două cicluri for, cu

i, j=1, 2, …, n, se citesc toate elementele a[i, j]. Această

procedură a fost prezentată ca aplicaţie în lecţia

„Reprezentarea grafurilor orientate”

Procedura {iniţializări;} realizează iniţializarea stivei şi

a proprietarului CD-ului.

într-un ciclu for, se iniţializează cu 0 întreg vectorul-

stivă;

se citeşte numărul de ordine al proprietarului CD-ului în

variabila x (nodul de plecare).

Procedura {tipar(p:integer):} afişează o configuraţie

(st[1], st[2], …, st[p]) a vectorului-stivă.

Funcţia {valid(p:integer):boolean;} verifică pentru

fiecare nivel p dacă st[p]I a generat o soluţie (st[1],

st[2], …, st[p]) validă.

Testarea se face prin intermediul unei variabile

booleene ok, iniţializează cu TRUE. În primul rând, din

nodul st[p-1] se poate ajunge în nodul st[p] numai

printr-un arc (orice drum/circuit trece prin arce). Aşadar

nodul st[p] este valid numai dacă există arc de la st[p-

1] la st[p], adică a[st[p-1], st[p]]=1 (această condiţie

provine din faptul că fiecare elev va transmite CD-ul

numai prin cunoştinţă, ia relaţia de cunoştinţă este

34

marcată în graf printr-un arc). În caz contrar ok devine

FALSE.

Dacă ok a rămas TRUE, urmează testarea celei de-a

doua condiţii. Am spus că soluţia este finală dacă p=n,

iar pe ultimul nivel trebuie să se găsească nodul x. Dar

pe ultimul nivel anterior lui n nu putem avea nodul x

(CD-ul revine la proprietar, dar numai după ce a trecut

pe la ceilalţi elevi, pe la fiecare o singură dată).

Dacă ok a rămas în continuare TRUE, mai avem şi o a

treia condiţie. Nodul st[p] să nu se mai găsească pe

stivă (urmare a faptului că CD-ul trebuie să treacă pe la

fiecare elev o singură dată).

Parcurgem într-un ciclu nivelele i=1, 2, …, p-1

anterioare lui p. Dacă găsim un st[i] egal cu st[p],

înseamnă că st[p] se mai găsesc pe un nivel anterior,

deci ok devine şi în cazul acesta FALSE.

Procedura recursivă {bktr(p:integer);} “tratează” un

nivel oarecare p al stivei. Prin variabila val vor trece pe

rând, într-un ciclu, toate valorile care teoretic ar putea

fi puse pe nivelul p. Pentru fiecare dintre aceste valori:

- dacă respectiva valoare a generat o soluţie validă

(dacă funcţia valid(p) a returnat TRUE), atunci:

35

if (ok)

if ((p<n) &(st[p]==x))

ok=0 (FALSE)

- dacă soluţia respectivă e şi finală o tipărim (apelând

procedura tipar (p)); în caz contrar trecem la nivelul

următor (pentru a completa soluţia cu un nou nivel),

prin auto-apelul bktr(p+1).

În programul principal, apelăm procedurile iniţializări şi

citire_matrice, apoi declanşăm lanţul recursiv prin

apelul bktr(1) (plecăm de la nivelul 1 al stivei).

int n,xr;

int st[20],a [20][20];

procedure citire_matrice;

{citeste matricea de adiacenta a de la tastatura}

{var I,j:integer;

Cout<< “numarul de noduri: “; cin>>n;

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

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

{write (‘[‘, i, ’,’, j, ‘]=’); cin>>(a[i, j]);}}

void initializari()

{initializeaza stiva si citeste datele problemei}

Int i;

{cout<<”‘Cine este proprietarul: “; cin>>x;

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

st();}

Int tipar (int p);

{tipareste o solutie memorata in vectorul st}

{Int k;

Cout<<x<<””;

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

36

do cout<<st[k] ;

cout<<endl;

function valid(int p)

{testeaza daca valoarea pusa pe nivelul p a generat o

solutie valida, returnand TRUE sau FALSE}

Int nr, i, ok;

{{CD-ul poate circula numai intre elevii care se cunosc,

deci elevul st[p-1] trebuie sa il cunoasca pe st[p] pentru

a-i putea da CD-ul mai departe}

ok=1;(TRUE)

if (a[st[p-1], st[p]]==0) then ok=0;

if (ok)

{proprietarul x nu se poate gasi pe un nivel anterior

ultimului}

if (p<n) and (st[p]==x) then ok=0;

if (ok)

{elevul st[p] nu trebuie sa se mai gaseasca pe nivelele

anterioare}

for (i=1;i<=p-1;i++)

if (st[p]==st[i]) ok=0;

valid=ok;

end;

void bktr (int p)

{implementeaza algoritmul de backtracking recursiv}

Int val;

{{in variabila val trec pe rand toate valorile care ar

putea fi incercate pe nivelul p al stivei}

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

{st[p]=val; {pune o noua valoare pe nivelul p}

37

if valid(p) {daca solutia obtinuta e valida}

{o solutie e finala daca CD-ul a trecut pe la n elevi

(p=n) si ultimul e proprietarul (st[p]=x)}

if ((p=n) ||(st[n]==x)) tipar (p) {daca e si finala,

tipareste solutia}

else bktr (p+1); {trece la nivelul urmator in stiva,

pentru a completa solutia}}}

{citire_matrice; bktr(1); {plecam de la nivelul 1 pe

stiva}}

Informatica - profil matematica-informatica Lucrarea studiaza limbajul C++ si se adreseaza elevilor din clasele IX-X care au studiat limbajele C si Pascal Cornelia Ivasc, Mona Carmen-Pruna, Luminita-Mihaela Condurache, Doina Logofatu-Hrinciuc Editura Petrion

Informatica - Manual pentru clasa a XI-aAutor : Mariana Milosescu

Limbajul C/C++ - teorie si aplicatii (clasa a XI-a) Autor : Cristian Udrea

38