Date post: | 16-Jan-2016 |
Category: |
Documents |
Upload: | lepadatu-alexandru |
View: | 34 times |
Download: | 3 times |
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