ALGORITMI FUNDAMENTALI PE GRAFURI. DETERMINAREA DRUMURILOR ȘI DISTANȚELOR OPTIME COORDONATOR ȘTIINȚIFIC, ABSOLVENT, Conf. univ. dr. Cristina FLAUT… [628890]

Ministerul Educației Naționale
Universitatea OVIDIUS Constanța
Facultatea de Matematică și Informatică
Specializarea Informatică

Lucrare de Licență

ALGORITMI FUNDAMENTALI PE GRAFURI. DETERMINAREA
DRUMURILOR ȘI DISTANȚELOR OPTIME

COORDONATOR ȘTIINȚIFIC, ABSOLVENT: [anonimizat]. univ. dr. Cristina FLAUT SITĂ ANDREI

CONSTANȚA, 2020

CUPRINS

I. INTRODUCERE… 1

II. SCURT ISTORIC AL TEORIEI GRAFURILOR … 2

III. NOȚIUNI PRELIMINARII
III.1. DEFINIȚII ALE GRAFURILOR … 4
III.2. REPREZENTĂRI ALE GRAFURILOR … 5
III.3. PARCURGEREA GRAFURILOR … 13

IV. DRUMURI OPTIME. ALGORITMI DE DETERMINARE A
DRUMURILOR OPTIME
IV.1. DRUMURI OPTIME … 24
IV.2. ALGORITM DE DETERMINARE A VALORILOR
MINIME DE DRUMURI DE LA UN VÂRF DAT … 25
IV.3. ALGORITM DE DETERMINARE A VALORILOR MAXIME
DE DRUMURI DE LA UN VÂRF DAT … 35

V. INSTRUCȚIUNI SAGE PENTRU REPREZENTAREA GRAFURILOR …
42

VI. CONCLUZII … 45
VII. BIBLIOGRAFIE … 47

I. INTRODUCERE

În cadrul lucrării mele de licență, mi -am propus să
discut despre grafuri deoarece unul dintre hobby -urile
mele este călătoria, iar grafurile reprezintă o modalitate
practică de reprezentare a mai multor localități , în
cadrul cărora doresc să determin distanțele optime
dintre acestea.
Tematica lucrării de licență se referă la algoritmii
fundamentali pe grafuri respectiv determinarea
drumurilo r și distanțelor optime, iar în structura lucrării
vor fi cuprinse figuri, tabele, calcule și fragmente de
cod referitoare la fiecare problemă abordată.
În primul capitol voi face un scurt istoric al teoriei
grafurilor în care voi evidenția repere istorice cu privire
la descoperirea problemelor fundamentale .
Al doilea capitol va cuprinde definițiile, parcurgerile
și reprezentările grafurilor . În al treilea capitol voi vorbi
despre drumurile optime și voi aborda cei mai
importanți algoritmi de determinare a acestora, atât de
valoare minimă, cât și de valoare maximă, aceștia fiind ,
în opinia mea, Bellman -Kalaba (pentru drumuri
minime) și Roy -Floyd (pentru drumuri maxime), iar la
final voi încheia cu concluzii exprimate pe marginea
rezultatelor finale și a rolurilor grafurilor din viața reală.
1

II. SCURT ISTORIC AL TEORIEI GRAFURILOR

Originile teoriei grafurilor se găsesc în rezolvarea unor
probleme de jocuri matematice, care au atras atenția unor
matematicieni de seamă cum ar fi : Euler, Hamilton,
Sylvester, Birkhoff, Cayley.
Data nașterii teoriei grafurilor este considerată a fi anul
1736, când matematicianul Leonard Euler a publicat un
articol în care a clarificat problema celor 7 poduri de la
Königsberg și a prezentat o metodă pentru rezolvarea altor
probleme de același tip. Articolul, în limba latină, avea
titlul : Solutio problematis ad geometriam situs pertinentis
(Solu ția unei probleme legate de geometria poziției) și a
apărut în revista Commentarii Scietiarum Imperials
Petropolitanae.
Un alt matematician care s -a ocupat de aceleași probleme
ca și Euler (se pare fără cunoașterea articolului acestuia),
dar care și -a publicat rezultatele cercetărilor sale în anul
1873, a fost Carl Hierholzer. Acesta a demonstrat în plus
unele rezultate c are lui Euler i se păreau evidente.
În anul 1851 articolul lui Euler a fost tradus și publicat în
revista Nouvelles Annales de Mathematiques, iar rezultatele
sale au fost îmbogățite, fiind studiate în clase speciale de
grafuri.
Alte izvoare ale te oriei grafurilor sunt studiul rețelelor
electrice, problema celor patru culori, aplicațiile, teoriei
2

grafurilor în chimie (inițiate de Cayley), probleme
hamiltoniene, grafuri planare, etc.
Termenul de graf a fost folosit pentru prima dată în sensul
său actual (derivat din termenul “nota ție grafică ” din
chimie) într -un articol ce a apărut în primul număr al
revistei American Journal of Matemathics. Teoria
grafurilor are numeroase aplicații în chimie, cercetări
privind determinarea numărului de izomeri ai compușilor
organici contribuind în mare măsură la rezolvarea
problemelor de numărare a grafurilor aparținând unor clase
speciale.
Teoria grafurilor, printre altele, ne ajută să alegem un
traseu optim dintr -o mulțime de variante posibile. Pentru
realizarea unui obiectiv în timp scurt, aceasta ne ajută să
determinăm momentele de abordare a activităților de
realizat (ordonanțare).
Pentru stabilirea unor programe de transport optime, teoria
grafurilor ne furnizează algoritmi performanți. În teoria
astfel dezvoltată graful este un obiect abstract, dar ale cărui
elemente sunt asignate unor realități concrete. Recurgerea
la aceste modele fiind utilă datorită algoritmilor cu care se
pot rezolva d iferitele probleme concrete.
Dintre cercetătorii care s -au ocupat de teoria
grafurilor în ultimele decenii, îi aminitim pe C.Berge,
S.Cataranciuc, V.Cepoi, C.Croitoru, L.R.Ford, M.
Gondran, W.T.Tutte, H. -J. Voss și T.Zamfirescu.

3

III. NOȚIUNI PRELIMINARII (DEFINIȚII,
REPREZENTĂRI, PARCURGERI ALE GRAFURILOR)

III.1. DEFINIȚII ALE GRAFURILOR

Se numește multigraf orientat orice sistem de forma (X,U), notat cu G, în
care X este o mulțime de elemente oarecare, iar U ⊂ X x X x N. Elementele
mulțimii X se numesc vârfuri, iar cele ale U arce ale multigrafului. În unele
lucrări G este notat cu (V, E) de la cuvintele englezești vertex (vârf) și edge
(arc).
Dacă mulțimile X și U sunt finite, atunci G se numește finit ș i în acest caz
cardinalul mulțimii X, notat cu n = |X|, se numește ordinul multigrafului.
Cardinalul mulțimii U se notează cu m și se numește dimensiunea multigrafului
G. Vo i considera numai multigrafuri finite. Dacă extremitățile unui arc coincid,
atunci arcul se numește buclă.

Exemplu :

1 2
5 6 3
7 4
8 FIG.1

4

Multigraful reprezentat în Fig.1 are : ca mul țime de
vârfuri pe X = {1, 2, 3, 4, 5, 6, 7, 8} și ca mulțime de
arce pe U = {(1,2,1) ; (2,3,1) ; (2,3,2) ; (3,4,1) ; (4,8,1) ;
(8,7,1) ; (7,6,1) ; (6,5,1) ; (5,1,1)}.

III.2. REPREZENTĂRI ALE GRAFURILOR

Fie graful G=(X,U). Deoarece între mulțimea U cu n
elemente și mulțimea {1,2,..,n} există o bijecție, p ot
presupune, fără a restrânge generalitatea, că U =
{1,2,.. ,n}. În cadrul algoritmilor de prelucrare a
grafurilor, acestea pot fi reprezentate prin matr icea de
adiacență.
Matricea de adiacență asociată unui graf G cu n vârfuri
este o matrice pătratică de ordinul n, A = (𝑎𝑖𝑗)𝑛𝑋𝑛 ,
unde 𝑎𝑖𝑗= {

Exemplul 1. Se dă următorul graf neorientat, cu n=5

1, dac ă (i,j) ∈ U
0, dacă (i,j) ∉ U
2 1
4 3
5
5

Matricea de adiacență a grafului este
A =
0 0 1 1 0
0 0 1 1 0
1 0 0 0 1
1 0 1 0 1
0 0 1 1 0

Exemplul 2. Se dă un graf orientat, cu n=5

Matricea de adiacență a acestui graf este

A =
0 0 0 1 0
0 0 0 0 0
1 0 0 1 1
0 0 0 0 1
0 0 0 0 0
2 1
4 3
5
6

Matricea de adiacență a unui graf neorientat este una
simetrică, iar cea asociată unui graf orientat nu este
neapărat simetrică.
În matricea de adiacență asociată unui graf neorientat,
suma elementelor liniei i (care este identică cu suma
elementelor coloanei i) reprezintă gradul vârfului i
oricare ar fi i de la 1 la n.
Se numește matrice a drumurilor asociată
grafului orienta t G=(X,U), cu U={ 𝑋1,𝑋2,…, 𝑋7}
matricea M= (𝑚𝑖𝑗)𝑛𝑋𝑛 dată prin
𝑚𝑖𝑗= {

Exemplu, pentru graficul orientat de mai sus, matricea
drumurilor este:

A =
0 0 0 1 1
0 0 0 0 0
1 0 0 1 1
0 0 0 0 1
0 0 0 0 0
1, dac ă există drum în G de la 𝑢𝑖 la 𝑢𝑗
0, în caz contrar
7

Cel mai cunoscut algoritm pentru
determinarea matricei drumurilor unui graf
este cel al lui Roy -Warshall. Algoritmul
construiește matricea drumurilor pornind de la
cea de adiacență a grafului iar pseudocodul
acestuia este:

Pentru k:=1,n execută
Pentru i :=1,n (i ≠k) execută
Pentru j :1,n (j ≠k) execută
Dacă a [i,j]=0 atunci
a[i,j]=min(a[i,k],a[k,j])
Sfârșit dacă
Sfârșit pentru
Sfârșit pentru
Sfârșit pentru
8

Aplic algoritmul lui Roy – Warshall
pentru găsirea matricei drumurilor
asociată grafului de mai jos :

1 3
2 4 5
6
7
9

Dacă aplicăm matricei M transformările 𝑇1,𝑇2,…, 𝑇7 se
obține matricea drumurilor M*, unde

M= M*=

Deoarece M* conține 1 pe diagonala principală, rezultă
că toate vârfurile grafului aparțin unor cirucite. Dacă
notez cu S( 𝑋𝑖) mulțimea vârfurilor care sunt extremități
terminale ale unor drumuri care pleacă din 𝑋𝑖 și cu P (𝑋𝑖)
mulțimea vârfurilor care sunt extremități inițiale ale
unor drumuri care se termină în 𝑋𝑖, componenta tare
conexă care conține vârful 𝑋𝑖 va fi tocmai mulțimea
S(𝑋𝑖) ∩ P(𝑋𝑖), la care se adaugă vârful 𝑋𝑖.

Dar S( 𝑋𝑖) și P( 𝑋𝑖) se citesc ușor din matricea M* – S(𝑋𝑖) este
compusă din vârfurile 𝑋𝑗 pentru care j verifică 𝑎𝑖𝑗*=1, deci
corespund coloanelor care conține câte un 1 în linia i, iar P(𝑋𝑖) 1 1 1 0 0 0 0
1 1 1 0 0 0 0
1 1 1 0 0 0 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 1 0 0 0 0
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 1 1 0 0 1 1
0 0 1 1 0 0 0
0 0 0 0 1 0 0
0 1 0 0 0 1 0
10

este compusă din acele vârfuri 𝑋𝑗 pentru care 𝑎𝑗𝑖*=1,
deci care corespund liniilor care conțin un 1 în coloana
i.
De aici rezultă un algoritm pentru găsirea
componentelor tare conexe ale unui graf pornind de la
M*. Pentru graful de mai sus elementele 1 din linia și
coloana 1 a lui M* determină mulțimile
S(𝑋𝑖)={ 𝑋1,𝑋2,𝑋3 } ;
P(𝑋𝑖)={ 𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6,𝑋7 }
Deoarece S(𝑋𝑖) ∩ P( 𝑋𝑖) = S(𝑋1) avem componenta tare
conexă care conține vârful 𝑋𝑖 și este 𝐶1= {𝑋1,𝑋2,𝑋3 }
Să consider acum unul din vârfurile rămase, 𝑋4 de
exemplu. Elementele 1 din linia și coloana 4 a lui M*
duc la
S(𝑋4)={ 𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6,𝑋7 } ;
P(𝑋4)={ 𝑋4,𝑋5,𝑋6,𝑋7 }
Deci S(𝑋4) ∩ P( 𝑋4) = { 𝑋4,𝑋5,𝑋6,𝑋7 }
Componenta tare conexă a grafului care conține x4 este
𝐶4={𝑋4,𝑋5,𝑋6,𝑋7}.
Deoarece graful nu mai are alte vârfuri care aparțin lui
𝐶1 sau 𝐶2, rezultă că am găsit toate componentele tare
conexe ale grafului.
11

În continuare, prezint un fragment din program de
determinare a matricei drumurilor unui graf orientat G=(X,U)
cu U={1,2,..,n}.

void main(void)
{
int i,j,k;
citeste();
printf(" \nMatricea de adiacenta: \n");
afiseaza();
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(!a[i][j]) a[i][j]=a[i][k]*a[k][j];
printf("Matricea drumurilor: \n");
afiseaza();
}
void citeste(void)
{
int m,i,j,x,y;
FILE *f;
f=fopen("date.txt","r");
fscanf(f, "%d", &n);
fscanf(f, "%d", &m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) a[i][j]=0;
12

for(i=1;i<=m;i++)
{
fscanf(f, "%d %d", &x, &y);
a[x][y]=1;
}
fclose(f);
}
void afiseaza(void)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d",a[i][j]);
printf(" \n");
}
}

III.3. PARCURGEREA GRAFURILOR

Fiind dat un graf G, orientat sau nu, se pune problema
de a vizita/parcurge toate vârfurile grafului. Această
vizitare se poate face în diferite moduri. Dintre aceste
modalități, cele mai cunoscute sunt parcurgerea în
lățime (bradth first) și cea în adâncime (depth first).
13

Există o relativă asemănare între parcurgerile
vârfurilor unui graf cu parcurgerea elementelor
unei matrice. Cea di n urmă se poate face “pe linii”
sau “pe coloane”, fiind de precizat ordinea de
selectare a liniilor și coloanelor.
Teorema parcurgerii în lățime se referă la faptul
că “se vizitează vârful de pornire, apoi toți
succesorii acestuia, vecinii nevizitați a i acestora și
așa mai departe până când se vizitează toate
vârfurile grafului ”.

Exemplu:

FIG.2 1
2 3
5
7 4
8 6
14

Pentru graful din figura 2, ordinea de parcurgere a nodurilor
cu metoda BF, când se pleacă din vârful 1, este următoarea :
1, 2, 3, 4, 5, 6, 7, 8.
De observat că ordinea parcurgerii vârfurilor adiacente unui
nod la un moment dat nu este prestabilită. În exemplul dat am
considerat această ordine ca fiind cea crescătoare a numărului
de nod (de exemplu pentru vârful 1 am parcurs vârfurile
adiacente cu el în ordinea 2,3,4 și nu 3,2,4 sau altfel).

Pentru marcarea vârfurilor deja vizitate la un moment dat, vo i
folosi un vector VIZ cu n componente, astfel :

VIZ[j]= {
Pentru oricare j de la 1 la n.
Nodurile ale căror vecini nevizitați urmează să fie prelucrați
într-o coadă C.

Algoritmul în pseudocod este următorul:

Pas 1 . Pentru j:=1,n execută VIZ[j]:=0 { toate vârfurile se
consideră nevizitate }
Pas 2 . Adaugă (C,i) {adaug ă vârful la coada j } 1, dac ă vârful j a fost vizitat
0, în caz contrar
15

Vizitează vârful i
VIZ[i]:=1 {se vizitează vârful i și se marchează ca atare}

Pas 3 . Cât timp not CoadaVidă(C) execută {coada este
nevidă}
Pas 3.1 . Accesează (C,v) {reține în v vârful din capul cozii}
Elimină (C) {elimină elementul din capul cozii}
Pas 3.2 . Pentru toți vecinii j, ai lui v, nevizitați încă,
execută
Adaugă (C,j) {adaugă vârful j în coadă}
Vizitează vârful j;
VIZ[j]:=1 { marchează vârful j ca fiind vizitat }

Pas 4 . Stop .

Iar acum prezint un fragment dintr -un program de parcurgere
prin metoda BF a unui graf neorientat reprezentat prin
matricea de adiacență, în C++, coada C fiind implementată
sub forma unui vector.

void citeste(void);
void bf(int);
void main(void)
{
16

int i,x0;
citeste();
for(i=1;i<=n;i++) viz[i]=0;
printf(" \nDati varful de plecare:");
scanf("%d", &x0);
printf("Parcurgerea BF:");
bf(x0);
}
void citeste(void)
{
int m,i,j,x,y;
FILE *f;
f=fopen("date.txt", "r");
fscanf(f,"%d", &n);
fscanf(f,"%d", &m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
for(i=1;i<=m;i++)
{
fscanf(f, "%d %d", &x,&y);
a[x][y]=a[y][x]=1;
17

}
fclose(f);
}
void bf(int x0)
{
int c[NMAX], p, u, v, j;
p=u=1;
c[1]=x0;
printf("%d", x0);
viz[x0]=1;
while(p<=u)
{
v=c[p];
p++;
for(j=1;j<=n;j++)
if((a[v][j]) && (!viz[j]))
{
c[++u]=j; printf("%d", j);
viz[j]=1;
}
}
}
18

Ordinul de complexitate al acestui algoritm este O( 𝑛2).

Parcugerea în adâncime DF constă în:
“Se vizitează vârful de pornire, apoi se repetă vizitarea
unui succesor nevizitat a ultimului vârf nevizitat până când nu
mai există succesori nevizitați pentru ultimul vârf vizitat, apoi
se revine la predecesorul ultimului vârf vizitat ( se consideră
că ultimul vârf vizitat ca fiind predecesorul care a condus la
vizitarea ultimului vârf vizitat. Procesul de schimbare a
ultimului vârf vizitat con tinuă până când se ajunge la vârful
de pornire și acesta nu are succesori nevizitați .”
Exemplu:
Pentru graful din figura 2, ordinea parcurgerii DF a
nodurilor, plecând din vârful 1, este : 1,2,5,3,7,6,4,8. Ca și în
cazul metodei BF, ordinea în care aleg dintre vârfurile
adiacente și nevizitate pentru un anumit nod, pe cel ce
urmează a fi parcurs, nu este una prestabilită. În exemplul dat
am considerat această ordine ca fiind cea crescătoare a
indicelui de nod, de aceea am ales să “cobo r” din vârful 1 pri n
vârful 2 când la fel de bine se putea “cobor î” prin vârful 3 sau
4.
O descriere a algoritmului de parcurgere în adâncime a unui
graf este:
Vizitează vârful de pornire,
Repetă
Cât timp
19

Există succesor nevizitat al ultimului vârf vizitează -l,
Sfârșit cât timp;
Revenire la predecesorul vârfului ce nu mai are succesori
nevizitați;
Până când vârful de pornire nu mai are succesori nevizitați.

Pentru implementarea algoritmului DF vom utiliza vectorul
VIZ cu aceeași semnificație ca la algoritmul BF, o stivă S
pentru memorarea vârfurilor ce urmează a fi prelucrate la un
moment dat și un vector URM cu n componente care reține
pentru fiecare vârf j ce urmaș al nodului j am parcurs ultima
oară.
Pentru determinarea următorului nod neparcurs, adiacent cu
j, prin care p ot continua “coborîrea” în graf, parcurg linia j din
matricea de adiacență a grafului începând din coloana
urm[j]+1 până este găsit un vecin al lui j nevizitat încă.
Iată și algorit mul în pseudocod :
Pas 1 . Pentru j:=1,n execut ă
VIZ[j]:=0 {toate vârfurile se consideră
nevizitate}
URM[j]:=0 {inițial nu a fost parcurs
urmașul nici unui nod}

Pas 2 . Adaugă (S,i) {plasează vârful de pornire în stivă}
Vizitează vârful I
VIZ[I]=1 {marchează vârful I ca fiind vizitat}
20

Pas 3. Cât timp not StivVidă(S) execută
Pas 3.1 . Accesează (S,j) {reține în j elementul din
vârful stivei S}
Pas 3.2 . determină următorul vecin k al lui j nevizitat
încă – URM[j]:=k
Pas 3.3 . Dacă există un asemenea k atunci
Vizitează vârful k
VIZ[k]:=1
Adaugă(S,k) {adaugă vârful k în stiva s}
altfel
Elimină (S) { elimină elementul din vârful stivei
S}

Pas 4. Stop .

Iar fragmentul de cod C++ este :

void citeste(void);
void df(int);
void main(void)
{
int i,x0;
citeste();
for(i=1;i<=n;i++) viz[i]=0;
21

printf("dati varful de plecare: ");
scanf("%d", &x0);
printf("Parcurgerea DF: ");
df(x0);
}
void citeste(void)
{
int m,i,j,x,y;
FILE *f;
f=fopen("date.txt", "r");
fscanf(f,"%d", &n);
fscanf(f,"%d", &m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
for(i=1;i<=m;i++)
{
fscanf(f, "%d %d", &x,&y);
a[x][y]=a[y][x]=1;
}
fclose(f);
}
void df(int x0)
{
22

int p,j,k,s[NMAX], urm[NMAX];
for(j=1;j<=n;j++) urm[j]=0;
p=1;
s[1]=x0;
printf("%d",x0);
viz[x0]=1;
while(p>=1)
{
j=s[p];
for(k=urm[j]+1; (k<=n)&& (!a[j][k] || (a[j][k] && viz[k])); k++)
urm[j]=k;
if(k<=n)
{
printf("%d", k);
viz[k]=1;
s[++p]=k;
}
else p –;
}
}

23

IV. DRUMURI OPTIME. ALGORITMI DE DETERMINARE
A DISTANȚELOR ȘI DRUMURILOR OPTIME

IV.1. DRUMURI OPTIME
Algoritmii de rezolvare a acestor probleme se
pot baza pe unele proprietăți ale arcelor și/sau ale
grafurilor, precum pozitivitatea valorilor arcelor,
l(u)=1, pentru u ∈ U, graful este fără circuite. Dacă
l(u)=1 algoritmii vor determina lungimile
minime(ma xime) ale drumurilor.

Pentru a da condițiile de existență a valorii
minime a drumurilor de la un vârf i la un vârf j, să
consider că între aceste două drumuri există cel
puțin un drum μ care conține un circuit ω. Situația
este prezentată în figura de mai jos, în care s -au
prezentat doar segmentele drumului.

i k
j
ω
24

Notez cu μ’ drumul de la i la j care nu conține circuitul ω.
Deci are loc l( μ)=l(μ’) + l( ω).
Dacă l( ω) < 0 atunci nu există valoare minimă a
drumurilor de la i la j deoarece circuitul ω se poate parcurge
de oricâte ori și valoarea acestor drumuri tinde la – ∞.
Dacă l( ω) >= 0 atunci l( μ’) < l(μ) și deci în căutarea valorii
minime mă pot restrânge la mulțimea drumurilor elementare
de la i la j. Deci se poate considera că grafurile sunt simple și
nu conțin circuite de valoare negativă, când se caută valoarea
maximă a drumurilor. Deoarece într -un graf finit, mulțimea
drumurilor elementare e ste finită, rezultă că problema
determinării valorii minime a drumurilor în condițiile
precizate are soluție.

IV.2. ALGORITM DE DETERMINARE A VALORILOR
MINIME DE DRUMURI DE LA UN VÂRF DAT

Algoritimul Bellman – Kala ba
Acest algoritm se bazează pe principiul optimalității
enunțat de Bellman astfel :
“Un drum este minim dacă orice subdrum al său este minim
între oricare două vârfuri ale sale. ”
Dacă se notează cu 𝛌𝒊 valoarea minimă a drumurilor de la
vârful 1 la vârful i, ∀ i ∈ X și considerând că
𝚪𝑗−1 = {𝑘1, 𝑘2, 𝑘3,…, 𝑘𝑝} ,
atunci conform principiului lui Bellman trebuie ca
25

𝛌𝒋 = min { 𝛌𝑘1 + 𝐥𝑘1𝑗, 𝛌𝑘2 + 𝐥𝑘2𝑗, … , 𝛌𝑘𝑝 + 𝐥𝑘𝑝𝑗}
= min { 𝛌𝑖 + 𝐥𝑖𝑗|I ∈𝚪𝑗−1}
Dacă se definește matricea arcelor V = (𝑣𝑖𝑗 )𝑖,𝑗 ∈ x astfel :
𝑣𝑖𝑗 ={ Prin urmare valorile 𝛌𝒊, i ∈ X, trebuie să verifice relațiile :

{

Acest sistem de ecuații îl p ot rezolva bazându -ne pe
principiul lui Bellman folosind un procedeu iterativ. Metoda
de rezolvare este cunoscută și cu numele de algoritmul
Bellman -Kallaba.

Algoritmul Bellman -Kalaba determină valorile și
drumurile minime de la vârful 1 la orice alt vârf într -un graf
oarecare sau detectează existența unui circuit de valoare
negativă. 0, i=j
𝐥𝑖𝑗, (i, j) ∈ U
∞, altfel
𝛌𝒊=𝟎
𝛌𝒋 = min{ 𝛌𝒊 + 𝑣𝑖𝑗 | i=1,n}, j >= 2
26

(a) Inițializări
{ k:=1;

(b) Iterația de bază
{ k:=k+1;

(c) Criteriul de stop
dacă ( 𝛌𝑗𝑘+1 = 𝛌𝑗𝑘 pentru j=1,n) atunci stop sfd ;
dacă k <= n atunci go to (b)
altfel tipărește “există circuit de valoare
negativă ”;
stop;
sfd.
𝛌11 := 0
𝛌𝑗1 := 𝑣𝑖𝑗, j >= 2

𝛌1𝑘+1 := 0
𝛌𝑗𝑘+1 := min{ 𝛌𝑖𝑘 + 𝑣𝑖𝑗 | 𝑖=1,𝑛}, j >= 2

27

Voi aplica algoritmul Bellman -Kalaba pentru graful din
figura de mai jos:

2 5
3 6 4
1 7
8 2 1 -4 2
-2
2 3
28

La sfârșitul aplicării algoritmului , matrice a valorilor 𝛌𝑖𝑘,
calculat ă de acesta, este cea din tabloul de mai jos :

k 𝛌1𝑘 𝛌2𝑘 𝛌3𝑘 𝛌4𝑘 𝛌5𝑘 𝛌6𝑘
1 0 7 ∞ ∞ ∞ ∞
2 0 7 8 3 8 ∞
3 0 7 6 3 8 10
4 0 7 6 3 8 8
5 0 7 6 3 8 8

Valorile de pe ultima linie (sau penultima) a coloanei
𝛌𝑖𝑘 sunt valorile minime de la vârful 1 la vârful i.
Observație : În aplicarea algoritmului Bellman -Kalaba,
pentru a determina elementul 𝛌𝑖𝑘+1 din tablou se
procedează astfel: se adună linia k din tablou cu coloana
i din matricea valorilor arcelor apoi se determină
valoarea minimă a rezultatelor. Valoarea minimă se
trece în tabel pe poziția 𝛌𝑖𝑘+1.
Iau o aplicație practică : consider o schelă de extracție
petrolieră care este plasată (vârful 8) la o distanță
oarecare de țărmul unei mări (vârful 1). Ținând cont de
posibilitățile de plantare a stâlplilor de susținere în
funcție de curenții de apă, cât și de adâncimea apei în
diverse pun cte, să se stabilească locurile de plantare a
stâlpilor de susținere necesari construcției unei conducte
de aducțiune.
29

Costurile conductelor, a stâlpilor, precum și a
posibilităților de instalare sunt date în graful din figura
de mai jos.

1 2
3
4 7
6
5 1
2
3
4
5 8 11
6 13
14
2
3 8 6
15
5
9 4
30

Planul instalării conductei de aducțiune, cu un cost total
minim, este dat de drumul de valoare minimă în graful dat.
Pentru determinarea drumului de valoare minimă, vo i folosi
algoritmul Bellman -Kalaba.
Matricea V a valorilor arcelor este:

K
𝛌1𝑘

𝛌2𝑘
𝛌3𝑘
𝛌4𝑘
𝛌5𝑘
𝛌6𝑘
𝛌7𝑘
𝛌8𝑘
1 0 1 3 5 ∞ ∞ ∞ ∞
2 0 1 3 5 8 13 14 20
3 0 1 3 5 8 11 14 17
4 0 1 3 5 8 11 13 17
5 0 1 3 5 8 11 13 17
0 1 3 5 ∞ ∞ ∞ ∞
∞ 0 2 ∞ ∞ ∞ 13 ∞
∞ ∞ 0 4 5 11 14 ∞
∞ ∞ ∞ 0 6 8 ∞ 15
∞ ∞ ∞ ∞ 0 3 ∞ 9
∞ ∞ ∞ ∞ ∞ 0 2 6
∞ ∞ ∞ ∞ ∞ ∞ 0 4
∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 2 1 3 4 5 6 7 8
1
2
3
4
5
6
7
8
31

𝛌11 = 0 ;
𝛌21 = 𝑣12 =1 ; 𝛌31 = 𝑣13 =3 ; 𝛌41 = 𝑣14 =5 ;
𝛌51 = 𝑣15 = ∞; 𝛌61 = 𝑣16 = ∞; 𝛌71 = 𝑣17 = ∞;
𝛌81 = 𝑣18 = ∞;

𝛌12 = min[0+0, ∞+1, ∞+3, ∞+5, ∞+∞, ∞+∞, ∞+∞, ∞+∞]=0;
𝛌22 = min[1+0, 0+1, ∞+3, ∞+5, ∞+∞, ∞+∞, ∞+∞, ∞+∞]=1;
𝛌32 = min[3+0, 2+1, 0+3, ∞+5, ∞+∞, ∞+∞, ∞+∞, ∞+∞]=3;
𝛌42 = min[5+0, ∞+1, 4+3, 0+5, ∞+∞, ∞+∞, ∞+∞, ∞+∞]=5;
𝛌52 = min[ ∞+0, ∞+1, 5+3, 6+5, 0+ ∞, ∞+∞, ∞+∞, ∞+∞]=8;
𝛌62 = min[ ∞+0, ∞+1, 11+3, 8+5, 3+ ∞, 0+∞, ∞+∞, ∞+∞]=13;
𝛌72 = min[ ∞+0, 13+1, 14+5, ∞+5, ∞+∞, 2+∞, 0+∞,∞+∞]=14;
𝛌82 = min[ ∞+0, ∞+1, ∞+5, 15+5, 9+ ∞, 6+∞, 4+∞,0+∞]=20.

𝛌13 = min[0+0, ∞+1, ∞+3, ∞+5, ∞+8, ∞+13, ∞+14, ∞+20]=0;
𝛌23 = min[1+0, 0+1, ∞+3, ∞+5, ∞+8, ∞+13, ∞+14, ∞+20]=1;
𝛌33 = min[3+0, 2+1, 0+3, ∞+5, ∞+8, ∞+13, ∞+14, ∞+20]=3;
𝛌43 = min[5+0, ∞+1, 4+3, 0+5, ∞+8, ∞+13, ∞+14, ∞+20]=5;
𝛌53 = min[ ∞+0, ∞+1, 5+3, 6+5, 0+8, ∞+13, ∞+14, ∞+20]=8;
𝛌63 = min[ ∞+0, ∞+1, 11+3, 8+5, 3+8, 0+13, ∞+14, ∞+20]=11;
𝛌73 = min[ ∞+0, 13+1, 14+3, ∞+5, ∞+8, 2+13, 0+14, ∞+20]=14;
𝛌83 = min[ ∞+0, ∞+1, ∞+3, 15+5, 9+8, 6+13, 4+14,0+20]=1 7;

32

𝛌14 = min[0+0, ∞+1, ∞+3, ∞+5, ∞+8, ∞+11, ∞+14, ∞+17]=0;
𝛌24 = min[1+0, 0+1, ∞+3, ∞+5, ∞+8, ∞+11, ∞+14, ∞+17]=1;
𝛌34 = min[3+0, 2+1, 0+3, ∞+5, ∞+8, ∞+11, ∞+14, ∞+17]=3;
𝛌44 = min[5+0, ∞+1, 4+3, 0+5, ∞+8, ∞+11, ∞+14, ∞+17]=5;
𝛌54 = min[ ∞+0, ∞+1, 5+3, 6+5, 0+8, ∞+11, ∞+14, ∞+17]=8;
𝛌64 = min[ ∞+0, ∞+1, 11+3, 8+5, 3+8, 0+1 1, ∞+14, ∞+17]=11;
𝛌74 = min[ ∞+0, 13+1, 14+3, ∞+5, ∞+8, 2+1 1, 0+14, ∞+17]=13;
𝛌84 = min[ ∞+0, ∞+1, ∞+3, 15+5, 9+8, 6+1 1, 4+14,0+ 17]=17;

𝛌15 = min[0+0, ∞+1, ∞+3, ∞+5, ∞+8, ∞+11, ∞+13, ∞+17]=0;
𝛌25 = min[1+0, 0+1, ∞+3, ∞+5, ∞+8, ∞+11, ∞+13, ∞+17]=1;
𝛌35 = min[3+0, 2+1, 0+3, ∞+5, ∞+8, ∞+11, ∞+13, ∞+17]=3;
𝛌45 = min[5+0, ∞+1, 4+3, 0+5, ∞+8, ∞+11, ∞+13, ∞+17]=5;
𝛌55 = min[ ∞+0, ∞+1, 5+3, 6+5, 0+8, ∞+11, ∞+13, ∞+17]=8;
𝛌65 = min[ ∞+0, ∞+1, 11+3, 8+5, 3+8, 0+1 1, ∞+13, ∞+17]=11;
𝛌75 = min[ ∞+0, 13+1, 14+3, ∞+5, ∞+8, 2+1 1, 0+1 3,∞+17]=13;
𝛌85 = min[ ∞+0, ∞+1, ∞+3, 15+5, 9+8, 6+1 1, 4+1 3,0+17]=17.

Valoarea drumului minim e dată de ultima valoare din
liniile egale, adică 𝛌84 sau 𝛌85. Drumul de lungime
minimă căutat are lungimea 17. Pentru determinarea
succesiunii de vârfuri care formează drumul căutat,
urmărim pe linia 4 sau 5 valorile strict descrescătoare ce
ne conduc de la 8 la fiecare vârf 𝑋𝑖.
33

Am posibilitatea să aleg în componența drumurilor
minime vârfurile : 1, 2, 3, 4, 5, 6, 7, 8. Astfel obțin
drumurile: (1,2,3,5,7,8), (1,3,5,6,7,8), (1,2,3,5,6,8),
(1,3,5,6,8) care pot da câte un plan al instalării
conductei de aducțiune, cu un cost total minim .
Alegerea unui plan sau al altuia se poate face ținând
cont și de alte condiții, cum ar fi dezvoltarea în
perspectivă a acestei zone extractive sau a extinderii
acestei instalații pentru alte produse de pe țărm.
Un fragment de program C++ care determin ă toate
drumurile minime între oricare două vârfuri ale unui
graf G=(X,U) cu X= {1,2,…,n} este:

l[1][1]=0;
for(j=2;j<=n;j++) l[1][j]=v[i][j];
k=1;
for(i=1;i<=n;i++)
for(j=2;j<=n;j++)
for(k=1;k<=n;k++)
l[k+1][j]=minn(l[k][i]+v[i][j]);
for(j=1;j<=n;j++)
if(l[k+1][j]==l[k][j]) cout<<l[k][j];
else cout<<”exist ă circuit de valoare negativă ”;

34

IV.3. ALGORITM I DE DETERMINARE A VALORILOR
MAXIME DE DRUMURI DE LA UN VÂRF DAT

Algoritimul Roy-Floyd
Fie G=(X,U) un graf orientat fără circuite,
U={𝑋1,𝑋2,…,𝑋𝑛} și I :U -> R. Se pune problema deter minării
drumurilor de lungime maximă în acest graf. Voi atașa
grafului G o matrice M= (𝑚𝑖𝑗)𝑛𝑋𝑛, definită astfel :

𝑚𝑖𝑗 = {

Observ că această matrice este asemănătoare matricei
costurilor atașată graficului pentru determinarea drumurilor
minime, cu diferența că pentru perechi de noduri distincte
𝑋𝑖,𝑋𝑗 pentru care nu există arcul ( 𝑋𝑖,𝑋𝑗) marcăm în matrice
-∞. Intuitiv, aceasta ar însemna că inexistența arcului (𝑋𝑖,𝑋𝑗)
este totuna pentru studiul drumurilor maxime, cu existența
unui arc de lungime -∞.
Considerând problema determinării tuturor drumurilor
maxime între oricare două vârfuri distincte 𝑋𝑖,𝑋𝑗 pentru care l((𝑋𝑖,𝑋𝑗)), dacă ( 𝑋𝑖,𝑋𝑗) ∈ U
0, dacă i = j
-∞, dacă (𝑋𝑖,𝑋𝑗) ∉ U și i ≠ j
35

există drum de la 𝑋𝑖 la 𝑋𝑗, putem utiliza următorul algoritm,
care este o adaptare a lui Roy -Floyd.
Fie M matricea definită mai sus, iar D= (𝑑𝑖𝑗)𝑛𝑋𝑛 cu
𝑑𝑖𝑗 = {

Pentru k:=1,n execută
Pentru i :=1,n ( i ≠ k) execută
Pentru j:=1,n ( j ≠ k) execută
Dacă 𝑚𝑖𝑗 < 𝑚𝑖𝑘 + 𝑚𝑘𝑗
Atunci
𝑚𝑖𝑗 := 𝑚𝑖𝑘 + 𝑚𝑘𝑗
𝑑𝑖𝑗 := 𝑑𝑘𝑗
Altfel
Dacă 𝑚𝑖𝑗 := 𝑚𝑖𝑘 + 𝑚𝑘𝑗
Atunci
𝑑𝑖𝑗 := 𝑑𝑖𝑗 ∪ 𝑑𝑘𝑗
Sfârșit dacă
Sfârșit dacă
Sfârșit pentru
Sfârșit pentru {𝑋𝑖 }, dacă 𝑚𝑖𝑗 > -∞ și i ≠
j
Φ, dacă 𝑚𝑖𝑗 = ∞ sau i=j
36

Sfârșit pentru
Un program C++ de determinare a tuturor drumurilor
maxime între oricare două noduri folosind algoritmul
prezentat anterior, pentru un graf fără circuite G= (X,U),
U={1,2,…,n} este:

#include <iostream>
#define NMAX 20
#define INF 10000
using namespace std;
typedef struct
{
int nre;
int elem[NMAX];
} MULTIME;
int c[NMAX][NMAX], n,lg, dr[NMAX];
MULTIME d[NMAX][NMAX];

void citire ()
/* initializeaza matricea costurilor */
{
int arc,i,j,u, v,l;
cin>>n; /* numarul de varfuri */
for(i=1;i<=n;i++)
37

{
for(j=1;j<=n;j++)
c[i][j]=INF;c[i][i]=0;
}
cin>>arc ; /*numarul de arce */
for(i=1;i<=arc;i++)
{
/* citeste extremitatile arcului i si lungimea sa */
cin>>u>>v>>l;
c[u][v]=l;
}
}
void init() /* initializeaza matricea predecesorilo r d */
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if((c[i][j]<INF)&& (i!=j))
{
d[i][j].nre=1; /*initializam d[i][j] cu {i} */
}
else d[i][j].nre=0; /*d[i][j] este multimea vida */
}
void drum (int i,int j)
38

/* genereaza in vectorul dr un drum de la i la j pornind din nodul j */
{
int k;
if(i!=j)
for(k=1;k<=d[i][j].nre;k++)
{
lg++;
dr[lg]=d[i][j].elem[k];
drum(i,d[i][j].elem[k]);
lg–;
}
else
{
cout<<" \n";
for(k=lg;k>=1;k –)
cout<<dr[k]<<" ";
}
}
void afisare()
/* afiseaza rezultatele */
{
int i,j,l;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
39

if(i!=j)
{
cout<<" \n";
if(c[i][j]==INF)
cout<<"nu exista drum de la "<<i<<" la "<<j;
else
{
cout<<"lungimea drumurilor m axime de la "<<i<<" la"<<j<<"
este "<<c[i][j];
lg=l;
dr[l]=j;
drum(i,j);
}
}
}
int main()
{
int i,j,k,x,p,q,exista;
citire();
init();
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(c[i][j] <c[i][k]+c[k][j])
40

{
c[i][j]=c[i][k]+c[k][j];
d[i][k]=d[k][j];
}
else if(c[i][j]==c[i][k]+c[k][j])
{
/* adaug la multimea d[i][j] multimea d[k][j] */
x=d[i][j].nre;
for(p=1;p<=d[k][j].nre;p++)
{
exista=0;
for(q=1;(q<=d[i][j].nre) && (!exista); q++)
if(d[k][j].elem[p]==d[i][j].elem[q])
exista=1;
if(!exista)
{
x++;
d[i][j].elem[x]=d[k][j].elem[p];
}
}
d[i][j].nre=x;
}
afisare();
}
41

V. INSTRUCȚIUNI SAGE PENTRU REPREZENTAREA
GRAFURILOR

Pentru reprezentarea unui graf din toate punctele de vedere,
am folosit platforma cocalc.com, iar în cadrul acestui capitol
voi descrie diverse instrucțiuni cu privire la particularitățile
acestuia. Astfel, am luat ca exemplu

h=DiGraph([(1,2,1),(1,3,3),(1,4,5),(2,3,2),(2,7,13),(3,4,4),(3,5
5),(3,6,11),(3,7,14),(4,5,6),(4,6,8),(4,8,15),(5,6,3),(5,8,9),(6,7,
2),(6,8,6),(7,8,4)]) ,
unde h este un graf orientat av ând ca parametri o serie de
muchii care conțin extremitățile și lungimile drumu rilor dintre
acestea.

h.show(edge_labels=True) – este o instrucțiune care afișează
graful cu lungimile drumurilor afișate pe muchii

42

h.adjacency_matrix() – afișează matricea de adiacență,
valorile acesteia fiind 1 dacă există drum direct între două
vârfuri, sau 0 în caz contrar

h.weighted_adjacency_matrix() – afișează matricea distanțelor
directe , dacă există drum direct se afișează lungimea acestuia,
dacă nu există se afișează doar 0.

h.connected_components() – afișează component a conex ă,
fiind formată din toate vârfurile grafului

h.strongly_connected_components() – afișează componentele
tari conexe, acestea fiind reprezentate de toate vârfurile
grafului

43

h.shortest_path_length(1,8,True) – afișează lungimea celui
mai scurt drum dintre vârfurile 1 și 8

h.longest_path(1,8,True) – afișează lungimea celui mai lung
drum dintre vârfurile 1 și 8, respectiv numărul de noduri care
îl alcătuiesc.

h.all_paths(1,8) – afișează toate drumurile posibile dintre
nodurile 1 și 8

h.shortest_paths(1) – determină cele mai scurte căi , formate
dintr -un număr minim de muchii, plecând din nodul 1

h.distance_all_pairs(True) – afișează perechile de noduri ce
formează drumuri și costurile lor

44

VI. CONCLUZI I

Realizând operațiile din cadrul algoritmicii grafurilor,
pot trage concluzia că grafurile aparțin lumii
înconjurătoare iar prin intermediul acestora putem face
calcule precise, de exemplu asupra locurilor unde
intenționăm să ajungem atunci când pornim la drum. [7]
Pe lângă domeniul rutier, grafurile apar și în alte
domenii, precum chimia, informatica, biologia,
geografia, rețelele de socializare, căile aeriene ,
instalațiile electrice/de încălzire, rețelele de canalizare
și apă curentă. [7]
Grafurile mai pot arăta legăturile dintre anumite
grupuri sau oameni, cele orientate pot arăta transferul
de informații sau a unor bunuri. Un arbore genealogic
este de asemenea un graf neorientat. [7]
De asemenea, teoria grafurilor mai este folosită și în
reprezentarea caricaturilor, dând exemplu rubrica
“Andografia zilei ” în care personajele și replicile
acestora sunt reprezentate sub formă de grafuri. [8]

45

46

VII. BIBLIOGRAFIE

[1] Alfred V. Aho, Jeffrey D. Ullman, Foundations of
Computer Science, Computer Science Press, New York,
1995.
[2] J. Bang -Jensen, G. Goutin, Digraphs: Theory, Algorithms
and Applications, Springer -Verlag, London, 2000.
[3] C. Berge, Théorie des graphes et ses applications,
Dunod, Paris, 1967.
[4] Nicolae Rădescu, Eugenia Rădescu, Probleme de teoria
grafurilor, Scrisul Romanesc, Craiova, 1982.
[5] E. T anaguchi, City logistic, Pergamon, Amsterdam,
2001.
[6] I. Tomescu, Combinatorică și Teoria Grafurilor,
București, 1978.
[7] http://atestat -grafuri.weebly.com/grafuri -icircn –
via539a -reala.html
[8] http://eazi.ro/andografia -zilei/discurs -politic

47