ALGORITMI FUNDAMENTALI PE GRAFURI. DETERMINAREA DRUMURILOR ȘI DISTAN ȚELOR OPTIME Coordonator Științific, Conf. Univ. Dr. Cristina FLAUT Absolvent ,… [628889]

Constan ța
2020

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,
Conf. Univ. Dr. Cristina FLAUT
Absolvent: [anonimizat]

1
CUPRINS

Introducere ………………………………………………………………………………………………….. 2
1. Scurt istoric al teoriei grafurilor ……………………………………………………………..3
2. Noțiuni Preliminarii ……………………………………………………………… ..5
2.1. Defini ții și clasificări ale grafurilor ………………………………………. ..5
2.1.1. Defini ția general ă ……………………………………………………… ..5
2.1.2. Defini ția matematic ă …………………………………………………. ..5
2.1.3. Clasificări ale grafurilor ……………………………………………….. ..6
2.2. Reprezent ări ale grafurilor ……………………………………………… .7
2.2.1. Matricea de adiacen ță. Defini ție și exemple …………. ……….. …….7
2.2.2. Matricea drumurilor. Definitie, exemple și determinare …….. …….9
2.2.3. Lista vecinilor / de adiacen ță …………………………………………1 5
2.3. Parcurgerea grafurilor ………………………………………………………… …………1 6
2.3.1. Parcurgerea în lă țime ……………………………………………………………………1 6
2.3.2. Parcurgerea în adâncime ………………………………………………………………20
3. Drumuri optime. Algoritmi de determinare a drumurilor o ptime
3.1. Drumuri Optime ………………………………… ..……….………………………………..24
3.2. Algoritm de determinare a valorilor m inime de drumuri
de la un vârf dat………………………………. ………………………….25
3.3. Algoritm de determinare a valorilor maxime de d rumuri
de la un vârf dat ……………………………… ………………………….30
3.4. Aplica ție practic ă în vederea determin ării unui drum minim ……….38
4. Instruc țiuni S AGE pentru reprezentarea grafurilor ……… ……………4 2
5. Concluzii …………………………. ………………. ………………………………..46
6. Bibliografie …………………………………………….. ………………………….48

2
Introducere

În cadrul lucrării mele de licen ță, mi-am propus s ă analizez problematica
grafurilor , în special algoritmii fundamentali pentru determinarea
drumurilor și distan țelor optime. Astfel , armonizez unul din hobby -urile
mele, călători ile, cu metode științifice de determinare a traseelor și
circuitelor turistice optime pe care inten ționez să le vizitez .
Tematica lucrării de licen ță se refer ă la algoritmii fundamentali pe grafuri
respectiv determinarea drumurilor și distan țelor optime, iar în structura
lucrării sunt cuprinse diagrame , tabele, calcule și fragmente de cod
referitoare la fiecare problemă abordată.
Lucrarea este structurat ă pe patru capitole , după cum urm ează:
În primul capitol am făcut un scurt istoric al teoriei grafurilor în care am
evidențiat repere istorice cu privire la descoperirea și dezvoltarea
problemelor fundamentale .
Al doilea capitol cuprinde defini țiile, parcurgerile și reprezent ările
grafurilor .
În al treilea capitol am dezvoltat tematica drumuril or optime și am abordat
cei mai importan ți algoritmi de determinare a acestora, at ât de valoare
minim ă, cât și de valoare maxim ă, aceștia fiind , Bellman -Kalaba (pentru
drumuri minime) și Roy -Floyd (pentru drumuri maxime) , construind și o
aplicație practic ă de calcul a unui drum minim .
În ultimul capitol am realizat o aplica ție software cu prinzând și instrucțiuni
de programare a unui graf în concordan ță cu tematicile dezvoltate în
precedentele capitole.
Lucrarea se încheie cu exprimarea concluziilor și eviden țierea surselor
bibliografice.

3
1. Scurt istoric al teoriei grafurilor
Începuturile teoriei grafurilor își au originea în 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: două insule A și B, formate de râul
Pragel în Königsberg (Prusia orientală, acum orașul Kaliningrad din vestul
Rusiei) sunt conectate între ele și de malurile C și D prin șapte poduri
(figura de mai jos) , formând, în acea vreme, patru cartiere. În plimbările lor,
localnicii încercau să traverseze toate cele șapte poduri, astfel încât, plecând
dintr-un anumit cartier, să se înapoieze în acesta trecând o singură dată
peste fiecare pod. Nu reușeau să facă aces t lucru. 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 matemat ician 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 care lui Euler i se păreau evidente.
În anul 1859, matematicianul William Hamilton (1805 -1865) a lansat
un joc care presupune gãsirea unui circuit pe muchiile dodecaedrului, care sã
treacã prin fiecare vârf o singurã datã. „Câmpul de joc” este un dodecaedru
regulat, adic ã un corp geometric cu toate fe țele pentagoane regulat e. Acesta
a rămas în istoricul informaticii sub denumirea de graf hamiltonian.

4

Claude Berge (1926 -2002) a fost un matematician francez, recunoscut
drept unul din fondatorii combinatoricii și teoriei grafurilor. Acesta a jucat un
rol major în rena șterea combinatoric ii, iar în teoria grafurilor a r ămas
cunoscut pentru conjectura grafurilor perfecte, rezolvat ă după câteva luni de
la moartea sa.
Alte izvoare ale teoriei grafurilor sunt studiul re țelelor electrice,
problema celor patru culori, teoriei 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 în anul 1878 de
către matematicianul Sylvester.
Dintre cercetătorii care s -au ocupat de teoria grafurilor în ultimele
decenii, îi aminitim pe S.Cataranciuc, V.Cepoi, C.Croitoru, L.R.Ford, M.
Gondran, W.T.Tutte, H. -J. Voss și T.Zamfirescu.

Vederea jocului original

Vederea jocului în formă grafică
( graf hamiltonian )

5
2. Noțiuni Preliminarii
2.1. Defini ții și clasificări ale grafurilor
2.1.1. Defini ția generală
Un graf este o structură care corespunde unui grup de obiecte, în
care unele perechi de obiecte sunt într -un anumit sens "legate"
reciproc. Obiectele corespund unor abstrac ții matematice numite
într-un graf noduri sau vârfuri (numite și puncte) și fiecare
legătură dintre perechile de obiecte asociate se nume ște muchie
(numit ă și arc sau linie, prin care este și reprezentat ă). De
obicei, un graf este reprezentat în form ă schematic ă ca un set
sau grup de puncte pentru noduri, iar aceste a sunt unite două
câte două de linii sau curbe pentru muchii.
2.1.2. Defini ția matematică
Un graf este o pereche ordonată de mul țimi (X,U), unde X este o
mulțime finit ă și nevid ă de elemente numite noduri sau v ârfuri
(𝑋𝑖) iar U este o mul țime de perechi neordonate din X, de forma
([𝑋𝑖, 𝑋𝑗]) numite muchii sau arce.
Ex: G= (X,U) unde:
X={1,2,3,4,5,6,7} și
U={ [1,2],[1,6],[1,7],[2,3], [2,5], [2,7],[3,7],[5,7] }

2 1
3
4 5 7 6

6
2.1.3. Clasificări ale grafurilor

Cel mai important criteriu de clasificare al grafurilor este în
func ție de proprietatea de simetrie : dacă [𝑋𝑖, 𝑋𝑗] apar ține mul țimii
muchiilor U, atunci și [𝑋𝑗, 𝑋𝑖] apar ține mul țimii U.
Conform acestei proprietă ți, grafurile se împart în :
– grafuri neorientate, care au proprietatea de simetrie , în
cadrul cărora elementele de legătură dintre vârfuri se numesc
muchii (Exemplul 1) ;
– grafuri orientate, care nu au proprietatea de simetrie, în
cadrul cărora elementele de legătură dintre vârfuri se numesc
arce iar perechile de v ârfuri sunt ordonate (Exemplul 2).

Exemplul 1 – Grafuri neorientate

X={1,2,3,4,5,6}
U={[1,2],[1,6],[2,3],[2,5]}

Gradul vârfului 2 este 3 (gradul unui vârf reprezintă numărul de
muchii incidente cu acesta)

Vârf izolat : 4 ( Dacă un vârf nu este extremitatea nici unei
muchii, atunci el se nume ște vârf izolat)

Vârf terminal : 3,5,6

Vârfuri adiacente : sunt vârfurile între care există o m uchie.
(2 și 3), (1 și 2), (1 și 6), (2 și 5)

Muchii incidente: sunt muchiile cu o extremitate comună.
[1,2] și [2,3], [1,2] și [2,5]

2 1
3
4 5
5 6

7
Exemplul 2 – Grafuri orientate
X={1,2,3,4,5}
U={[1,2],[1,3],[2,5],[4,2],[4,5]}

Gradul intern al vârfului 2 este 2 (numărul de muchii care intră
într-un vârf)
Gradul extern al vârfului 2 este 1 (numărul de muchii care ies
dintr-un vârf)
Vârf terminal : 3
Vârful 5 este succesor al vârfului 2
Vârful 2 este predecesor al vârfului 5

2.2. Reprezent ări ale grafurilor

Grafurile pot fi reprezentate prin 3 metode :
 Matricea de adiacen ță
 Matricea drumurilor
 Lista vecinilor / adiacen ță
2.2.1. Matricea de adiacen ță. Definiție și exemple
Matricea de adiacen ță asociat ă unui graf G cu n v ârfuri este o
matrice p ătratică de ordinul n, A = (𝑎𝑖𝑗)𝑛𝑋𝑛 ,
unde 𝑎𝑖𝑗 = { 1 2
5 3
4
1, dac ă (i,j) ∈ U
0, dacă (i,j) ∉ U

8
Defini ția de mai sus este valabilă atât pentru grafuri neorientate
cât și pentru grafurile orientate.

Exemplul 1 – se dă următorul graf neorientat cu n=5

Matricea de adiacență a grafului este :

Exemplul 2 – se dă următorul graf orientat cu n=5

Matricea de adiacență a grafului este :

Matricea de adiacență a unui graf neorientat este una simetrică, iar cea
asociată unui graf orientat nu este neapărat simetrică. 1 3
2
4 5
A = 0 0 1 1 0
0 0 0 0 0
1 0 0 1 1
1 0 1 0 1
0 0 1 1 0

1 3
2
4 5
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

9
În matricea de adiacență asociată unui graf neorientat, suma elementelor
liniei i (care este identică cu suma elementelor coloanei i) repre zintă
gradul vârfului i oricare ar fi i de la 1 la n.
2.2.2. Matricea drumurilor. Definitie , exemple și determinare
Se nume ște matrice a drumurilor asociat ă grafului orientat
G=(X,U), cu U={ 𝑋1,𝑋2,…, 𝑋𝑛} matricea M= (𝑚𝑖𝑗)𝑛𝑋𝑛 dată prin
𝑚𝑖𝑗 = {
Exemplul 1 – se dă următorul graf neorientat cu n=5

Matricea drumurilor din graf este :

Exemplul 2 – se dă următorul graf orientat cu n=5

1, dac ă există drum în G de la 𝑥𝑖 la 𝑥𝑗
0, în caz contrar
1 3
2
4 5
A = 0 0 1 1 1
0 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0

1 3
2
4 5

10
Matricea drumurilor grafului este :

Pentru determinarea matricei drumurilor unui graf putem folosi
algoritmul Roy-Warshall care construie ște matricea pornind de la
matricea de adiacen ță a grafului , având următorul pseudocod :
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
Exemplu: se dă un graf orientat cu 7 vârfuri și matricea lui de
adiacență (M) . Se va aplica algoritmul lui Roy – Warshall pentru
găsirea matricei drumurilor (M*).

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
2 3
4 5
6
7

11

M=

M*=

a[2,1]=1 => noul a[2,1]=1
a[2,2]=0 => noul a[2,2]=min(a[2,1],a[ 3,2])=min(1, 1)=1
a[2,3]=0 => noul a[2,3]=min(a[2,1],a[1,3])=min(1,1)=1
a[2,4]=0 => noul a[2,4]=min(a[2,1],a[1,4])=min(1,0)=0
a[2,5]=0 => noul a[2,5]=min(a[2,1],a[1,5])=min(1,0)=0
a[2,6]=0 => noul a[2,6]=min(a[2,1],a[1,6])=min(1,0)=0
a[2,7]=0 => noul a[2,7]=min(a[2,1],a[1,7])=min(1,0)=0

a[3,1]=0 => noul a[3,1]=min(a[3,2],a[2,1])=min(1,1)=1
a[3,2]=1 => noul a[3,2] r ămâne tot 1.
a[3,3]=0 => noul a[3,3]=min(a[3, 2],noul a[2,3])=min( 1,1)=1
a[3,4]=0 => noul a[3,4]=min(a[3,1],a[1,4])=min(0,0)=0
a[3,5]=0 => noul a[3,5]=min(a[3,1],a[1,5])=min(0,0)=0
a[3,6]=0 => noul a[3,6]=min(a[3,1],a[1,6])=min(0,0)=0
a[3,7]=0 => noul a[3,7]=min(a[ 3,1],a[1,7])=min(0,0)=0

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
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 Dacă aplicăm matricei M
transformările 𝑇1,𝑇2,…, 𝑇7 se
obține matricea drumurilor
M*

12
a[4,1]=0 => noul a[4,1]=min(a[4,2],a[2,1])=min(1,1)=1
a[4,2]=1 => noul a[4,2] rămâne tot 1.
a[4,3]=1 => noul a[4,3] rămâne tot 1.
a[4,5]=0 => noul a[4,5]=min(a[4, 6],a[6,5])=min(1,1)=1
a[4,6]=1 => noul a[4,6] rămâne tot 1
a[4,7]=1 => noul a[4,7] rămâne tot 1

a[5,1]=0 => noul a[5,1]=min(a[5,3], noul a[3,1])=min(1,1)=1
a[5,2]= 0 => noul a[5,2 ]=min(a[5,3],a[3,2])=min(1,1)=1
a[5,3]=1 => noul a[5,3] rămâne tot 1
a[5,4]=1 => noul a[5,4] rămâne tot 1
a[5,6]=0 => noul a[5,6]=min(a[5,4],[4,6])=min(1,1)=1
a[5,5]=0 => noul a[5,5]=min( noul a[5,6], a[6,5])=min(1,1)=1
a[5,7]=0 => noul a[5,7]=min(a[5,4],[4,7])=min(1,1)=1

a[6,1]=0 => noul a[6,1]=min(a[6,5], noul a[5,1])=min(1,1)=1
a[6,3]=0 => noul a[6, 3]=min(a[6,5],a[5,3] )=min(1,1)=1
a[6,2]=0 => noul a[6 ,2]=min(a[6, 5],noul a[5,2])=min(1,1)=1
a[6,4]=0 => noul a[6,4]=min(a[6,5],a[5,4])=min(1,1)=1
a[6,5]=1 => noul a[6,5] rămâne tot 1
a[6,6]=0 => noul a[6,6]=min(noul a[6, 5],noul a[5,6])=min(1,1)=1
a[6,7]=0 => noul a[6,7]=min(a[6, 5],noul a [5,7])=min(1,1)=1

a[7,1]=0 => noul a[7,1]=min(a[7,6],noul a[6,1])= min(1,1)=1
a[7,2]=0 => noul a[7,2]=min(a[7,6],noul a[6,2])= min(1,1)=1
a[7,3]=0 => noul a[7,3]=min(a[7,6],noul a[6,3])= min(1,1)=1
a[7,4]=0 => noul a[7,4]=min(a[7,6],noul a[6,4])= min(1,1)=1
a[7,5]=0 => noul a[7,5]=min(a[7,6],noul a[6,5])= min(1,1)=1
a[7,6]=1 => noul a[7,6] rămâne tot 1
a[7,7]=0 => noul a[7,7]=min(a[7,6],noul a[6,7])= min(1,1)=1

13
a[1,1]=0 => noul a[1,1]=min(a[1,3],noul a[3,1])=min(1,1)=1
a[1,2]=0 => noul a[1,1]=min(a[1,3], a[3,2])=min(1,1)=1
a[1,3]=0 => noul a[1,3] rămâne tot 1
a[1,4]=0 => noul a[1,4]=min(a[ 1,3],a[3,4])=min( 1,0)=0
a[1,5]=0 => noul a[1,5]=min(a[ 1,3],a[3,5])=min( 1,0)=0
a[1,6]=0 => noul a[1,6]=min(a[ 1,3],a[3,6])=min( 0,0)=0
a[1,7]=0 => noul a[1,7]=min(a[1,3],a[3,7])=min(0,0)=0
Pe baza determinării matricei drumurilor, conform calculelor de
mai sus, deoarece M* con ține 1 pe diagonala principal ă, rezult ă
că toate v ârfurile grafului apar țin unor circuite. 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(𝑋𝑖)
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 }
Consider ăm 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 𝑋4, este
𝐶4={𝑋4,𝑋5,𝑋6,𝑋7}.

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

În baza celor de mai sus, putem realiza un cod în format C++ de
determinare a matricei drumurilor :
“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;
for(i=1;i<=m;i++)
{

15
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");
}
}
============================

2.2.3. Lista vecinilor / de adiacen ță
Reprezentarea unui graf G (orientat sau neorientat) prin liste de
adiacen ță constă în:
 precizarea numărului de vârfuri, n;
 pentru fiecare vârf i (1<=i<=n) se precizează lista Li a
vecinilor săi, adică lista nodurilor adiacente cu nodul i.

Vârful i Lista vecinilor lui i
1 3
2 1
3 2
4 2,3,6,7
5 3,4
6 5
7 2,6

16
2.3. Parcurgerea grafurilor
Fiind dat un graf G, orientat sau nu, se pune problema de a
vizita/parcurge, într -un mod sistematic, toate vârfurile grafului
plecând de la un vârf (de plecare) mergând pe muchii incidente
două câte două.

Această vizitare se poate face în diferite moduri. Dintre aceste
modalită ți, cele mai cunoscute sunt parcurgerea în lățime (br eadth
first) și cea în adâncime (depth first).

Există o relativă asemănare între parcurgerile vârfurilor unui graf cu
parcurgerea elementelor unei matrice. Cea din urmă se poate face
“pe linii” sau “pe coloane”, fiind de precizat ordinea de selectare a
liniilor și coloanelor .

2.3.1. Parcurgerea în lă țime
Teorema parcurgerii în lă țime se refer ă la faptul c ă “se vizitează
vârful de pornire, apoi to ți succesorii acestuia, vecinii nevizita ți ai
acestora și așa mai departe p ână când se viziteaz ă toate v ârfurile
grafului ”.

Exemplu:

1
3 2
5 4
6
7 8

17
Pentru graful din figura de mai sus, ordinea de parcurgere a
vârfurilor 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 vârf (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, voi folosi
un vector VIZ cu n componente, astfel :

𝑉𝐼𝑍[𝑗] =

Pentru oricare j de la 1 la n.
Vârfurile care au vecini nevizita ți urmeaz ă să fie prelucrate î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 }
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}

1, dacă vârful j a fost vizitat
0, în caz contrar {

18

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.

În baza celor de mai sus, putem realiza un cod în format C++ de
parcurgere prin metoda BF a unui graf (orientat sau neorientat)
reprezentat prin matricea de adiacen ță, coada C fiind implementată
sub forma unui vector. Ordinul de complexitate al acestui algoritm
este O( 𝑛2).
“fragment din program de parcurgere prin metoda BF”
===============================
void citeste(void);
void bf(int);
void main(void)
{
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");

19
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 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;
}
}
}

20
2.3.2. Parcurgerea în adâncime
Teorema parcugerii în adâncime este enun țată astfel:
“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 continuă până când se
ajunge la vârful de pornire și acesta nu are succesori nevizita ți.”

Exemplu:

Pentru graful din figura de mai sus, 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 se aleg dintre vârfurile adiacente și nevizitate pentru
un anumit vârf, 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 vârf, de aceea am ales să “cobor âm” din
vârful 1 prin vârful 2 când la fel de bine se putea “cobor î” prin vârful 3
sau 4.

21
O descriere a algoritmului de parcurgere în adâncime a unui graf este:
Vizitează vârful de pornire,
Repetă
Cât timp
Există succesor nevizitat al ultimului vârf vizitează -l,
Sfârșit cât timp;
Revenire la predecesoru l 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[j] cu
aceea și semnifica ție ca la algoritmul BF (ia valoarea 1 dac ă vârful j a
fost vizitat sau 0 în caz contrar) , 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 putem continua “coborîrea” în graf, parcurgem 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ă.
Explica țiile de mai sus pot fi tr anspuse într -un pseudocod de forma :
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}
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

22
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 .
În baza celor de mai sus, putem realiza un cod în format C++ de
parcurgere prin metoda DF a unui graf (orientat sau neorientat)
“fragment din program de parcurgere prin metoda DF”
+++++++++++++++++++++++++++
void citeste(void);
void df(int);
void main(void)
{
int i,x0;
citeste();
for(i=1;i< =n;i++) viz[i]=0;
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++)

23
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)
{
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 –;
}
}

24
3. Drumuri optime. Algoritmi de determinare a drumurilor
optime

3.1. Drumuri optime
Una dintre problemele care apar foarte des în practică este găsirea
drumului optim între două vârfuri ale unui graf. Valoarea unui drum
este dată de suma valorilor arcelor care îl compun. Problema drumului
optim se referă la găsirea, pentru o pereche de vâ rfuri, a drumurilor de
valoare optimă ( minimă și/sau maximă ) între cele două vârfuri și
valorile acestora, în condi țiile existen ței unei func ții care asociaz ă
fiecărui arc o valoare real ă.

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(maxime) 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, se 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.

Se notează 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 ne
putem restrânge la mul țimea drumurilor elementare de la i la j. Deci se i k
j
ω

25
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 este finită, rezultă că
problema determinării valorii minime a drumurilor în condi țiile
precizate are solu ție.
3.2. Algorit m de determinare a valorilor minime de drumuri de la
un vârf dat
Un algoritm cunoscut de determinare a valorilor minime de drumuri de
la un vârf dat este Bellman -Kalaba, care 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
𝛌𝒋 = 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 putem rezolva baz ându-ne pe principiul lui
Bellman folosind un procedeu iterativ. Metoda de rezolvare este
cunoscut ă și cu numele de algoritmul Bellman -Kallaba. 0, i=j
𝐥𝑖𝑗, (i, j) ∈ U
∞, altfel
{ 𝛌𝒊=𝟎
𝛌𝒋 = min{ 𝛌𝒊 + 𝑣𝑖𝑗 | i=1,n}, j >= 2

26
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 ă, parcurgând următoarele
etape :
(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.
Voi aplica algoritmul Bellman -Kalaba pentru graful de mai jos:

𝛌11 := 0
𝛌𝑗1 := 𝑣𝑖𝑗, j >= 2

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

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

27

Matricea valorilor arcelor este:
0 7 8 ∞ ∞ ∞
∞ 0 ∞ -4 1 ∞
∞ 2 0 ∞ ∞ 2
∞ ∞ ∞ 0 ∞ ∞
∞ ∞ ∞ 2 0 ∞
∞ ∞ ∞ ∞ 3 0

Pentru determinarea matricei valorilor 𝛌𝑖𝑘, realizăm următoarele
calcule:
k=1
𝛌11 = 0, 𝛌21 = 𝑣12= 7, 𝛌31 = 𝑣13= 8, 𝛌41 = 𝑣14= 𝛌51 = 𝑣15= 𝛌61 = 𝑣16=∞
k=2
𝛌12 = 𝛌11+1 = min( 𝛌11+𝑣11, 𝛌21 + 𝑣21, 𝛌31 + 𝑣31, 𝛌41 + 𝑣41, 𝛌51 + 𝑣51, 𝛌61 + 𝑣61)
= min(0+0, 7+ ∞, 8+∞, ∞+∞, ∞+∞, ∞+∞) = 0
𝛌22 = 𝛌21+1 = min( 𝛌11+𝑣12, 𝛌21+𝑣22, 𝛌31+𝑣32, 𝛌41+𝑣42, 𝛌51+𝑣52, 𝛌61 + 𝑣62)
= min(0+ 7, 7+0, 8+ 2, ∞+∞, ∞+∞ ∞+∞) = 7
𝛌32 = 𝛌31+1 = min( 𝛌11+𝑣13, 𝛌21+𝑣23, 𝛌31+𝑣33, 𝛌41+𝑣43, 𝛌51+𝑣53, 𝛌61 + 𝑣63)
= min(0+ 8, 7+∞, 8+0, ∞+∞, ∞+∞, ∞+2) = 8
𝛌42 = 𝛌41+1 = min( 𝛌11+𝑣14, 𝛌21+𝑣24, 𝛌31+𝑣34, 𝛌41+𝑣44, 𝛌51+𝑣54, 𝛌61 + 𝑣64)
= min(0+ ∞, 7+(-4), 8+∞, ∞+0, ∞+∞, ∞+∞) = 3
𝛌52 = 𝛌51+1 = min( 𝛌11+𝑣15, 𝛌21+𝑣25, 𝛌31+𝑣35, 𝛌41+𝑣45, 𝛌51+𝑣55, 𝛌61 + 𝑣65)
= min(0+ ∞, 7+1, 8+∞, ∞+∞, ∞+0, ∞+3) = 8
𝛌62 = 𝛌61+1 = min( 𝛌11+𝑣16, 𝛌21+𝑣26, 𝛌31+𝑣36, 𝛌41+𝑣46, 𝛌51+𝑣56, 𝛌61 + 𝑣66)
= min(0+ ∞, 7+∞, 8+2, ∞+∞, ∞+∞, ∞+0) = 10
k=3
𝛌13 = 𝛌12+1 = min( 𝛌12+𝑣11, 𝛌22 + 𝑣21, 𝛌32 + 𝑣31, 𝛌42 + 𝑣41, 𝛌52 + 𝑣51, 𝛌62 + 𝑣61)

28
= min(0+0, 7+ ∞, 8+∞, 3+∞, 8+∞, 10+∞) = 0
𝛌23 = 𝛌22+1 = min( 𝛌12+𝑣12, 𝛌22+𝑣22, 𝛌32+𝑣32, 𝛌42+𝑣42, 𝛌52+𝑣52, 𝛌62 + 𝑣62)
= min(0+ 7, 7+0, 8+ 2, 3+∞, 8+∞, 10+∞) = 7
𝛌33 = 𝛌32+1 = min( 𝛌12+𝑣13, 𝛌22+𝑣23, 𝛌32+𝑣33, 𝛌42+𝑣43, 𝛌52+𝑣53, 𝛌62 + 𝑣63)
= min(0+ 8, 7+∞, 8+0, 3+∞, 8+(-2), 10+∞) = 6
𝛌43 = 𝛌42+1 = min( 𝛌12+𝑣14, 𝛌22+𝑣24, 𝛌32+𝑣34, 𝛌42+𝑣44, 𝛌52+𝑣54, 𝛌62 + 𝑣64)
= min(0+ ∞, 7+(-4), 8+∞, 3+0, 8+2, 10+∞) = 3
𝛌53 = 𝛌52+1 = min( 𝛌12+𝑣15, 𝛌22+𝑣25, 𝛌32+𝑣35, 𝛌42+𝑣45, 𝛌52+𝑣55, 𝛌62 + 𝑣65)
= min(0+ ∞, 7+1, 8+∞, ∞+2, 8+0, 10+3 ) = 8
𝛌63 = 𝛌62+1 = min( 𝛌12+𝑣16, 𝛌22+𝑣26, 𝛌31+𝑣36, 𝛌41+𝑣46, 𝛌51+𝑣56, 𝛌61 + 𝑣66)
= min(0+ ∞, 7+∞, 8+2, 3+∞, 8+∞, 10+0) = 10
k=4
𝛌14 = 𝛌13+1 = min( 𝛌13+𝑣11, 𝛌23 + 𝑣21, 𝛌33 + 𝑣31, 𝛌43 + 𝑣41, 𝛌53 + 𝑣51, 𝛌63 + 𝑣61)
= min(0+ 0, 7+ ∞, 8+∞, 3+∞, 8+∞, 10+ ∞) = 0
𝛌24 = 𝛌23+1 = min( 𝛌13+𝑣12, 𝛌23+𝑣22, 𝛌33+𝑣32, 𝛌43+𝑣42, 𝛌53+𝑣52, 𝛌63 + 𝑣62)
= min(0+ 7, 7+0, 8+2, 3+ ∞, 8+∞, 10+ ∞)=7
𝛌34 = 𝛌33+1 = min( 𝛌13+𝑣13, 𝛌23+𝑣23, 𝛌33+𝑣33, 𝛌43+𝑣43, 𝛌53+𝑣53, 𝛌63 + 𝑣63)
= min(0+ 8, 7+ ∞, 6+0, 3+ ∞, 8+(-2), 10+ ∞) = 6
𝛌44 = 𝛌43+1 = min( 𝛌13+𝑣14, 𝛌23+𝑣24, 𝛌33+𝑣34, 𝛌43+𝑣44, 𝛌53+𝑣54, 𝛌63 + 𝑣64)
= min( 0+∞, 7+(-4), 6+ ∞, 3+0, 8+2, 10+ ∞) = 3
𝛌54 = 𝛌53+1 = min( 𝛌13+𝑣15, 𝛌23+𝑣25, 𝛌33+𝑣35, 𝛌43+𝑣45, 𝛌53+𝑣55, 𝛌63 + 𝑣65)
=min( 0+∞, 7+1, 6+ ∞, 3+∞, 8+0, 10+3) = 8
𝛌64 = 𝛌63+1 = min( 𝛌13+𝑣16, 𝛌23+𝑣26, 𝛌33+𝑣36, 𝛌43+𝑣46, 𝛌53+𝑣56, 𝛌63 + 𝑣66)
= min(0+ ∞, 7+∞, 6+2, 3+∞, 8+∞, 10+0) = 8
k=5
𝛌15 = 𝛌14+1 = min( 𝛌14+𝑣11, 𝛌24 + 𝑣21, 𝛌34 + 𝑣31, 𝛌44 + 𝑣41, 𝛌54 + 𝑣51, 𝛌64 + 𝑣61)
= min(0+ 0, 7+ ∞, 6+∞, 3+∞, 8+∞, 8+∞) = 0

29
𝛌25 = 𝛌23+1 = min( 𝛌14+𝑣12, 𝛌24+𝑣22, 𝛌34+𝑣32, 𝛌44+𝑣42, 𝛌54+𝑣52, 𝛌64 + 𝑣62)
= min(0+ 7, 7+0, 6+2, 3+ ∞, 8+∞, 8+∞)=7
𝛌35 = 𝛌34+1 = min( 𝛌14+𝑣13, 𝛌24+𝑣23, 𝛌34+𝑣33, 𝛌44+𝑣43, 𝛌54+𝑣53, 𝛌64 + 𝑣63)
= min(0+ 8, 7+ ∞, 6+0, 3+ ∞, 8+(-2), 8+∞) = 6
𝛌45 = 𝛌44+1 = min( 𝛌14+𝑣14, 𝛌24+𝑣24, 𝛌34+𝑣34, 𝛌44+𝑣44, 𝛌54+𝑣54, 𝛌64 + 𝑣64)
= min( 0+∞, 7+(-4), 6+ ∞, 3+0, 8+2, 8+∞) = 3
𝛌55 = 𝛌54+1 = min( 𝛌14+𝑣15, 𝛌24+𝑣25, 𝛌34+𝑣35, 𝛌44+𝑣45, 𝛌54+𝑣55, 𝛌64 + 𝑣65)
=min( 0+∞, 7+1, 6+ ∞, 3+∞, 8+0, 8+3) = 8
𝛌65 = 𝛌64+1 = min( 𝛌14+𝑣16, 𝛌24+𝑣26, 𝛌34+𝑣36, 𝛌44+𝑣46, 𝛌54+𝑣56, 𝛌64 + 𝑣66)
= min(0+ ∞, 7+∞, 6+2, 3+∞, 8+∞, 8+0) = 8
În urma calculelor de mai sus, am determinat matricea valorilor 𝛌𝑖𝑘 :

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 matricei 𝛌𝑖𝑘 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.
În concluzie, analizând rezultatele din tabel , se poate spune că distan ța
minimă de la 1 la 6 este 8 pe traseul (1,2,5,3,6).
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;

30
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ă ”;
3.3. Algoritm de determinare a valorilor maxime de drumuri de la
un vârf dat
Dacă pentru determinarea valorilor minime de drumuri de la un vârf dat
am folosit algoritmul Bellman -Kalaba, în cazul determin ării valorilor
maxime de drumuri de la un vârf dat folosesc algoritmul 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 :
𝑣𝑖𝑗 = {
Voi aplica algoritmul Roy-Floyd pentru graful de mai jos:

0, dacă i=j
l((𝑋𝑖,𝑋𝑗)), dacă ( 𝑋𝑖,𝑋𝑗) ∈ U
-∞, dacă (𝑋𝑖,𝑋𝑗) ∉ U și i ≠ j

31

Matricea valorilor arcelor este:

Se observ ă că această matrice este asemănătoare matricei costurilor
atașată graficului pentru determinarea drumurilor minime, cu diferen ța
că pentru perechi de vârfuri 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 există drum de la 𝑋𝑖 la 𝑋𝑗,
putem utiliza următorul algoritm :
Fie M matricea definită mai sus, iar D= (𝑑𝑖𝑗)𝑛𝑋𝑛 cu

𝑑𝑖𝑗 =

Mai jos prezint adaptarea algoritmului Roy -Floyd sub forma unui
pseudocod:
Pentru k:=1,n execută
Pentru i :=1,n ( i ≠ k) execută
Pentru j:=1,n ( j ≠ k) execută
Dacă 𝑚𝑖𝑗 < 𝑚𝑖𝑘 + 𝑚𝑘𝑗
Atunci
𝑚𝑖𝑗 := 𝑚𝑖𝑘 + 𝑚𝑘𝑗
𝑑𝑖𝑗 := 𝑑𝑘𝑗
Altfel 0 7 8 -∞ -∞ -∞
-∞ 0 -∞ -4 1 -∞
-∞ 2 0 -∞ -∞ 2
-∞ -∞ -∞ 0 -∞ -∞
-∞ -∞ -2 2 0 -∞
-∞ -∞ -∞ -∞ 3 0
{𝑋𝑖 }, dacă 𝑚𝑖𝑗 > -∞ și i ≠ j
Φ, dacă 𝑚𝑖𝑗 = -∞ sau i=j
{

32
Dacă 𝑚𝑖𝑗 := 𝑚𝑖𝑘 + 𝑚𝑘𝑗
Atunci
𝑑𝑖𝑗 := 𝑑𝑖𝑗 ∪ 𝑑𝑘𝑗
Sfârșit dac ă
Sfârșit dac ă
Sfârșit pentru
Sfârșit pentru
Sfârșit pentru

Pentru determinarea drumurilor maxime , se realiz ează următoarele
calcule:
𝑑11 = 𝑑22 = 𝑑33 = 𝑑44 = 𝑑55 = 𝑑66 = Φ
𝑑12 : 𝑚12( 7) < 𝑚13 (8) + 𝑚32 (2) = 10 – Adevărat = > 𝑚12 = 𝑚13 + 𝑚32
 𝑚12 = 8+2 = 10, iar 𝑑12={1,3,2}
𝑑13 ={1,3} ( 𝑚13=8)
𝑑14: 𝑚14( −∞) < 𝑚12 (7) + 𝑚24 (−4) = 3 – Adevărat = > 𝑚14 = 𝑚12 +
𝑚24  𝑚14 = 7-4 = 3, iar 𝑑14={1,2,4}
𝑑15: 𝑚15( −∞) < 𝑚12 (7) + 𝑚25 (1) = 8 – Adevărat => 𝑚15 = 𝑚12 + 𝑚25
 𝑚15 = 7+1 = 8, iar 𝑑15={1,2,5}
𝑑16: 𝑚16( −∞) < 𝑚13 (8) + 𝑚36 (2) = 10 – Adevărat => 𝑚16 = 𝑚13 + 𝑚36
 𝑚16 = 8+2 = 10, iar 𝑑16={1,3,6}

𝑚21 = -∞ => 𝑑21 = Φ
𝑑23: 𝑚23( −∞) < 𝑚25 (1) + 𝑚53 (−2) = -1 – Adevărat = > 𝑚23 = 𝑚25 +
𝑚53  𝑚14 = 1-2=-1, iar 𝑑23={2,5,3}
𝑑24: 𝑚24( −4) < 𝑚25 (1) + 𝑚54 (2) = 3 – Adevărat = > 𝑚24 = 𝑚25 + 𝑚54
 𝑚24 = 1+3=4, iar 𝑑23={2,5,4}
𝑑25 ={2,5} ( 𝑚25=1)
𝑚26 = -∞ => 𝑑26 = Φ

33
𝑚31 = -∞ => 𝑑31 = Φ
𝑑32 ={3,2} ( 𝑚32=2)
𝑑36 ={3,6} ( 𝑚36=2)
𝑑35: 𝑚35( −∞) < 𝑚36 (2) + 𝑚65 (3) = 5 – Adevărat = > 𝑚35 = 𝑚36 + 𝑚65
 𝑚35 = 2+3=5, iar 𝑑35={3,6,5}
𝑑34: 𝑚34( −∞) < 𝑚35 (−2) + 𝑚54 (2) = 7 – Adevărat = > 𝑚34 = 𝑚35 + 𝑚54
 𝑚34 = 5+2=7, iar 𝑑35={3,6,5,4}

𝑚41 = 𝑚42 = 𝑚43= 𝑚45= 𝑚46= -∞ => 𝑑41 = 𝑑42= 𝑑43= 𝑑45= 𝑑46= Φ

𝑚51 = -∞ => 𝑑51 = Φ
𝑑52: 𝑚52( −∞) < 𝑚53 (−2) + 𝑚32 (2) = 0 – Adevărat = > 𝑚52 = 𝑚53 + 𝑚32
 𝑚52 = -2+2=0 iar 𝑑52={5,3,2}
𝑑53 ={5,3} ( 𝑚53=-2)
𝑑54 ={5,4} ( 𝑚54=2)
𝑑56: 𝑚56( −∞) < 𝑚53 (−2) + 𝑚36 (2) = 0 – Adevărat = > 𝑚56 = 𝑚53 + 𝑚36
 𝑚56 = -2+2=0 iar 𝑑56={5,3,6}

𝑚61 = -∞ => 𝑑61 = Φ
𝑑65 ={6,5} ( 𝑚65=3)
𝑑63: 𝑚63( −∞) < 𝑚65 (3) + 𝑚53 (−2) = 0 – Adevărat = > 𝑚63 = 𝑚65 + 𝑚53
 𝑚65 = 3-2=1 iar 𝑑52={6,5,3}
𝑑62: 𝑚62( −∞) < 𝑚63 (1) + 𝑚32 (2) = 3 – Adevărat = > 𝑚62 = 𝑚63 + 𝑚32
 𝑚52 = 1+2=3 iar 𝑑52={6,5,3,2}
𝑑64: 𝑚64( −∞) < 𝑚65 (3) + 𝑚54 (2) = 5 – Adevărat = > 𝑚64 = 𝑚65 + 𝑚54
 𝑚64 = 3+2=5 iar 𝑑64={6,5,4}

În concluzie, realizând calculele de mai sus, pot spune că 𝑚𝑖𝑗 este
lungimea maximă a drumurilor dintre vârfurile i și j, iar 𝑑𝑖𝑗 este mulțimea
vârfurilor ce formează drumurile maxime.

34
Astfel, de exemplu, între nodul ini țial (1) și cel final (6), distan ța
maxim ă este 𝑚16 = 10, iar 𝑑16 = {1,3,6}, ce ea ce înseamnă că drumul
de lungime maximă de la 1 la 6 trece prin vârfurile 1,3 și 6.
În baza celor de mai sus, putem realiza un cod în format C++ de
determinare a drumurilor maxime :
“fragment din program de determinare a drumurilor maxime unui graf
G=(X,U) cu U={1,2,..,n} ”
=============================
void citire ()
/* initializeaza matricea costurilor */
{
int arc,i,j,u, v,l;
cin>>n; /* numarul de varfuri */
for(i=1;i<= n;i++)
{
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 predecesorilor d */
{
int i,j;

35
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)
/* 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]<<" ";
}
}

36
void afisare()
/* afiseaza rezultatele */
{
int i,j,l;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
cout<<" \n";
if(c[i][j]==INF)
cout<<"nu exista drum de la "<<i<<" la "<<j;
else
{
cout<<"lungimea drumurilor maxime 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++)

37
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(c[i][j]<c[i][k]+c[k][j])
{
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();
}

38
3.4. Aplicație practică în vederea determinării unui drum minim
O companie de turism international inten ționeaz ă să organizeze un
traseu turistic, av ând trei componente: aerian, terestru și maritim.
Dacă pentru transportul aerian și sejurul maritim ofertele de pret au
fost cerute companiilor de transport si leisure specializate, pentru
circuitul terestru a contactat o companie locală căreia i -a cerut să -i
determine drumurile optime pe zona de interes dintre aeroport si portul
maritim, oferindu -i următoarele date:
• Locatia aeroportului unde vor sosi turi știi
• Portul de ambarcare a turistilor după terminarea traseului terestru
• Punctele de interes care ar putea fi atinse / incluse în traseu
• Cheltuielile în punctele de interes sunt aproximativ egale

Costurile drumurilor precum și poziționarea punctelor de interes sunt date
în gra ful din figura de mai jos, unde 1 este vârful de pornire iar 8 este
vârful terminal

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

39
Drumurile optime, cu un cost total minim, sunt date de cele de valoare
minimă în graful dat. Pentru determinarea drumului de valoare minimă,
se va folosi algoritmul Bellman -Kalaba.
Matricea V a valorilor arcelor este:

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

Pentru determinarea matricei valorilor 𝛌𝑖𝑘, realizăm următoarele
calcule:
𝛌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.

40

𝛌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]=17;

𝛌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+11, ∞+14, ∞+17]=11;
𝛌74 = min[ ∞+0, 13+1, 14+3, ∞+5, ∞+8, 2+11, 0+14, ∞+17]=13;
𝛌84 = min[ ∞+0, ∞+1, ∞+3, 15+5, 9+8, 6+11, 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+11, ∞+13, ∞+17]=11;
𝛌75 = min[ ∞+0, 13+1, 14+3, ∞+5, ∞+8, 2+11, 0+13, ∞+17]=13;
𝛌85 = min[ ∞+0, ∞+1, ∞+3, 15+5, 9+8, 6+11, 4+13,0+17]=17.

În urma calculelor de mai sus, am determinat matricea valorilor 𝛌𝑖𝑘 :

41
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

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 descr escătoare ce ne
conduc de la 8 la fiecare vârf 𝑋𝑖.
Alegem în componen ța drumurilor minime v ârfurile : 1, 2, 3, 4, 5, 6, 7,
8. Astfel obținem drumurile de mai jos, care da u câte un plan al
traseului, cu un cost total minim:
• A – (1,2,3,5, 6,7,8)
• B – (1,3,5,6,7,8)
• C – (1,2,3,5,6,8)
• D – (1,2,3,5,8)
• E – (1,3,5,6,8)
• F – (1,3,5,8)

42
4. 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,55),(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 drumurilor dintre acestea.
h.show() – afișează graful cu v ârfurile și arcele sale.

h.show(edge_labels=True) – afișează graful cu v ârfurile, arcele și
distanțele atașate pe acestea.

43

h.adjacency_matrix() – afișează matricea de adiacen ță – un element
din matrice ia valoarea 1 dac ă există drum direct între dou ă vârfuri și 0
în caz contrar.

h.weighted_adjacency_matrix() – afișează matricea distan țelor – dacă
există drum direct între dou ă vârfuri, elementul aferent matricei ia
valoarea distanței, în caz contrar ia valoarea 0.

44
h.connected_components() – afișează componetele conexe ale grafului.
În cazul nostru există una singură.
[[1, 2, 3, 4, 5, 6, 7, 8]]

h.strongly_connected_components() – afișează componetele tari
conexe ale grafului. În cazul nostru exist ă 8 componente tari conexe.
[[8],[7],[6],[5],[4],[3],[2],[1] ]

h.shortest_path (1,8 , True) – afișează drumul de lungime minim ă între
primul și ultimul nod.
[1, 2, 3, 5, 8]

h.all_paths(1,8) – afișează toate drumurile între primul și ultimul nod.
[[1, 2, 3, 4, 8], [1, 2, 3, 4, 5, 8], [1, 2, 3, 4, 5, 6, 8], [1, 2, 3, 4, 5, 6,
7, 8], [1, 2, 3, 4, 6, 8], [1, 2, 3, 4, 6, 7, 8], [1, 2, 3, 5, 8], [1, 2, 3, 5,
6, 8], [1, 2, 3, 5, 6, 7, 8], [1, 2, 3, 6, 8], [1, 2, 3, 6, 7, 8], [1, 2, 3, 7,
8], [1, 2, 7, 8], [1, 3, 4, 8], [1, 3, 4, 5, 8], [1, 3, 4, 5, 6, 8], [1, 3, 4,
5, 6, 7, 8], [1, 3, 4, 6, 8], [1, 3, 4, 6, 7, 8], [1, 3, 5, 8], [1, 3, 5, 6, 8],
[1, 3, 5, 6, 7, 8], [1, 3, 6, 8], [1, 3, 6, 7, 8], [1, 3, 7, 8 ], [1, 4, 8], [1,
4, 5, 8], [1, 4, 5, 6, 8], [1, 4, 5, 6, 7, 8], [1, 4, 6, 8], [1, 4, 6, 7, 8]]

h.shortest_path_length(1,8,True) – afișează lungimea drumului minim
între primul și ultimul nod.
17

h.longest_path(1,8,True) – afișează lungimea drumului maxim între
primul și ultimul nod, și num ărul de arce ce îl alcătuiesc.
(22, Subgraph of (): Digraph on 7 vertices)

h.distance_all_pairs(True) – afișează toate perechile de drumuri
minime realizate nod cu nod și lungimile aferente.

45
{1: {1: 0, 2: 1, 3: 3, 4: 5, 5: 8, 6: 11, 7: 13, 8: 17}, 2: {2: 0, 3: 2, 4:
6, 5: 7, 6: 10, 7: 12, 8: 16}, 3: {3: 0, 4: 4, 5: 5, 6: 8, 7: 10, 8: 14},
4: {8: 14, 4: 0, 5: 6, 6: 8, 7: 10}, 5: {8: 9, 5: 0, 6: 3, 7: 5}, 6: {8: 6,
6: 0, 7: 2}, 7: {8: 4, 7: 0}, 8: { 8: 0}}

h.shortest_paths(1, True) – afișează toate perechile de drumuri minime
realizate de nodul 1 cu fiecare nod din graf.
{1: [1], 2: [1, 2], 3: [1, 3], 4: [1, 4], 5: [1, 3, 5], 6: [1, 3, 5, 6], 7:
[1, 3, 5, 6, 7], 8: [1, 3, 5, 8]}

h.neighbors(1) – afișează nodurile terminale ale arcelor ce pleac ă din 1
[2, 3, 4]
h.neighbors(2) – afișează nodurile terminale ale arcelor ce pleac ă din 2
[1, 3, 7]
h.neighbors(3) – afișează nodurile terminale ale arcelor ce pleac ă din 3
[1, 2, 4, 5, 6, 7]
h.neighbors(4) – afișează nodurile terminale ale arcelor ce pleac ă din 4
[8, 1, 3, 5, 6]
h.neighbors(5) – afișează nodurile terminale ale arcelor ce pleac ă din 5
[8, 3, 4, 6]
h.neighbors(6) – afișează nodurile terminale ale arcelor ce pleac ă din 6
[8, 3, 4, 5, 7]
h.neighbo rs(7) – afișează nodurile terminale ale arcelor ce pleac ă din 7
[8, 2, 3, 6]
h.neighbors(8) – afișează nodurile terminale ale arcelor ce pleac ă din 8
[4, 5, 6, 7]

46
5. Concluzii

Realizând opera țiile din cadrul algoritmicii grafurilor, se poate trage concluzia
că acestea au una dintre cele mai mari aplicabilită ți în varii domenii, fiind
folosite ca bază în dezvoltarea de modele matematice / informatice pentru
cercetare, proiectare, dezvoltare sau analiză.
Ca exemplificare, mai jos redăm următoarele domenii :

 În sectorul business se folosesc pentru:
o previziuni financiare
o controlul proceselor industriale
o cercetări de pia ță
o validări de date pe bază de clasificări și de tipare
o managementul riscului
o previziuni de marketing

 Chimie – se folosesc grafurile
moleculare care reprezintă modele ale
unui sistem chimic, utilizate pentru
caracterizarea interac țiunii
componentelor sale: atomi, legături,
grupuri de atomi sau molecule.

 Sociologie
o Rețele sociale ( facebook )
o Elaborarea de modele pentru
efectuarea de studii
sociologice cu privire la
recens ământul popula ției,
apartenen țele politice și opțiuni
electorale
o Reprezentarea arborelui
genealogic

47

 Rețele de transport na țional și interna țional
o Transport terestru ( auto și feroviar )
o Transport aerian

 Informatică
o Rețele de calculatoare
o Circuite electronice

Finalmente, citez din Grigore C. Moisil : “Azi teoria grafurilor a devenit o
disciplin ă major ă, deși nu-și găsește locul într-o clasificare dogmatic ă a
capitolelor matematicii. Folosirea teoriei grafurilor în domenii variate, de la
chimie, la economie, de la studiul rețelelor electrice la critica textelor și la
politică, îi dau azi un prestigiu de care cel ce clasifică șt iințele tr ebuie să țină
seama”.

 Urbanism
o Rețele de străzi
o Rețele de utilități (apă,
canalizare, iluminat public,
gaze etc.)
o Rețele de transport public

48
6. Bibliografie

[1] Suport de curs, Conf. Univ. D r. Cristina FLAUT
[2] Alfred V. Aho, Jeffrey D. Ullman, Foundations of Computer Science,
Computer Science Press, New York, 1995.
[3] J. Bang -Jensen, G. Goutin, Digraphs: Theory, Algorithms and Applications,
Springer -Verlag, London, 2000.
[4] C. Berge, Théorie des graphes et ses applications, Dunod, Paris, 1967.
[5] Nicolae Rădescu, Eugenia Rădescu, Probleme de teoria grafurilor, Scrisul
Romanesc, Craiova, 1982.
[6] E. Tanaguchi, City l ogistic, Pergamon, Amsterdam, 2001.
[7] I. Tomescu, Combinatorică și Teoria Grafurilor, București, 1978.
[8] http://www.cursuri.flexform .ro/courses/L2/document/Cluj –
Napoca/grupa6/Contras_Diana/site/
[9] http://harti.tramclub.org/constanta -iul11.jpg
[10] https://www.teoalida.ro/harti/cfr/cfr1992 -93.jpg
[11] https://fest -bilet.ru/ro/snaryazhenie/tehnicheskie -i-nauch nye-
dostizheniya -actekov -drevnyaya -civilizaciya -actekov -desyat.html
[12] https://www.bbvaopenmind.com/en/science/mathematics/william –
hamilton -the-mathematical -vandal -who-invented -board -game/
[13] http://tourex.ro/bilete -de-avion -2/
[14]
http://www.gsaranyjanos.ro/Files/pages/pages_iskola/erasmus/informatika/s
uport/sup14.pdf
[15] http://chim.upt.ro/_old/comunicate -cadre/96370spectro_Intro+UV –
VIZ.pdf