Introducere … … … … 2 [625256]

1 Cuprins
Introducere ………………………….. ………………………….. ………………………….. …………… 2
Capitolul I ………………………….. ………………………….. ………………………….. …………….. 3
Elemente de teoria grafurilor ………………………….. ………………………….. …………….. 3
1. 1. Grafuri orientate – Noțiuni de bază ………………………….. ………………………….. ………………………….. …3
1. 2. Matrici ata șate unui graf ………………………….. ………………………….. ………………………….. ………………. 8
Capitolul II ………………………….. ………………………….. ………………………….. …………. 10
Algoritmi pentru rezolvarea unor probleme relative la grafuri ………………….. 10
2. 1. Algoritmul lui Yu Chen pent ru aflarea matricei drumurilor ………………………….. ……………………… 10
2. 2. Algoritmi pentru precizarea existenței circuitelor într -un graf ………………………….. …………………. 11
2. 3. Algoritmi pentru aflarea componentelor tare conexe ale unui graf ………………………….. ………….. 12
2. 4. Drumuri și circuite hamiltoniene ………………………….. ………………………….. ………………………….. …. 16
Capitolul III ………………………….. ………………………….. ………………………….. ………… 24
Rezolvarea unor probleme relative la drumuri de v aloare optimă ……………… 24
3. 1. Grafuri valorizate. Principiul optimalității. ………………………….. ………………………….. ………………… 24
3. 2. Drumuri optime într -un graf. Algoritmi de găsire a drumului optim ………………………….. …………. 25
3. 2. 1. Algoritmul lui Bellman – Kalaba ………………………….. ………………………….. ………………………….. .. 25
3. 2. 2. Algoritmul lui Ford simplificat ………………………….. ………………………….. ………………………….. …. 28
3. 2. 3. Algoritmul lui Dijkstra ………………………….. ………………………….. ………………………….. ……………. 30
3.2.4. Obtinerea arborelui partial de cost minim folosind alg oritmul lui Kruskal ………………………….. .. 32
Concluzii ………………………….. ………………………….. ………………………….. …………….. 39
Bibliografie ………………………….. ………………………….. ………………………….. …………. 40
Anexa ………………………….. ………………………….. ………………………….. ………………………….. …………………. 41
Cod sursa Algoritm Kruskal ………………………….. ………………………….. ………………………….. ………………. 41

2 Introducere

În această scurtă introducere este prez entat pe scurt conținutul lucrări numită: “Algoritmi
combinatoriali”.
În prima parte avem o descriere despre grafu ri orientate cu noțiuni de bază: ce este un graf, din
ce este alcătuit graful (din mulțimi de vârfuri, numite și noduri, și mulțimi de muchii, numite și arce),
ordinul unui graf (este egal cu numărul de noduri ale grafului), ce este un graf parțial altui graf
(graful parțial se obține din graful căruia îi este parț ial prin suprimarea anumitor arce),ce este un
subgraf ( este graful însă și sau se ob ține din acel graf prin suprimarea anumitor vârfuri și a tuturor
arcelor incidente cu acestea), lanțul unui graf (un traseu care unește prin a rce două noduri numite
extremită ți), drumul uni graf ( coincide î n mare parte cu lanțul uini graf,orice drum este ș i lanț),
noțiunea de conexitate.

Despre matricile atașate uni graf: matricea conexiunilor directe (o matrice pătratică de ordin n),
valorile matricei conexiunilor directe (se poate considera ca o valoare booleana), matricea
conexiunilor totale ,matrice latin ă.

În a doua parte sunt prezentați câțiva algoritmi pentru rezolvarea unor probleme relative la
grafuri: algoritmul lui Yu Chen pentru aflarea matrici drumurilor (pași prin care se realizează acest
algoritm,un scurt exemplu), algoritmi petru precizarea existenței circuitelor într -un graf(a lgoritmul
marcării -cu pași pentru realizarea acestui algoritm si exemplificat, algoritmul matricei drumurilor ),o
scurtă preze ntare despre algoritmi pentru a flarea tare conexe ale unui graf, drumuri și circuite
hamilton iene(despre problema comis voiajo rului,o reprezentare a reginunii aprovizionate, problema
poștașului,problema adunarii deșeurilor, aplicarea algoritmului Chen pentru determinarea
drumurilo r hamiltoniene în grafuri fara circuite,algoritmul Chen pentru graf uri cu circuite).

În a treia parte sunt prezentate grafuri pentru rezolvarea unor probleme relative la drumuri de
valoare optimă: grafuri valorizate(valoarea arcului, valoarea drumului), drumuri optime î ntr-un
graf(algoritmul lui Bellman -Kalabe care gă sește drumul de valoare minimă de la toate nodurile
grafului la un nod oarecare fixat, algoritmul lui Ford simplificat -se aplică la grafuri care nu admit
circuite și este folosit pentru descoperirea drumului de valoare optimă intre două noduri fixate,
algori tmul lui Dijkstra care este o completare a algoritmului Ford deoarece păstrează, la fiecare
iterație, mulțimea minimă de noduri, pe toate cele care formează efectiv drumul optim ).

La fiecare algoritm sunt prezentați pașii de real izare a algoritmului, un exemplu și unele
demonstrati i aferente algoritmilor.

3
Capitolul I
Elemente de teoria grafurilor

1. 1. Grafuri orientate – Noțiuni de bază

Definiția 1. 1. 1. Numim graf o pereche ordonată de mulțimi , notată G=(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 sau ordonate ) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce
(dacă sunt perechi ordonate). În primul caz, graful se numește neorientat , altfel acesta este orientat.

Observația 1. 1. 1. Conform definiției 1. 1. 1., un graf orientat G este format dintr -o pereche
ordonată de mulțimi G = (X, U), ca și î n cazul grafurilor neorientate, X este mulțimea vâ rfurilor sau
nodurilor grafului. Mulț imea U este formată din perechi ordonate de elemente distincte din X,
numite arce. Orice arc u U va fi notat prin u = (x, y) cu x, yX.
Spunem ca vâ rful x este extremitatea iniț ială a arcului u, iar vârful y este extremitatea final ă
a arcului u. Spre de osebire de caz ul grafurilor neorientate, notaț iile (x,y) și (y,x) vor desemna două
arce diferite.
Daca graful G conț ine arcul (x, y) vom spune ca vâ rfurile x și y sunt adiacente în G și
amândouă sunt incidente cu arcul (x, y). Deci, un graf orientat G poate fi imaginat ca o mulț ime de
vârfuri, d intre care unele sunt unite două câte două prin arce. Un graf orientat poate fi desenat în plan
reprezentâ nd vârfurile sale prin puncte și arcele prin săgeț i care sunt o rientate de la extremitatea
inițială catre extremitatea finală a fiecarui arc , vezi exemplul 1. 1. 1 .

Exemplul 1. 1. 1. În graful din figura 1. 1. 1. mulț imea nodurilor este X = {1, 2, 3, 4, 5, 6 , 7} și
mulțimea arcelor este U={u 1, u2, u3, u4, u5, u6, u7, u8, u9, u10}={(1, 2), (2, 3), (3, 4), (4, 1), (3, 5), (5,
3), (5, 6), (6, 7), (7, 6), (7, 5)}.

Figura 1. 1. 1.

4 Definiția 1. 1. 2. Numim ordinul unui graf, numărul de noduri al grafului, deci cardinalul
mulțimii X și notăm această valoare cu | G |. Numărul de muchii se notează cu
G .

graful și se notează cu
 . Spunem că un Observația 1. 1. 2. Graful vid este
graf G este trivial dacă acesta are ordinul 0 sau 1.

un graf și
Xx un vârf. Fie

Definiția 1. 1. 3. Mulțimile
 UyxXy x  ),(: și
 UxyXy x  ),(: se
numesc mulțimea succesorilor, respectiv mulțimea predecesorilor lui x. Mulțimea
x x x  
se numește mulțimea vârfurilor adiacente lui x sau vecinătatea lui x.

Definiția 1. 1. 4. Cardinalul mulțimii
x se notează cu
xd și se numește semigradul
exterior al lui x, iar cardinalul mulțimii
x se notează cu
xd și se numește semigradul interior
al lui x. Gradul vârfului x, notat
xd , este
xdxdxd  .

Exemplul 1. 1. 2. Pentru graful din exemplul 1. 1. 1 . avem:
7 6
,
7 ,5 6 ,
7 ,5 6 .
16d
,
,26d
 3216d  .

Observ ația 1. 1. 3 . Dacă adunăm gradele tuturor nodurilor din graful G, obținem de două ori
numărul de muchii, adică:
 G xd
Xx
2

Definiția 1. 1. 5 . Un graf parțial al unui graf orientat G = (X, U) este un graf
 U. V ,,1   VX G

Observația 1. 1. 4 . Un graf parțial
1G al grafului G se obține din graful G prin suprimarea
anumitor arce.

Exemplul 1. 1. 3. Porninid de la graful G = (X, U) dat de exemplul 1. 1. 1. se pot construi
grafurile parțiale
,,i i VX G unde
i i uUV \ și
10,1i

Definiția 1. 1. 6 . Un subgraf al lui G este un graf H = (Y, V), unde Y X, iar arcele din V sunt
toate arcele din U care au ambele extremițați în mulțimea de vâ rfuri Y.

Observația 1. 1. 5 . Deci un subgraf H al unui graf orientat G , este graful G î nsuși , sau se obține
din G , prin suprimarea anumitor vârfuri ș i a tutur or arcelor incidente cu acestea .Vom spune ca
subgraful H este indus sau generat de mulțimea de vâ rfuri Y.
,G
UX G ,

5
Exemplul 1. 1. 4. Porninid de la graful G = (X, U) dat de exemplul 1. 1. 1. se po ate construi
subgraful
VY H , , unde Y={1, 2, 3, 4, 5} și V={(1, 2), (2, 3), (3, 4), (4, 1), (3, 5), (5, 3)}={
,1u
,2u

,3u
,4u
,5u
6u}, vezi figura 1. 1. 2.
Definiția 1. 1. 7. Un graf orientat este complet dacă oricare două vârfuri sunt adiacente.

Definiția 1. 1. 8. Un lanț al unui graf orientat
UX G , se definește ca un șir de arce L = [
1u
,
2u, . . . , up], cu proprietatea că oricare arc
iu din acest șir are comună o extremitate cu
1iu, iar
cealaltă extremitate este comună cu
1iu pentru orice i = 2 , . . . , p-1.

Observația 1. 1. 6 . Altfel spus, un lanț este un traseu care unește prin arce două noduri numite
extremitățile lanțului, fără a ține cont de orientarea arcelor componente.

Definiția 1. 1. 9. Un drum într -un graf orientat G = (X, U) , este un șir de vârfuri notat :
D = (
0x ,
1x, . . . ,
rx ), cu proprietatea că (
0x,
1x), (
1x ,
2x), . . . , (
1rx ,
rx)U, deci sunt arce ale
grafului. Vârfurile
0x si
rx se numesc extremitățile drumului D. Dacă vârfurile
0x ,
1x, . . . ,
rx sunt
distincte două câte două, drumul D se numește eleme ntar.

Observația 1. 1. 7 . Din aceste definiții rezultă ca orice drum este și lanț, dacă îl privim ca pe un
șir de arce. Dacă toate arcele lanțului L au aceeași orientare, care este dată de sensul deplasării de la
x0 către x r, lanțul L este un drum. Un drum D = (
0x, … ,
rx) poate fi interpretat ca fiind traseul unei
deplasări , pe arcele grafului , în ordinea (
0x ,
1x), (
1x ,
2x), . . . , (
1rx ,
rx).

Definiția 1. 1. 10. Fie drumul D = (
0x ,
1x, . . . ,
rx ), dacă x 0 =
rx și toate arcele (
0x ,
1x), (
1x ,
2x
), . . . ,(
1rx ,
rx) sunt distincte două câte două, drumul D se numește circuit. Dacă toate vârfurile
circuitului, cu excepția primului și a ultimului vârf, sunt distincte două câte două, circuitul se
numește elementar.

Exemplul 1. 1. 5. L = [u 1, u2,
10 5u ,u ] este lanț în graful din exemplul 1. 1. 1.
 5 7, 6, 5, 3, 2, ,11D
este drum în graful din exemplul 1. 1. 1. Figura 1. 1. 2.

6
 7 6, 5, 3, 2, ,12D este drum elementar în graful din exemplul 1. 1. 1.
 1 4, 3, 5, 3, 2, ,11C
este circuit în graful din exemplul 1. 1. 1.
1 4, 3, 2, ,12C
este circuit elementar în graful din exemplul 1. 1. 1.
Noțiunile de conexitate și de componentă conexă a unui graf orientat sunt similare cu c ele de la
grafurile neorientate, utilizând noțiunea de lanț din cazul grafurilor orientate.
Definiția 1. 1. 11. Un graf
UX G , este conex, dacă oricare ar fi două vârfuri ale sale, există
un lanț care le leagă.
Exemplul 1. 1. 6 . Graful din figura 1. 1. 3. este co nex, pentru că oricum am lua două noduri
putem ajunge de la unul la celalalt pe un traseu de tip lanț.

Exemplul 1. 1. 7 . Graful din figura 1. 1. 4. nu este conex , pentru că de la vârful 2 la vârful 6 , nu
putem ajunge pe un traseu de tip lanț.

Figura 1. 1. 3.
Figura 1. 1. 4.

7
Definiția 1. 1. 1 2. O componentă conexă C , a unui graf orientat G , se definește ca fiind un
subgraf conex maximal al lui G, deci nu există nici un lanț care să unească un vârf din C cu un vârf
care nu aparține lui C.

Exemplul 1. 1. 8 . În graful din figura 1. 1. 4. distingem două componente conexe: G1 = (X 1,U1),
unde X 1={1, 2, 3}, U 1={u 1, u2, u3} și G 2 = (X 2, U2), unde X 2={4,5,6}, U 2={u 4, u5}.

Definiția 1. 1. 1 3. Un graf orientat G = (X, U) este tare conex dacă pentru oricare două noduri x
și y care aparțin lui X, există un drum de la x la y precum și un drum de la y la x.

Exemplul 1. 1. 9 . Graful cu n =3 din figura 1. 1. 5. este tare conex.
Pentr u a demonstra acest lucru, formă m toate perechile posibile de noduri distincte (x, y) cu x,
y Є{1, 2, 3} și pentru fiecare astfel de per eche, căutăm un drum de la x la y și un drum de la y la x.
x =1, y = 2
De la 1 la 2 – drumul (1, 3, 2) , pe arcele (1, 3) și (3, 2);
De la 2 la 1 – drumul (2, 3, 1) , pe arcele (2, 3) și (3, 1).
x =1, y =3
De la 1 la 3 – drumul (1, 2, 3) , pe arcele (1, 2) și (2, 3);
De la 3 la 1 – drumul (3, 2, 1) , pe arcele (3, 2) și (2, 1).
x =2, y =3
De la 2 la 3 – drumul (2, 1, 3) , pe arcele (2, 1) și (1, 3);
De la 3 la 2 – drumul (3, 1, 2) , pe arcele (3, 1) și (1, 2).

Observația 1. 1. 8 . Pentru grafurile orientate , conexitatea tare implică conexitatea simplă, adică
orice graf tare conex este și conex.Figura 1. 1. 5.

8
Definiția 1. 1. 1 4. Se numește componentă tare conexă a grafului
UX G , , un subgraf
VY GY ,
al lui G , care este tare conex și este maximal în raport cu incluziunea față de
această proprietate, adică
YXx \ subgraful lui G , genera t de
x Y , nu este tare conex.

Exemplu l 1. 1. 10 . În graful din figura 1. 1. 4. distingem o componentă tare conexă : G1 =
(X1, U1), unde X 1={1, 2, 3}, U 1={u 1, u2, u3}.

Fie
UX G , un graf orientat și relația binară definită pe X astfel:
yx yx ~ sau
există un drum de la x la y și un drum de la y la x.

Propoziția 1. 1. 1. În codițiile de mai sus are loc:
Relația binară definită mai sus este relație de echivalență ;
Clasele de echivalență sunt componente tare conexe ale grafului G .

Demonstrație. a)
,~xx deoarece
xx de unde avem ca relația binară ~ este reflexivă (1),
se mai observă ca dacă
,~yx atunci
yx sau există un drum de la x la y și un drum de la y la x
de unde avem că
,~xy deci relația binară ~ este simetrică (2). Fie acum
yx~ și
zy~
deducem că
zx sau există un drum de la x la z și un drum de la z la x, adică
zx~ și deci
relația binară ~ este tranzitivă (3). Din (1), (2) și (3) avem că relația binară ~ este o relație de
echivalență pe X.
b) Dacă notăm cu
^
x clasa de echivalență a vârfului x în raport cu relația de echivalență ~ ,
observăm fără dificultate ca graful indus de mulțimea
^
x verifică definiția componentei tare
conexe a unui graf.

1. 2. Matrici ata șate unui graf

Fie G = ( X, U) un graf orientat, f init cu mulțimea vârfurilor X={x
1 , x
2, . . . , x
n }.

Definiția 1. 2. 1 . Se numește matricea conexiunilor directe (matricea arcelor, matricea de
adiacență) asociată grafului G o matrice pătratică de ordin n, notată:
 n ji aAij ,1,cu   , unde:

 

U xU x
a
jj
ij,x dacă ,0,x dacă ,1
ii

Observația 1. 2. 1. Valorile matricei conexiunilor direct e se pot considera ca valorile
booleene și deci elementul
ija precizează dacă perechea de vârfuri
j ixx, este sau nu arc
(muchie) în graful reprezentat prin matricea de adiacență A .
Exemplul 1. 2. 1. Fie G = ( X, U) graful din figura 1. 2. 1.

Figura 1. 2. 1.

9
Matricea booleană atașat ă grafului este:

Definiția 1. 2. 2 . Se numește matricea conexiunilor totale (matricea drumurilor) asociată
grafului G o matrice notată:
 n1,ji,cu  ijd D , unde:



j ij i
xla xla de drum nu dacă ,0 xla xla de drum dacă ,1
ijd

Exemplul 1. 2. 2. Pentru graful din figura 1. 2. 1. matricea drumurilor este:

Observația 1. 2. 2. Dacă două grafuri au aceeași mulțime de vârfuri și aceeași matrice a
arcelor, atunci cele două grafuri coincid.
Dacă două grafuri au aceeași mulțime de vârfuri și aceeași matrice a drumurilor, nu rezultă
că cele două grafuri coincid (nu este obligatoriu să aibă și aceleași arce).

Definiția 1. 2. 3 . Se numește matricea latină asociată grafului G o matrice pătratică de ordin
n, notată: , unde:

Exemplul 1. 2. 3. Pentru graful din figura 1. 2. 1. matricea latină este:

 n ji lLij ,1,cu  

 

U xU x xx
l
jj ji
ij,x dacă ,0,x dacă ,
ii

10
Capitolul II

Algoritmi pentru rezolvarea unor probleme relative la grafuri

2. 1. Algoritmul lui Yu Chen pentru aflarea matricei drumurilor

În asigurarea unor algoritmi relativi la probleme de teoria grafurilor avem nevoie de
operațiile de adunare booleană

 și înmulțire booleană

 , definite după cum urmează :

Algoritmul lui Yu Chen , are următorii pași:
Pasul 1. Se scrie matricea booleană A a grafului G = (X, U);
Pasul 2. Se adună boolean la prima linie toate liniile corespunzătoare la vârfurile care au
cifra 1 pe prima linie. Noile cifre de 1 care apar se marchează cu o *.
Pasul 3. Se adună boolean la linia întâi toate liniile corespunzătoare vârfurilor care au cifra 1
*
pe prima linie. Noile cifre de 1 care apar se marchează cu **. Acest pas se continuă până când
nu mai apar cifre noi de 1 pe linia întâi.
Pasul 4 . Se aplică pașii 2 și 3 la fiecare din liniile matricei booleene. În final, se obține
matricea D a drumurilor. Justificarea algoritmilor este imediată.
Exemplul 2. 1. 1. Pentru graful din figura 1. 2. 1. să aflăm matricea drumurilor, folosind
algoritmul lui Yu Chen. Scriem matricea booleană atașată grafului:

Aplicând pașii algoritmului obținem:

care este tocmai matricea găsită la exemplul 1. 2. 2.

11
2. 2. Algoritmi pentru precizarea existenței circuitelor într -un graf

Vom prezenta doi algoritmi.
Algoritmul marcării cu “*”. Pașii acestui algoritm sunt:
Pasul 1. Se marcheaz ă cu ”*” toate v ârfurile f ără succesori;
Pasul 2. Marc ăm cu ”*” toate v ârfurile ale c ăror succesori au fost marcaț i;
Pasul 3. Se continu ă procesul de la Pasul 2 p ânâ când nu mai putem face marc ări.
Dacă toate v ârfurile au fost marcate, atunci graful este f ără circuite. În caz c ă a rămas cel
puțin un v ârf nemarcat, graful dat are circuit e.

Exemplul 2. 2. 1. Să cercet ăm dac ă graful din figura 2. 1. 1. are circuite.

La pasul întâi putem marca doar vârful
7x , fiind singurul fără succesori. La pasul 2 putem
marca vârful
6x deoarece succesorul său
7x a fost marcat. Nu mai putem face marcare de vârfuri
deoarece vârfurile râmase au succesori nemarcați. Așadar, graful dat are circuite.

Algoritmul matricei drumurilor. Cum un circuit este un drum ce începe și se termină în
același vârf, rezultă că un graf va avea circuite dacă în matricea drumurilor apare cifra 1 pe
diagonala principală. Rezultă că, pentru a cerceta dacă un graf are sau nu circuite, este suficient să
găsim matricea drumurilor.

Exemplul 2. 2. 2. Să aplicăm acest algoritm la graful din figura 2. 2. 1. Scriem matricea
booleană A:

Figura 2. 2. 1.

12
Aplicând algoritmul Yu Chen pentru aflarea matricei drumurilor, obținem:

Având în D de trei ori cifra 1 pe diagonala principală, conchidem că graful are trei circuite.

2. 3. Algoritmi pentru aflarea componentelor tare conexe ale unui graf

Aflarea componentelor tare conexe ale unui graf este important ă pentru practic ă deoarece se
obține o partiț ie a grafului în subgrafele tare conexe. Proprietatea unui graf de a fi tare conex este
foarte importantă, de exemplu, în rețele de comunicații, în cadrul cărora trebuie să se ajungă în
orice moment între două puncte ale rețelei.
Algoritmul marc ării cu ”
 ”.
Pasul 1. Se marcheaz ă cu ”
 ” un v ârf în care intr ă și iese cel puț in câte un arc.
Pasul 2. Se marcheaz ă cu ”+” v ârfurile care sunt extremit ăți finale pentru arce care pleac ă
dintr -un vârf marcat cu ”+” și se marcheaz ă cu ”–” vârfurile inițiale pentru arce ale c ăror v ârfuri
finale sunt marcate cu ” –”.
Pasul 3. Se aplic ă repetat pasu l 2, p ână nu se mai pot face marc ări. Dac ă toate v ârfurile au
fost marcate cu ”
”, atunci graful este tare conex, av ând o sigur ă component ă tare conex ă. Dacă
exist ă vârfuri care nu au fost marcate cu ”
”, atunci se consider ă mulț imea C
1 format ă din toate
vârfurile marcate cu ”
”. C
1formeaz ă o prim ă component ă tare conex ă.
Pasul 4. În graful dat se elimin ă vârfurile din componenta C
1și toate arcele aferente
acestora. Noului graf (de fapt, subgraf al grafului iniț ial) i se aplic ă paș ii 2–3 până se găsesc toate
componentele tare conexe ale grafului.
Pentru a evidenț ia geometric (intuitiv) descompunerea grafului dat în componente tare
conexe se aranjeaz ă vârfurile pe componente ș i se tr aseaz ă arcele din graful iniț ial.
Exemplul 2. 3. 1. Să considerăm graful din figura 2. 3. 1.

Figura 2. 3. 1.

13
Deoarece în vârful
1x iese și intră cel puțin câte un arc îl marcăm cu ”
 ”. Apoi marcăm cu
”+” vârfurile
2x și
5x și cu ” –” vârful
3x . Acum marcăm cu ” –” vârful
2x și cu ”+” vârfurile
3x ,
4x
și
6x . Procesul de marcare nu mai poate continua, rămânând vârfuri care nu sunt marcate cu ”

”.
Prima componentă tare conexă a grafului este
3 2 1 1 ,,xxx C
Suprimăm vârfurile
3 2 1,,xxx și arcele adiacente lor și obținem graful din figura 2. 3.2.

Imediat se marcheaz˘a cu ”
 ” numai vârfurile
4x și
5x , obținând cea de -a doua
componentă tare conexă
5 4 2 ,xx C . Vârful
6x formează cea de-a treia componentă tare conexă,
adică
6 3x C .
În figura 2. 3. 3. prezentăm graful cu vârfurile sale împărțite în componente tare conexe.

Algoritmul lui Yu Chen. Acest algoritm pentru aflarea componentelor tare conexe folosește
ideea de lucru de la algoritmul lui Chen pentru determinarea matricei drumurilor.
Fie G = ( X, U) un graf orientat,
Xx1 , un vârf fixat al grafu lui. Notăm cu
1V mulțimea
vârfurilor atinse de la
1x și
2V mulțimea vârfurilor care ating pe
1x , adică:

 
 1 i 2i 1 1
xla xla de drum xla xla de drum

ii
x Vx V

Propoziție 2. 3. 1. Mulț imea de vârfuri
1 2 1 1 x VV C  este componenta tare conexă
care conține vârful
1x .
Figura 2. 3. 2.

Figura 2. 3. 3.

14
Demonstrație. Dacă
2 1VV , atunci
1 1x C .
Dacă
2 1VV , atunci fie
1 i 2 1 i x x V VV  și
2 ixV , adica există drum de la
1x la
ix
și există drum de la
ix la
1x , de unde
1x și
ix sunt mutual atinse , de unde putem deduce că
, ,1Cyx
există un drum de la x la y și un drum de la y la x, adică
1C este tare conexă. Trebuie
să mai arătăm că
1C este maximal, relativ la proprietatea de tare conexiune (dacă mai adăugăm un
vârf comp onentei
1C se pierde această proprietate). Presupunem că
1C nu este maximală. Prin
adăugarea unui vârf
1\CX xj la componenta
1C se pierde proprietatea de tare conexitate. Într-
adevăr, vârfurile
jx și
1x nu pot fi mutual atinse, deoarece, în acest caz, vârful
jx s-ar afla deja în
componenta
1C . Așadar,
1C este maximală.

Algoritmul lui Yu Chen are următorii pași:

Pasul 1. Se scrie matricea boolean ă A a grafului G = (X, U).
Pasul 2. Se determin ă toate drumurile care pleac ă din
1x spre alte v ârfuri, proced ând ca la
pașii 2 ș i 3 de la algoritmul Yu Chen p entru determinarea matricei drumurilor, adic ă se introduc
prin adunare boolean ă toate cifrele de pe linia întâi. Not ăm cu
1V mulțimea v ârfurilor care au cifra
1 pe linia întâi astfel obț inută.
Pasul 3. Ca la pasul 2 proced ăm pe coloana întâi, determin ând toate v ârfurile care sunt
legate prin drumuri cu
1x . Not ăm cu
2V mulțimea v ârfurilor care au cifra 1 pe coloana întâi astfel
obținută.
Pasul 4. Determin ăm prima component ă tare conex ă, luând
1 2 1 1 x VV C  .
Pasul 5. În matricea A se elimin ă liniile ș i coloanele care au v ârfurile în
1C.
La matricea obț inută se aplic ă, din nou paș ii 2–5. Se aplic ă algoritmul p ână se epuizeaz ă
vârfurile grafului.

Observație 2. 3. 1. Mulțimea vârfurilor
1V este pusă în evidență de pozițiile egale cu 1 de pe
prima linie a matricei D, iar mulțimea
2V se determină cu ajutorul pozițiilor egale cu 1 de pe
prima linie a matricei
tD sau echivalent, de pe prima coloană a matricei D.

Exemplul 2. 3. 2. Să considerăm graful din figura 2. 3. 4. Să -i aflăm componentele tare
conexe

Figura 2. 3. 4.

15
Scriem matricea booleană atașată grafului

Determinăm toate legăturile prin drumuri ce pleacă din
1x spre alte vârfuri:

Din tabelul de mai sus deducem că
 8 7 6 5 4 3 2 1 1 ,,,,,,, xxxxxxxx V .
Procedăm la fel pe coloana întâi, scriind tabelul, pentru economie de spațiu, tot pe
orizontală obținem:

Din tabelul de mai sus deducem ca mulțimea vârfurilor care sunt legate prin drumuri cu
1x
este
8 7 3 1 2 ,,, xxxx V .
Acum găsim prima componentă tare conexă
8 7 3 1 1 2 1 1 ,,, xxxx x VV C    .
Eliminăm în matricea A liniile și coloanele corespunzătoare vârfurilor din
1C și obținem
matricea:

Cum pe linia lui
2x în matricea A 1 avem numai cifra 0, deducem că următoarea componentă
tare conexă este
2 2x C . Eliminând linia și coloana corespunzătoare vârfului
2x din A 1,
obținem matricea:

16
Cum pe coloana lui
4x în matricea A 2 avem numai cifra 0, deducem că următoarea
componentă tare conexă este
4 3x C . Eliminând linia și coloana corespunzătoare vârfului
4x
din A 2, obținem matricea:

Calculând matricea drumurilor pentru matricea
3A obținrm:

Din observația 2. 3. 1. deducem că
6 5 1 ,xx V și
6 5 2 ,xx V , de unde mai obținem
componenta tare conexă
6 5 5 2 1 4 ,xx x VV C    .

Observația 2. 3. 2. Deoarece oricare două vârfuri dintr -o compone ntă tare conexă sunt legate
între ele prin drumuri, rezultă că un graf poate fi reprezentat prin unul care are ca vărfuri
componentele tare conexe, arcele de legătură, între ele stabilindu -se după arcele din graful dat. În
cazul exemplului nostru obținem g raful din figura 2. 3. 5. Graful astfel obținut se numește graful
condensat atașat grafului dat.

Observația 2. 3. 3. Graful condensat este important în rezolvarea multor probleme practice
deoarece reduce dimensiunea sistemelor complexe.

2. 4. Drumuri și circuite hamiltoniene

Una dintre cele mai știute probleme economice este problema reprezentantului comercial .
Reprezentantul comercial este o persoană care trebuie să prezinte s au să distribuie marfa solicitată
la o serie de sedi repartizate în general neliniar pe o anumită zonă teritorială ( orașele dintr -un
județ, magazinele dintr -un sector , persoanele dintr -un sat etc). Dacă numărul de obiective care
trebuie îndeplinite este mare sau foarte mare , iar timpul di sponibil foarte redus atunci devine
necesară o asemenea organizare a trecerii pe la fiecare obiectiv încât să se realizeze în intervalul
minim posibil. Acest timp minim se interpretează prin drumul cel mai scurt, iar cel mai scurt Figura 2. 3. 5.

17
drum este evident cel î n care se trece pe la fiecare obiectiv o singură dată. În plus, la sfârșit
trebuie să se localizeze în punctul inițial, adică centr ul firmei la care lucrează.
O reprezentare a zonei aprovizionate, în care sedile pe la care se trece sunt vizualizate prin
puncte, iar căile de acces la acestea prin segmente de curbe, va fi evident un graf, problema
reducându -se la a găsi circuitul hamiltonian de lungime minimă.
De-a lungul timpului s-au evidențiat o multitudine de probleme reductibile la descoperirea
unui traseu (sau circuit) hamiltonian într -un graf, cum ar fi:

Problema transportului in comun( descperirea celui mai scurt drum posibil pentru care
mijloacele de transport in comun ajung în puncte cheie a orașului).
Problema rețelei de telecomunicații ( generarea de semnal radio cu cât mai putine antene
posibile).
Problema poștașului ( descoperirea drumului cel mai scurt care trece pe la toate locuințele ce
aparțin de oficiul poștal la care lucrează acesta);
Problema colectării rezid urilor ( descoperirea celui mai redus traseu prin care se trece pe la
toate punctele de stocare a rezid urilor);
Problema succesiunii operațiilor (executarea mai multor operații pe o mașină în acea ordine
în care suma timpilor consumați cu pregătirea mașinii pentru trecerea de la o operație la
următoarea să fie minim) ;
Ordinea lipirii unor compone nte electronice pe o placă.

Fie G = (X, U) un graf orientat.

Definiția 2. 4 . 1. Drum hamiltonian este un drum elementar care trece prin toate nodurile X
ale grafului G.

Definiția 2. 4 . 2. Circuit hamiltonian este un circuit elementar care trece prin toate nodurile
X ale grafului G.

Exemplul 2. 4. 1. În figura 2. 4. 1. se observă că drumul
 2 4 5 3 1 1 ,,,, xxxxx D este drum
hamiltonian, iar drumul
 1 5 3 4 2 1 2 ,,,,, xxxxxx D este circuit hamilton ian.

Definiția 2. 4. 3. Putere de atingere a unui nod
ix  X în graful G este numărul de noduri la
care se poate ajunge din
ix .
Observația 2. 4. 1. Puterea de atingere a nodului
ix se notează cu p(
ix ), 1  i  n și evident
p(
ix) 
ixd .
Figura 2. 4. 1.

18 Exemplul 2. 4. 2. În graful din figura 2. 3. 4. puterea de atingere a unui nodului
8x este
78xp
, iar
38xd

Algoritmul lui Chen pentru determinarea drumurilor hamiltoniene în grafuri fără circuite

Fie G = (X,U) un graf orientat fără circuite, cu n noduri: X = {x 1, x2, … , x n}. Vom
considera că am calculat matricea drumurilor D și puterile de atingere ale tuturor nodurilor.
Dacă în graful G există un drum de la nodul x i la nodul x j atunci evident p(x i) > p(x j),
deoarece în orice vârf în care se poate ajunge din x j se poate ajunge și din x i dar din x j nu se poate
ajunge în
ix pentru că nu există circuite.
Teorema 2. 4. 1. (Chen) Un graf cu n noduri, fără circuite conține un drum hamiltonian dacă
și numai dacă există relația:

21
1
nnxpn
ii

Demonstrație
“” Fie H un drum hamiltonian și presupunem că nodurile grafului au fost notate în
ordinea în care apar în acest drum. Atunci din orice nod x i se poate ajunge în toate nodurile cu
indice mai mare și numai în acestea (altfel ar exista circuite) și deci puterea unui nod x i este n – i,
de unde:

n
iixp
1
= (n – 1) + (n – 2) + … + 1 + 0 =

21nn
“” Ordonând vârfurile în ordinea descrescătoare a puterii lor de atingere (i > j  p(x i) <
p(x j)) și cum graful nu are circuite, vom obține o matrice D cu zerouri pe diagonala principală și
sub diagonala principală (evident pe o poziție (i,i) nu se află nici un 1 , deoarece graful n-are
circuite, iar dacă ar fi un 1 pe poziția (i,j) cu i > j ar însemna că din x i se poate ajunge în x j, deci în
toate nodurile în care se poate ajunge din x j, iar din x j nu se poate ajunge în x i, deci p(x i) > p(x j) în
contradicție cu ipoteza de ordonare a nodurilor). Cum deasupra diagonalei principale sunt

21nn
poziții iar suma puterilor vârfurilor este chiar

21nn rezultă că toate pozițiile de
deasupra diagonalei sunt 1. Aceasta înseamnă că există toate arcele de forma (xi,xi+1),
 n i,1
(altfel n -ar exista drum de la x i la x i+1) și deci drumul hamiltonian (x 1, x2, … , x n) q.e.d.
Teorema 2. 4. 2. Dacă într -un graf orientat fără circuite , există un drum hamiltonian , atunci
acesta este unic.

Demonstrație Deoarece un drum hamiltonian se identifică cu o permutare a nodurilor
grafului, existența a două drumuri hamiltoniene implică existența a două permutări distincte a
nodurilor grafului și cum două permutări distincte diferă prin cel puțin o inversiune vor e xista
două noduri x i și x j în ordinea x i  xj pe un drum și invers pe celălalt, existând deci un drum atât
de la x i la x j cât și de la x j la x i, cele două formând împreună un circuit, în contradicție cu ipoteza.
Pe aceste teoreme se bazează algoritmul lui Chen de determinare a drumului hamiltonian
într-un graf orientat fără circuite:
Algoritmul lui Chen
Pasul 1. Se scrie matricea de adiacență A
Pasul 2. Se calculează matricea drumurilor D
Pasul 3. Dacă există un indice i cu d ii = 1 atunci graful are circuite, nu se poate aplica
algoritmul lui Chen și algoritmul se oprește. Dacă nu, se trece la pasul 4.

19
Pasul 4. Se calculează puterile de ati ngere pentru fiecare nod, astfel la matricea D se mai
adaugă o coloană ”p”, pe care se tre ce numărul de cifre 1 de pe fiecare linie din D. Aceste numere
sunt puterile de atingere corespunzătoare vârfurilor grafului
Pasul 5. Dacă nu se verifică relația

21
1
nnxpn
ii , atunci graful nu are drumuri
hamiltoniene și algoritmul se oprește, al tfel se trece la pasul 6.
Pasul 6. Se ordonează nodurile în ordinea descrescătoare a puterilor lor de atingere și
obținem drumul hamiltonian căutat.

Exemplul 2. 4. 3. Fie graful din figura 2. 4 . 2. Să cercet ăm, folosind algoritmul lui Chen
dacă acest graf are drum hamiltonian.

Matricea booleană atașată grafului este:

Matricea drumurilor la care am atașat coloana purerilor de atingere ale vârfurilor este:

Deoarece deducem conform algoritmului lui Chen , că

acest graf admite un drum hamiltonia dat de
Figura 2. 4. 2.

,2166145320
 1 6 2 3 5 4 ,,,,, xxxxxx H

20 Algoritmul Yu Chen pentru grafuri cu circuite.

Acest algoritm are următorii pași:
Pasul 1. Se determină componentele tare conexe ale grafului G = (X, U), notate cu
,1C
,2C
,3C
. . .
Pasul 2. Se determină graful condensat asociat grafului G = (X, U), care este un graf fără
circuite.
Pasul 3. Se determină drumul hamiltonian în graful condensat, cănd există.
Pasul 4. Se aranjează componentele tare conexe în ordinea dată de drumul hamiltonian
determinat la pasul 3.
Pasul 5. Se scriu toate drumurile hamiltoniene din fiecare componentă tare conexă.
Pasul 7. Stabilim legăturile de la o componentă la alta în funcție de arcele de incidență
(legătură) din graful dat, citind apoi toate drumurile hamiltoniene.

Observația 2. 4. 2. Dac ă în graful condensat nu exist ă drum hamiltonian sau între dou ă
componente nu exist ă legătură, atunci graful nu are drumuri hamiltoniene.

Exemplul 2. 4. 4. Să aflăm drumurile hamiltoniene ale grafului din figura 2. 3. 4. Din
exemplul 2. 3. 2. am aflat componentele tare conexe, care sunt:
,,,,8 7 3 1 1 xxxx C
,2 2x C
4 3x C
și
6 5 4 ,xx C . Graful condensat atașat grafului din figura 2. 3. 4. este graful din
figura 2. 3. 5.
Se obser vă că in graful condensat avem următorul drum hamiltonian:
 2 4 3 1 ,,, CCCC dCH

Acum, scriem componentele tare conexe în ordinea din drumul
CHd și sub ele scriem toate
drumurile hamiltoniene din fiecare component ă:

2
6565
4
318778312 4 3 1
xxxxxxxxxxxxxxC C C C

Apoi stabilim leg ăturile între ultimele vârfuri din drumurile dintr -o component ă și primele
vârfuri din componenta urm ătoare (le indic ăm prin săgeți).
Obținem drumurile hamiltoniene:

 2 6 5 4 7 8 3 1 1 ,,,,,,, xxxxxxxx dH

 2 6 5 4 3 1 8 7 2 ,,,,,,, xxxxxxxx dH

Algoritmul matricilor latine. Vom prezenta un procedeu prin care se pot găsi toate drumurile
elementare, deci și cele hamiltoniene, precum și circuitele hamiltoniene.

Definiția 2. 4. 4. Se numește alfabet o mulțime de semne numite simboluri sau litere
{si│iI} unde I este o mulțime oarecare de indici, finită sau nu.

Definiția 2 . 4. 5. Se numește cuvânt un șir finit de simboluri notat
n 2 1 i ii s…ss .

21 Definiția 2. 4. 6 . Se numește înmulțire latină o operație definită pe mulțimea cuvintelor
unui alfabet, notată "
L ", astfel:
n 2 1 i ii s…ss
L
m 2 1 j jj s…ss
=
m 2 1 n 2 1 j jji ii s…sss…ss
(produsul a două cuvinte se obține prin concatenarea lor)

Observația 2. 4. 3. Înmulțirea latină este asociativă, are ca element neutru cuvântul vid, nu e
comutativă și un element este inversabil doar dacă este cuvântul vid.

Definiția 2. 4. 7 . Se numește adunare latină o funcție definită pe mulțimea cuvintelor unui
alfabet cu valori în mulțimea pă rților mulțimi cuvintelor, notată "
L " astfel:
n 2 1 i ii s…ss
L
m 2 1 j jj s…ss
=


m 2 1n 2 1
j jji ii
s…sss…ss
(suma a două cuvinte este mulțimea formată din cele două cuvinte)

Fie G = (X, U) un graf. Cu ajutorul definițiilor de mai sus putem prezenta pașii algoritmului
matricilor latine.
Pasul 1. Construim matricea latină
njiijlL,1, asociată grafului, dată de :

lij =



j ij i ji
x,x arcul nu dacă 0x,x arcul dacă xx
și matricea
L~ , definită prin:
ijl~
=



j ij i j
x,x arcul nu adac0x,x arcul adacx

numită matricea latină redusă.
Pasul 2. Se calculează succesiv matricile:
L2 = L
L
L~ , L3 = L2
L
L~ , … ,Lk+1 = Lk
L
L~

folosind operațiile de înmulțire și adunare latină, alfabetul fiind mulțimea nodurilor grafului,
unde operația de înmulțire este ușor modificată, produsul dintre două elemente ale matricilor fiind
0, dacă unul dintre ele este 0 sau au un nod comun și este produsul latin al lor, în caz contrar.
Din felul cum a fost construită, matricea Lk va conține toate drumurile elementare de
lungime k . Cum un drum elementar poate avea cel mult n noduri (câte are graful cu totul) rezultă
că:
– primele n -1 puteri ale lui L conțin toate drumurile elementare din graf;
– puterile lui L mai mari sau egale cu n au toate elementele egale cu 0;
– matricea Ln-1 conține toate drumurile hamiltoniene din graf (dacă există).
Observația 2. 4. 4 . Dacă dorim să obținem circuitele hamiltoniene se va calcula
nL , dar
admitem, ca excepție, situația de repetare a primului și a ultimului vârf (cel care în chide
circuitul).
Exemplul 2. 4. 5. Pentru graful din figura 2. 4. 3. vom determina cu ajutorul algoritmului
matricelor toate drumurile hamiltoniene .

22

Scriem matricea latin ă L, iar apoi din ea g ăsim matricea latină
~
L , obținută din matricea
latină L prin suprimarea primei litere a elementelor nenule.

Apoi calculăm matricea
~2LL LL și obținem:

Figura 2. 4. 3.

23
Urmează să calculăm matricea
~2 3L L LL și obținem:

La final calculăm matricea
~3 4L L LL și obținem:

În conc luzie, graful dat mai sus are 6 drumuri hamiltoniene , acestea sunt :
dceba dH ,,,,1 ,
ebdca dH ,,,,2
,
adceb dH ,,,,3 ,
ebadc dH ,,,,4 ,
cebad dH ,,,,5 ,
badce dH ,,,,6 .
Observația 2. 4. 5. Pentru a obț ine circuitele hamiltoniene se va calcula
~4 5L L LL , dar
acum se admite ca primul ș i ultimul v ârf să se repete. Prin urmare matricea
~4 5L L LL are
forma:

În concluzie, graful dat are 5 circuite hamiltoniene:
 adceba cH ,,,,,1 ,
 badceb cH ,,,,,2
,
 cebadc cH ,,,,,3 ,
 dcebad cH ,,,,,4 și
 ebadce cH ,,,,,5 .

24 Capitolul III
Rezolvarea unor probleme relative la drumuri de valoare optimă

3. 1. Grafuri valorizate. Principiul optimalității.

Fie G = (X, U) un graf orientat fără bucle, adic ă
 Xx x xi i i  , .

Definiția 3. 1. 1. Graful G = (X, U) este valorizat dac ă exist ă funcția
Uv: R
.
Dacă
,Uu atunci v(u ) se numeș te valoarea arcului u.

Fie drumul
ku uud ,…,,2 1 în graful G.

Definiția 3. 1. 2. Se numeș te valoarea drumului d, numărul

Observația 3. 1. 1. Dacă v(u) = 1
Uu și
 k 2 1 u,…,u,ud , rezult ă v(d) = k.

Observația 3. 1. 2. Fie a, b
 X vom nota prin D(a, b) mulț imea drumurilor ce au ca v ârf
inițial pe a și ca vârf final pe b .
Definiția 3. 1. 3. Se numeș te drum optim în D(a, b) un drum
baDd ,~
 astfel ca:
dv optim dv
baDd ,~


unde prin optim vom î nțelege maxim sau minim.

Propoziția 3 . 1. 1. (Principiul optimalit ății) Orice subdrum al unui drum optim este optim.

Demonstrație. Fie
 baDbx xx xadj h l i , , ,…,, ,…,,   , drumul de valoare minimă (optimă)
ce conține vârfurile a,
bx xx xj h l i , ,…,, ,…,
 X și subdrumurile
l ix xa d ,…,,1 și
 bx xx dj h l , ,…,,2
, se observă că
2 1ddd . Vom arata că
1d are valoare minimă.
Presupunem prin reducere la absurd că
1d nu are valoare minimă și fie
l l i xaD x xa d , ,…,,~
1~

astfel încât
11~
dv dv , considerăm acum drumul
baD ddd ,21~ ~

se observă că
,2 1 21~ ~
dv dv dv dv dv dv  ceea ce
contrazice faptul că d este drumul de valoare minimă. Prin urmare
1d are valoare minimă.

Fie D(a, c, b ) mulțimea drumurilor ce conț in vârfurile a, c, b
 X. Are loc:
Propoziția 3. 1. 2. Fie
bcaDd ,, și
caDd ,1 ,
bcD d ,2 astfel încât are loc
2 1ddd
. Drumul d este optim în D(a, c, b) dac ă și numai dacă
1d este drum optim în D(a, c)
și
2d este drum optim în D(c, b).
.
1
k
iiuv dv

25 Demonstrație.
"" Dacă
bcaDd ,, este drum minimal (optim), iar
,2 1ddd unde
bcD d ,2
din propoziția 3.1. 1. deducem că
1d este drum optim în D(a, c) și
2d
este drum optim în D(c, b).
""
Fie acum
 bcaDb xc xa dj i ,, ,…,,,…,,'  un drum oarecare, considerăm drumurile
caDc xa di , ,…,,' '
1  
și
bcDb xc dj , ,…,,' '
2   . Din minimalitate drumurilor
,,1 caDd
bcD d ,2
și
,2 1ddd avem:
,' '
2'
1 2 1 dv dv dv dv dvdv  de unde deducem că
drumul
bcaDd ,, este minim.

3. 2. Drumuri optime într -un graf . Algoritmi de găsire a drumului optim

În marea majoritate a problemelor care pot fi modelate prin grafuri nu ne interesează numai
dacă există sau nu legături între componentele reprezentate prin nodurile grafului ci și intensi tatea
acestora. Această intensitate are semnificația unei valori numerice (pozitive sau negative) asociate
arcului corespunzător legăturii a cărei intensitate o măsoară.

În activit ățile economice această valoare poate fi:
– distanța rutieră dintre două orașe, sate, țări, etc. ;
– prețul străbaterii traseului reprezentat prin arcul căruia îi corespunde ;
– timpul străbaterii traseului respectiv ;
– greutatea expediată pe traseul respectiv ;
– volumul maxim al traseului respectiv ;
– profitul înfăptuit prin perindarea de la o stare la alta a s tructurii ;
– cheltuiala de putere energică pentru realizarea desfășurării respective;
– scor conceput etc.

Din cauza varietății ne redus e a grafurilor posibile, nu există un algoritm care să rezolve
orice problemă în timp util, dar s -au elaborat o mulțime de algoritmi, fiecare fiind cel mai eficace
în anumite cazuri. Acești algoritmi pot fi grupați în cinci categorii:
Algoritmi prin calcul matricial (Bellman -Kalaba, I. Tomesc u, Bellman -Schimbell);
Algoritmi prin ajustări succesive: (Ford);
Algoritmi prin inducție (Dantzig);
Algoritmi prin ordonare prealabilă a vârfurilor grafului;
Algoritmi prin extindere selectivă (Dijkstra).

În continuare vom prezenta patru dintre acești alg oritmi.

3. 2. 1. Algoritmul lui Bellman – Kalaba

Algoritmul se aplică în grafuri finite care nu au circuite de valoare negativă (pentru o
problemă de minim) sau care nu au circuite de valoare pozitivă (într -o problemă de maxim) și
găsește drumurile de va loare minimă (maximă) de la toate nodurile grafului la un nod oarecare,
fixat. Dacă dorim să cunoaștem drumurile de valoare minimă (maximă) între oricare două noduri
vom aplica algoritmul, pe rând, pentru fiecare nod al grafului.
Fie
,,UX G unde
nx xx X ,…,,2 1 un graf orientat finit. Presupunem (fără a
restrânge generalitatea, că am numerotat nodurile astfel încât nodul spre care căutăm drumurile de
valoare minimă (maximă) de la celelalte noduri să fie x n.
,c,aDd1

26 Se construiește matricea pă tratică M cu dimensiunea egală cu numărul de noduri ale
grafului ale cărei elemente sunt:
mij =





)x,(x arcul existanu dacamaxim) de problema(în minim) de problema(în ji daca 0j i si )x,(x arcul exista daca )x,(x arcului valoarea
j ij i j i
Se adaugă succesiv liniile L i la matricea M, elementele acestora calculându -se prin relațiile
de recurență:
L1j = m jn j = 1,…,n (prim a linie este ultima coloană, transpusă, a matricii M)
Lij = min (L i-1j ,
n1,kmin
 (mjk + L i-1k)) într -o problemă de minim
sau L ij = max (L i-1j ,
n1,kmax
 (mjk + L i-1k)) într -o problemă de maxim

După calcularea fiecărei linii noi se compară elementele ei cu cele ale precedentei:
Dacă L ij = L i-1,j pentru orice j = 1,…,n atunci se oprește recurența și ultima linie calculată
conține valorile minime ale drumurilor de la celelalte noduri la nodul x n.
Dacă există cel puțin un indice j cu L ij  Li-1j se trece la calcularea noii linii
jiL1
Pentru descoperirea drumului care dă valoarea minimă de la un nod x j la nodul x n se găsesc,
începând înapoi de la ultima linie, pe care s -au obținut valorile finale, notată L f, nodurile
1kx ,
2kx
, …,
rkx care formează drumul căutat, unde
1kx =
nx,
rkx =
jx și fiecare alt indice k i+1 este cel
pentru care s -a obținut minimul(maximul) de pe poziția k i al liniei L i.

Observați a 3. 2. 1. Pentru grafuri foarte mari, algoritmul necesită un volum mare de
memorie, prin necesitatea memorării matricei M, care este greu de manipulat. Chiar dacă din cele
n2 arce posibile graful ar avea doar un procent foarte mic , matricea grafului va avea tot n2 poziții
de memorat și analizat.
Exemp lul 3. 2. 1. Presupunem dat graful orientat de mai jos, în care se dorește descoperirea
drumului de valoare minimă de la nodul x 1 la nodul x 9.

27




    
070 486050 892307283 09 309705 40

Matricea M va fi :

După calcularea liniilor L i obținem:
x
1 x
2 x
3 x
4 x
5 x
6 x
7 x
8 x9
x1 0 4   5    
x2  0 7 9     
x3   0 3     9
x4    0     3
x5  8 2 7 0 3 2 9 
x6  8    0 5  
x7       0 6 8

28

Deoarece L 4 = L 5 oprim calcularea liniilor după calcularea liniei 5. În această linie se află
valorile celor mai scurte drumuri de la toate nodurile la nodul
9x . Drum ul dorit de noi (
9 1x x )
are valoarea dată de prima poziție a liniei 5, fiind egal cu 13.
Pentru a găsi acest drum, plecăm înapoi de la linia 4 și avem:

x
1 x
5
 
1
3 = 8 + 5 x
3
 
8 = 6 + 2 x
4
 
6 = 3 + 3

3  x
9

3. 2. 2. Algoritmul lui Ford simplificat

Algoritmul lui Ford simplificat se aplică doar în grafuri care nu admit circuite. Cu ajutorul
lui se găsește drumul de valoare optimă între două noduri fixate x i și x j. Printr -o eventuală
renumerotare a nodurilor putem presupune că nodul de la care pornește drumul este
1x , care va fi
numit nod inițial, iar nodul la care se termină este x n, numit nod final.
Algoritmul este:
I se dă vârfului inițial valoarea 0 (zero): w
1x = 0
Se construiește mulțimea A f ormată din nodul inițial:
1x A
Se analizează nodurile din afara mulțimii A.
Dacă există noduri în care se poate ajunge prin arce directe doar de la nodurile mulțimii A,
acestea se adaugă la mulțimea A, cu valoarea:
w(x i) =
  i j j
x,xxx,xv xw min
ijj
 , în problemele de minim x8    4    0 7
x9         0
L1   9 3   8 7 0
L2  1
2 6 3 1
0 1
3 8 7 0
L3 1
5 1
2 6 3 8 1
3 8 7 0
L4 1
3 1
2 6 3 8 1
3 8 7 0
L5 1
3 1
2 6 3 8 1
3 8 7 0

29 sau
w(x i) =
  i j j
x,xxx,xv xw max
ijj
 , în problemele de maxim
apoi se trece la pasul 4

Dacă nu există nici un nod de acest tip atunci nu există nici un drum de la x 1 la x n. STOP
Se analizează mulțimea A:
Dacă x n  A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de la x 1 la
xn. Pentru descoperirea acestui drum se pornește înapoi de la nodul final x n și se găsesc nodurile
1kx
,
2kx , …,
rkx care formează drumul căutat, unde
1kx = x n,
rkx = x 1 și fiecare alt i ndice k i+1
este cel pentru care:
w(
1ikx
 ) + v(
1ikx
 ,
ikx) = w(
ikx ) STOP
Dacă x n  A se reia algoritmul de la pasul 3.

Exemplul 3. 2 . 2. Pentru același graf , cel din figura 3. 2. 1. și aceeaș i pereche de noduri
1x
și
9x , aplicând algoritmul lui Ford vom avea succesiv:
pas1: w(x 1) = 0
pas2:
1x A
pas3: Nodurile în care se poate ajunge doar din x 1:
5x 
   550 , min5 1 1 5   xxvxw xw

pas4:
Ax9
pas3:
5 1,xx A și nodurile în care se poate ajunge prin arce directe doar din
1x și
5x
sunt:
6x 
  8 , min6 5 5 6    xxvxw xw

pas4:
A x9
pas3:
6 5 1,,xxxA și nodurile în care se poate ajunge prin arce directe doar din
1x ,
5x și
6x
sunt:
7 2,xx  
  
 488 ,85 ,40min, ,, ,, min2 6 6 2 5 5 2 1 1 2
     xxv xwxxv xwxxvxw xw

  758 ,25min , ,, min7 6 6 7 5 5 7     xxv xwxxv xw xw

pas4:
A x9
pas3:
 7 6 5 2 1 ,,,, xxxxx A și nodurile în care se poate ajunge prin arce directe doar din
6 5 2 1 ,,, xxxx
și
7x sunt:
8 3,xx  
  725 ,74min x,xv xw,x,xv xwmin xw3 5 5 3 2 2 3    

  1367 ,95min x,xv xw,x,xv xwmin xw8 7 7 8 5 5 8    

pas4:
A x9
pas3:
 8 7 6 5 3 2 1 ,,,,,, xxxxxxx A și nodurile în care se poate ajunge prin arce directe
doar din
7 6 5,3 2 1 ,, ,, xxxxxx și
8x sunt:
4x  
  
 10413 ,75 ,37 ,94min, ,, ,, ,, min4 8 8 4 5 5 4 3 3 4 2 2 4
      xxv xwxxv xwxxv xwxxv xw xw

30 pas4:
A x9
pas3:
 8 7 6 5 4 3 2 1 ,,,,,,, xxxxxxxxA și nodurile în care se poate ajunge prin
arce directe doar din
7 6 5 4 3 2 1 ,,,,,, xxxxxxx și
8x sunt:
9x  
  
 13713 ,87 ,310 ,97min, ,, ,, ,, min9 8 8 9 7 7 9 4 4 9 3 3 9
      xxv xwxxv xwxxv xwxxv xw xw

pas4: și urmează să găsim drumul care are lungimea 13.

Avem succesiv:
9 4 4 9 ,xxv xw xw 

4 3 3 4 ,xxv xw xw 

3 5 5 3 ,xxv xw xw 

5 1 1 1 ,xxvxw xw 

deci drumul căutat este:

Observația 3. 2. 2. Dacă graful are un circuit atunci se poate demonstra ușor că nu vom
putea da valoare nici unui nod al acestuia ș i dacă există vreun drum de la
1x la x n care trece prin
unul din nodurile circuitului nu vom putea da valoare nici lui x n, cu toate că există drum de la
1x
la x n.
Observația 3. 2. 3. Algoritmul necesită pentru memorare și manipulare doar cunoaște -rea,
pentru fiecare nod, a nodurilor spre care "pleacă" arce din acesta și valorile acestor arce, fiind
mult ma i ușor de aplicat sau implementat pe calculator. El are însă dezavantajul că se poate aplica
doar în grafuri fără circuite.

3. 2. 3. Algoritmul lui Dijkstra

În algoritmul Ford simplificat, pentru a găsi valoarea nodului final, deci a drumului minim,
plecăm de la nodul inițial în toate direcțiile posibile, păstrând de fiecare dată toate nodurile
analizate. Acest fapt duce la un consum inutil de timp, deoarece f oarte multe din aceste noduri nu
vor face parte din drumul optim. Pentru a elimina acest neajuns, algoritmul lui Dijkstra încearcă
să păstreze, la fiecare iterație, mulțimea minimă de noduri care să le conțină pe toate cele care vor
forma efectiv drumul op tim. În plus, algoritmul se poate aplica și în drumuri cu circuite. Ca un
minus este faptul că se aplică doar la probleme de minim. Algoritmul are următorii pași:
I se dă vârfului inițial valoarea 0 (zero):
Se construiește mulțimea A formată din nodul inițial:
Se analizează nodurile din afara mulțimii A.
Dacă există noduri în care se poate ajunge prin arce directe de la noduri din A (nu doar de la
nodurile mulțimii A, ca la algoritmul lui Ford simplificat) se calculează pentru toate acestea:

w(x i) = în problemele de minim dar, spre deosebire de

algoritmul lui Ford simplificat , se adaugă la mulțimea A doar cel pentru care se obține
valoarea minimă, apoi se trece la pasul 4.
Dacă nu există nici un nod de acest tip , atunci nu există nici un drum de la x 1 la x n. STOP
Se analizează mulțimea A:
1x A
01xw
  i j j
x,xAxx,xv xw min
ijj

Ax9
9 4 3 5 1 x x x x x 

31 Dacă x n  A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de la x 1 la
xn. Pentru descoperirea acestui drum se pornește înapoi de la nodul final x n și se găsesc nodurile
1kx
,
2kx , …,
rkx care formează drumul căutat, unde
1kx = x n,
rkx = x 1 și fiecare alt indic e k i+1
este cel pentru care:
w(
1ikx
 ) + v(
1ikx
 ,
ikx) = w(
ikx ) STOP
Dacă x n  A se reia algoritmul de la pasul 3.

Exemplu l 3. 2. 3. Vom aplica algoritmul lui Dijkstra la același graf , cel din figura 3. 2. 1.
folosit la ceilalți algoritmi, pentru a putea face comparații:
pas1:
01xw
pas2:
1x A
pas3: Mulțimea nodurilor în care se poate ajunge și din
1x este:
5 2,xx 
   440 , min2 1 1 2   xxvxw xw

   550 x,xv xwmin xw5 1 1 5   

 4 , min2 5 2 xw xwxw

pas4:
Ax9
pas3:
2 1,xx A și mulțimea nodurilor în care se poate ajunge prin arce directe din
1x
sau
2x este:
5 4 3,,xxx 
   1174 x,xv xwmin xw2 2 2 3   

   1394 x,xv xwmin xw4 2 2 4   

   550 x,xv xwmin xw5 1 1 5   

  5 xw xw,xw,xwmin5 5 4 3 

pas4:
A x9
pas3:
5 2 1,,xxx A și mulțimea nodurilor în care se poate ajunge prin arce directe din
1x
,
2x sau
5x este:
 8 7 6 4 3 ,,,, xxxxx 
  725 ,74min x,xv xw,x,xv xwmin xw3 5 5 3 2 2 3    

  1275 ,94min x,xv xw,x,xv xwmin xw4 5 5 4 2 2 4    

   835 x,xv xwmin xw6 5 5 6   

   725 x,xv xwmin xw7 5 5 7   

   1495 x,xv xwmin xw8 5 5 8   

  7 xw xw xw,xw,xw,xw,xwmin7 3 8 7 6 4 3 

pas4:
A x9
pas3:
 7 5 3 2 1 ,,,, xxxxx A și mulțimea nodurilor în care se poate ajunge prin arce
directe din
1x ,
2x,
3x,
5x și
7x este:
9 8 6 4 ,,, xxxx 
  
 1075 ,37 ,94min, ,, ,, min4 5 5 4 3 3 4 2 2 4
    xxv xwxxv xwxxv xw xw

   835 x,xv xwmin xw6 5 5 6   

  1367 ,95min x,xv xw,x,xv xwmin xw8 7 7 8 5 5 8    

  1587 ,97min x,xv xw,x,xv xwmin xw7 7 7 9 3 3 9    

  8 xw xw,xw,xw,xwmin6 9 8 6 4 

32 pas4:
A x9
pas3:
 7 6 5 3 2 1 ,,,,, xxxxxxA și mulțimea nodurilor în care se poate ajunge prin arce
directe din
6 5 3 2 1 ,,,, xxxxx și
7x este:
9 8 4,,xxx 
  
 1075 ,37 ,94min, ,, ,, min4 5 5 4 3 3 4 2 2 4
     xxv xwxxv xwxxv xw xw

  1367 ,95min , ,, min8 7 7 8 5 5 8     xxv xwxxv xw xw

  1587 ,97min , ,, min9 7 7 9 3 3 9     xxv xwxxv xw xw

  10 , , min4 9 8 4 xw xwxwxw

pas4:
A x9
pas3:
 7 6 5 4 3 2 1 ,,,,,, xxxxxxxA și mulțimea nodurilor în care se poate ajunge prin
arce directe din
6 5 4 3 2 1 ,,,,, xxxxxx și
7x este:
9 8,xx 
  
 1387 ,3 10 ,97min, ,, ,, min9 7 7 9 4 4 9 3 3 9
     xxv xwxxv xwxxv xw xw

  1367 ,95min x,xv xw,x,xv xwmin xw8 7 7 8 5 5 8    

 13 , min9 8 9 8  xw xw xwxw

pas4: x 9  A și urmează să găsim drumul optim care are lungimea 13.
Avem succesiv:
9 4 4 9 x,xv xw xw 

4 3 3 4 x,xv xw xw 

3 5 5 3 x,xv xw xw 

5 1 1 1 x,xv xw xw 

deci drumul căutat este:
9 4 3 5 1 x x x x x 

3.2.4. Obtinerea arborelui partial de cost minim folosind algoritmul lui Kruskal

Fie un graf neorientat conex. Fiecărei muchii u îi asociem un cost
c(u)>0. Problema constă în a determina un graf parțial conex A=(X,Δ) astfel încat suma
costurilor muchiilor din Δ să fie minimă.
Observăm că graful parțial de cost minim este chiar un arbore. Într -adevăr, A este
conex. Dacă A ar conține un ciclu, atunci eliminând o muchie oarecare din acest ciclu,
obținem tot un graf parțial conex, având însă un cost mai mic. Rezultă că A este un arbore.
Problema enunțată se mai numește problema conectării orașelor cu cost minim ,
deoarece putem să plecăm de la un graf complet în care cele n vârfuri reprezintă orașe; costul
unei muchii (i,j) reprezintă costul conectării directe a orașelor i și j. Un arbore parțial de cost
minim reprezintă modalitatea optimă (din punctul de vedere al construct orului) de a lega
direct perechi de orașe astfel încât în final orice oraș să fie conectat direct sau indirect cu toate
celelalte.
Metoda Greedy permite construirea arborelui parțial de cost minim muchie cu muchie
astfel: se alege întâi muchia de cost minim, iar apoi se adaugă repetat muchia de cost minim
nealeasă anterior și care nu formează cu precedentele un ciclu. Vom alege astfel n-1 muchii,
obținând un graf conex cu n-1 vârfuri, care este deci arbore. Evident, va mai trebui demonstrat
că arborele astfel construit este de cost minim. Algoritmul de mai sus este datorat lui Kruskal.
),(X G
u

33 Vom presupune că muchiile apar într -o matrice MAT cu m linii și trei coloane; fiecare
linie corespunde unei muchii, primele două elemente reprezentând extremitățil e muchiei, iar
al treilea reprezentând costul atașat muchiei. Vom presupune că în MAT muchiile apar în
ordinea crescătoare a costului atașat lor.
Înainte de a vedea cum se verifică dacă o nouă muchie formează împreună cu
precedentele muchii alese un ciclu, vom considera un exemplu.
Observăm că la fiecare pas în algoritmul lui Kruskal ia naștere o pădure, obținută din
pădurea precedentă unind doi arbori. Pădurea inițială este formată din n arbori, fiecare
constând dintr -un singur vârf
Pentru a soluționa prob lema apariției unui ciclu prin adăugarea unei muchii, o
modalitate eficientă este aceea de a memora pentru fiecare vârf tatăl său TATA(i) în pădurea
curentă. Atunci în momentul în care muchia (i,j) devine candidată la adăugarea ei în arborele
parțial de co st minim, pentru a determina dacă ea formează cu precedentele un ciclu este
suficient să verificăm dacă i și j fac parte din același arbore; în caz negativ vom adăuga
muchia respectivă, ceea ce revine la unirea a doi arbori cu ajutorul procedurii REUN1.

Observație. Arborele reprezentat prin vectorul TATA, rezultat în urma execuției
procedurii Kruskal, nu este parțial de cost minim; într -adevăr, la adăugarea unei muchii
(i,j), pentru pădurea curentă se unesc nu vârfurile i și j, ci rădăcinile arborilor ce l e conțin.

În procedura KRUSKAL care urmează presupunem pentru simplificare că muchiile au
atașate drept costuri valori întregi.

procedure KRUSKAL(n, m, MAT, COST, TATA)
integer MAT(m, 3), TATA(n)
for i = 1, n
TATA(i) ← –1
repeat
j ← 1; COST ← 0
for j= 1, m –1
do
if i > m then write ‘NU’;
return
endif
i1 ← MAT(j, 1);
i2 ← MAT(j, 2);;
call APART(i 1, TATA, n, t 1)
call APART(i 2, TATA, n, t 2)
if t1 = t 2 then call REUN1(t 1, t2, TATA, n);
write MAT(j, 1), MAT(j, 2)
COST ← COST + MAT(j, 3);
j ← j + 1;
exit
endif
j←j+1
repeat
repeat
write COST;
return
end

34 Exemplu de parcurgere a algoritmului lui Kruskal:

Vom parcurge pas cu pas acest algoritm. Ca exemplu vom folosi graful din figura
3.2.4.

Figura 3. 2. 4.

Pasul 1 :
În graful din figura 3.2.4., muchia (g, h) este cea mai scurtă. Oricare dintre nodurile g
sau h pot fi nod parinte. Noi vom alege arbitrar nodul g.

Pasul 2 :
Muchia (c,i) crează cea de -a doua pădure. Alegem nodul c ca părinte pentru cea de -a
doua pădure.

Pasul 3 :
Muchia (f,g) este urmatoarea muchie cu costul minim . Adăugam această muchie și
alegem nodul g ca fiind părinte.

35
Pasul 4 :
Muchia (a,b) creează a treia pădure.

Pasul 5 :
Adaugă muchia (c,f) și unește două păduri. Nodul c este ales ca nod părinte.

Pasul 6 :
Muchia (g,i) este următoarea cea mai scurtă cale, dar dacă o vom alege se va forma un
ciclu. Nodul c este nodul parinte al amândurora.

36
Pasul 7 :
În loc, adăugăm muchia (c,d).

Pasul 8 :
Dacă vom adăuga muchia (h, i) aceasta va forma un ciclu din nou.

Pasul 9 :
În loc să adăugăm muchia (h,i), vom adăuga muchia (a,h).

37
Pasul 10 :
Din nou, dacă vom adăuga muchia (b, c) se va crea un ciclu. Adăugăm muchia (d, e)
in locul ei și vom complecta pădurea finală care va forma arborele de cost minim. Acum toate
padurile și nodurile sunt unite.

Acum arborele arată în felul următor ;

Să trecem la analiza timpului necesitat de algoritm. Ordonarea celor m muchii în
ordinea crescătoare a costurilor atașate necesită timpul O(m log 2 m). Investigarea celor m
muchii necesită un timp proporțional cu m log 2 n, conform timpului de lucru al procedurii
APART . În plus, de n-1 ori se execută calculele corespunzătoare lui , care necesită un
2 1tt

38 timp constant. Cum , va rezulta că procedur a KRUSKAL are o eficacitate de ordinul
O(m log 2 m). Am ținut cont că datele de intrare sunt construite din m, n și MAT , deci au
lungimea 3m+2 .
Mai rămâne să demonstrăm corectitudinea procedurii KRUSKAL .

Propoziție. Algoritmul lui Kruskal furnizează un arb ore de cost minim.

Fie u1, u2, …, u n-1 muchiile alese – în această ordine – de algoritmul Kruskal. Vom
nota Uk={u 1,…,u k}. Fie v1, …, v n-1 muchiile unui arbore de cost minim și fie Vk={v 1, …, v k}.
Presupunem . Arătăm că c(u i)=c(v i) pentru orice i=1,…,n -1. Într -adevăr, în
caz contrar, fie k primul indice pentru care . Să considerăm graful
. Evident G' va conține un ciclu și numai unul, ciclu care va conține o
muchie (în caz contrar cu muchiile din Uk s-ar putea forma un ciclu, ceea ce nu este
posibil). Eliminând această muchie, vom obține un arbore . Evident
, în caz contrar algoritmul alegând drept uk pe vj. Nu putem avea însă
deoarece atunci costul lui G'' va fi mai mic decât cel minim. De aceea rezultă
și am obținut G'' de cost minim în care primele k componente au aceeași valoare
cu cele din Uk. Contradicție.

1mn
)( …)(1 1 nvc vc
)()(k k vc uc
}){ ,('1 k n u VX G 
k jUv
}){\}{ ,(''1 j k n v u VX G 
)()(k j uc vc
)()(k j uc vc
)()(k j uc vc

39 Concluzii

Teoria grafurilor, prin aplicarea algoritmilor combinatoriali, este folosită pentru aflarea
drumului cel mai scurt și mai eficient ca și in problema comis voiajerul cand trebuie să livreze
marfa de la distribuitori la clienți. Deci intreprinderile de livrări de marfă pot să folosească
această strategie pentru ușurarea mun ci lor. Sau problema poștașului care trebuie să găsească
drumul cel mai scurt și mai rapid de la o adresă la alta să livreze scrisorile.
Acești algoritmi sunt foarte utili pentru aceste probleme și sunt eficienți pentru reducerea
timpului de livrare.

Mai pot fi folosiți pentru harta traseurilor autobuzelor în transportul de personae pentru
descoperirea traseurilor acestora, pentru unirea cât mai multor puncte puternic populate.

Grafurile au o importață imensă în informatică, de exemplu: în unele probleme de sortare și
căutare -elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri
într-un graf sau schema logică a unui program se poate reprezenta print -un graf orientat în care o
instrucțiune sau un bloc de instrucțiuni este reprezentat print -un nod, iar muchiile direcționate
reprezintă calea de execuție sau in programare orientată pe obiect, ierarhia obiectelor(claselor)
imio program poate fi reprezentată printr -un graf în care fiecare nod reprezintă o clasă, iar
muchiile rep rezintă relații între acestea.

Teoria grafurilor ne va ajuta să rezolvăm o parte din problemele cu care ne confruntăam în
viața noastră zilnică, problemele rezolvate mai sus sau altele cum ar fi: rețeaua de apă, rețeaua de
canalizare, un traseu montan, vi zitarea mănăstirilor din țara, etc. În această situație ne ajută să
gasim un traseu cu costul cel mai mic și într -un timp rezonabil.

În concluzie spunem că teoria grafurilor a fost descoperită pentru a ne ușura viața și pentru a
realize unele lucruri cât mai rapid și cât mai eficient și cu costuri minime.

40 Bibliografie

1. Reinhard Diestel – Graph Theory (Electronic Edition 2000)
2. Alexandru Ionică, Victoria Iordan, Limbajul Algoritmic, Ed. Mirton, Tm., 1994
3. Sorin Nabadan, Andrea Sandru, Algoritmica Grafurilor, Editura Mirton, Timisoara,
2007.
4. T.H. Cormen, C.E. Leiserson, R.R. Rivest, Introducere i n algoritmi , Editura Computer
Libris Agora, Cluj Napoca, 2000.
5. R. Sedgewick, K Wayne – curs de algoritmi Princeton 2007
6. Silviu Barză, Luciana Maria Morogan, Algoritmica grafurilor, E ditur a Fundałiei
România de mâine, 2008
7. Alexandru Ionică, Algoritmizarea problemelor de ordonanțare, Ed. Mirton, Tm., 1999
8. C.Giumale ,Introducere in analiza algoritmilor: teorie si aplicat ie, Editura Polirom, Iasi,
2004.
9. Alexandru Ionic ă, Grafuri poligonale Kalmanson și aplicații , Editura Tehnic ă Militară,
Bucur ești, 2003
10. Alexandru Ionic ă, Michal Tuska, Elena Giorgiana Ionică, Cristian Alexandru Ionică,
Recursivitate si sortare, Vol I , Editura IVAN KRASKO, Nadlac -Arad-România, 2005
11. Alexandru Ionic ă, Michal Tuska, Elena Giorgiana Ionică, Cristian Alexandru Ionică,
Recursivitate si sortare, Vol II , Editura IVAN KRASKO, Nadlac -Arad -România, 2006
12. Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, Introducere in algoritmi ,
Editura Agora, 2000
13. http://www.scritub.com/stiinta/informatica/Algoritmi -pentru -gasirea -arbor95215.php
14. http://www.scrigroup.com/calculatoare/ELEMENTE -DE-TEORIA -GRAFURILOR –
92383.php

41 Anexa

Cod sursa Algoritm Kruskal

Project Client

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Kruskal
{
public partial class frmCost : Form
{
public int _cost;

public frmCost()
{
InitializeComponent();
}

private void btnOk_Click( object sender, EventArgs e)
{
if (txtCost.Text == string .Empty)
{
errorProvider1.SetError(txtCost, "Care este costul?" );
}
else
{
_cost = int.Parse(txtCost.Text);
this.Close();
}
}

private void txtCost_KeyPress( object sender, KeyPressEventArgs e)
{
e.Handled = ! Char .IsDigit(e.KeyChar);
}
}
}

namespace Kruskal
{
partial class frmCost

42 {
/// <summary>
/// Required designer variable.
/// </summary>
private System.ComponentModel. IContainer components = null;

/// <summary>
/// Clean up any resources being used.
/// </summary>
/// <param name="disposing"> true if managed resources should be disposed; otherwise,
false. </param>
protected override void Dispose( bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}

#region Windows Form Designer generated code

/// <summary>
/// Required method for Designer support – do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.components = new System.ComponentMod el.Container ();
this.btnOk = new System.Windows.Forms. Button ();
this.txtCost = new System.Windows.Forms. TextBox ();
this.errorProvider1 = new System.Windows.Forms. ErrorProvider (this.components);
((System.ComponentModel. ISupportInitialize )(this.errorProvider1)).BeginInit();
this.SuspendLayout();
//
// btnOk
//
this.btnOk.Location = new System.Drawing. Point (30, 35);
this.btnOk.Name = "btnOk" ;
this.btnOk.Size = new System.Drawing. Size(75, 23);
this.btnOk.TabIndex = 1;
this.btnOk.Text = "&Ok" ;
this.btnOk.UseVisualStyleBackColor = true;
this.btnOk.Click += new System. EventHandler (this.btnOk_Click);
//
// txtCost
//
this.txtCost.Location = new System.Drawing. Point (17, 7);
this.txtCost.Name = "txtCost" ;
this.txtCost.Size = new System.Drawing. Size(100, 20);

43 this.txtCost.TabIndex = 0;
this.txtCost.KeyPress += new
System.Windows.Forms. KeyPressEventHandler (this.txtCost_KeyPress);
//
// errorProvider1
//
this.errorProvider1.ContainerControl = this;
//
// frmCost
//
this.AcceptButton = this.btnOk;
this.AutoScaleDimensions = new System.Drawing. SizeF (6F, 13F);
this.AutoScaleMode = System.Wind ows.Forms. AutoScaleMode .Font;
this.ClientSize = new System.Drawing. Size(141, 63);
this.ControlBox = false ;
this.Controls.Add( this.txtCost);
this.Controls.Add( this.btnOk);
this.FormBorderStyle = Sy stem.Windows.Forms. FormBorderStyle .FixedSingle;
this.MaximizeBox = false ;
this.MinimizeBox = false ;
this.Name = "frmCost" ;
this.StartPosition = System.Windows.Forms. FormStartPosition .CenterScreen;
this.Text = "Cost" ;
((System.ComponentModel. ISupportInitialize )(this.errorProvider1)).EndInit();
this.ResumeLayout( false );
this.PerformLayout();

}

#endregion

private System.Windows. Forms. Button btnOk;
private System.Windows.Forms. TextBox txtCost;
private System.Windows.Forms. ErrorProvider errorProvider1;
}
}

namespace Kruskal
{
partial class frmMain
{
/// <summary>
/// Required designer va riable.
/// </summary>
private System.ComponentModel. IContainer components = null;

/// <summary>
/// Clean up any resources being used.
/// </summary>

44 /// <param name="disposing"> true if managed resources should be disposed; otherwise,
false. </param>
protected override void Dispose( bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(di sposing);
}

#region Windows Form Designer generated code

/// <summary>
/// Required method for Designer support – do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.panel1 = new System.Windows.Forms. Panel ();
this.butonRezolva = new System.Windows.Forms. Button ();
this.butonReseteaza = new System.Windows.Forms. Button ();
this.SuspendLayout();
//
// panel1
//
this.panel1.BackColor = System.Drawing. Color .White;
this.panel1.Location = new System.Drawing. Point (12, 12);
this.panel1.Name = "panel1" ;
this.panel1.Size = new System.Drawing. Size(524, 429);
this.panel1.TabIndex = 0;
this.panel1.Paint += new
System.Windows.Forms. PaintEventHandler (this.panel1_Paint);
this.panel1.MouseClick += new
System.Windows .Forms. MouseEventHandler (this.panel1_MouseClick);
//
// butonRezolva
//
this.butonRezolva.Location = new System.Drawing. Point (576, 341);
this.butonRezolva.Name = "butonRezolva" ;
this.butonRezolva.Size = new System.Drawing. Size(75, 23);
this.butonRezolva.TabIndex = 1;
this.butonRezolva.Text = "&Rezolva" ;
this.butonRezolva.UseVisualStyleBackColor = true;
this.butonRezolva.Click += new System. EventHandler (this.butonRezolva_Click);
//
// butonReseteaza
//
this.butonReseteaza.Location = new System.Drawing. Point (576, 34);
this.butonReseteaza.Name = "butonReseteaza" ;

45 this.butonReseteaza.Size = new System.Drawing. Size(75, 23);
this.butonReseteaza.TabIndex = 2;
this.butonReseteaza.Text = "&Reseteaza" ;
this.butonReseteaza.UseVisualStyleBackColor = true;
this.butonReseteaza.Cl ick += new System. EventHandler (this.butonReseteaza_Click);
//
// frmMain
//
this.AutoScaleDimensions = new System.Drawing. SizeF (6F, 13F);
this.AutoScaleMode = System.Windows.Forms. AutoScaleMode .Font;
this.BackColor = System.Drawing. SystemColors .ControlLight;
this.ClientSize = new System.Drawing. Size(694, 453);
this.Controls.Add( this.butonReseteaza);
this.Controls.Add( this.butonRezolva);
this.Controls.Add( this.panel1);
this.FormBorderStyle = System.Windows.Forms. FormBorderStyle .FixedSingle;
this.MaximizeBox = false ;
this.Name = "frmMain" ;
this.StartPosition = System.Windows.Forms. FormStartPosition .CenterScreen;
this.Text = "Kruskal Algorithm" ;
this.ResumeLayout( false );

}

#endregion

private System.Windows.Forms. Panel panel1;
private System.Windows.Forms. Button butonRezolva;
private System.Windows.Forms. Button butonReseteaza;
}
}

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

namespace Kruskal
{
public partial class frmMain : Form
{

#region Member Variables

const int _radius = 20;
const int _halfRadius = (_radius / 2);

Color culoarepunct = Color .Aqua;
Color culoaremuchie = Color .Red;

46 IList<Punct > varfuri;
IList<Muchie > _graph, _graphSolved;

Punct _primpunct, _urmpunct;

bool deseneazamuchie, _rezolvat;

#endregion

public frmMain()
{
InitializeComponent();
Clear();
}

#region Events

private void panel1_MouseClick( object sender, MouseEventArgs e)
{
Point clicked = new Point (e.X – _halfRadius, e.Y – _halfRadius);
if (Control .ModifierKeys == Keys .Control) //daca Ctrl este apasat
{
if (!desen eazamuchie)
{
_primpunct = SelecteazaPunct(clicked);
deseneazamuchie = true;
}
else
{
_urmpunct = SelecteazaPunct(clicked);
deseneazamuchie = false ;
if (_primpunct != null && _urmpunct != null && _primpunct.Name !=
_urmpunct.Name)
{
frmCost formCost = new frmCost ();
formCost.Show Dialog();

Point stringPoint = GetStringPoint(_primpunct.Position, _urmpunct.Position);
_graph.Add( new Muchie (_primpunct, _urmpunct, formCost._cost,
stringPoint));
panel1.Invalidate();
}
}
}
else
{
varfuri.Add( new Punct (varfuri.Count, clicked));
panel1.Invalidate();
}
}

47
private void panel1_Paint( object sender, PaintEventArgs e)
{
Graphics g = e.Graphics;
DeseneazaVarfuri(g);
DeseneazaMuchii(g);
g.Dispose();
}

private void butonRezolva_Click( object sender, EventArgs e)
{
if (varfuri.Count > 2)
{
if (_graph.Count < varfuri.Count – 1)
{
MessageBox .Show( "Lipsa muchii" , "Atentie" , MessageBoxButtons .OK,
MessageBoxIcon .Exclamation);
}
else
{
butonRezolva.Enabled = false ;
IKruskal kruskal = new Kruskal ();
int totalCost;
_graphSolved = kruskal.Solve(_graph, out totalCost);
_rezolvat = true;
panel1.Invalidate();
MessageBox .Show( "Costul total: " + totalCost.ToString(), "Solutie" ,
MessageBoxButtons .OK, MessageBoxIcon .Information);
}
}
}

private void butonReseteaza_Click( object sender, EventArgs e)
{
DialogResult dr = MessageBox .Show( "Reseteaza ?" , "Atentie!" ,
MessageBoxButtons .YesNo, MessageBoxIcon .Exclamation);
if (dr == DialogResult .Yes)
{
butonRezolva.Enabled = true;
Graphics g = panel1.CreateGraphics();
g.Clear(panel1.BackColor);
Clear();
}
}

#endregion

#region Private Method s

private void DeseneazaMuchii( Graphics g)

48 {
Pen p = new Pen(culoaremuchie);
var muchii = _rezolvat ? _graphSolved : _graph;

foreach (Muchie e in muchii)
{
Point v1 = new Point (e.V1.Position.X + _halfRadius, e.V1.Position.Y +
_halfRadius);
Point v2 = new Point (e.V2.Position.X + _halfRadius, e.V2.Position.Y +
_halfRadius);
g.DrawLine(p, v1, v2);
DrawString(e.Cost.ToString(), e. StringPosition, g);
}
}

private void DrawString( string strText, Point pDrawPoint, Graphics g)
{
Font drawFont = new Font("Arial" , 15);
SolidBrush drawBrush = new SolidBrush (Color .Black);
g.DrawString(strText, drawFont, drawBrush, pDrawPoint);
}

private void DeseneazaVarfuri( Graphics g)
{
Pen p = new Pen(culoarepunct);
Brush b = new SolidBrush (culoarepunct);
foreach (Punct v in varfuri)
{
g.DrawEllipse(p, v.Position.X, v.Position.Y, _radius, _radius);
g.FillEllipse(b, v.Position.X, v.Position.Y, _radius, _radius);
DrawString(v.Name.ToString(), v.Position, g);
}
}

private Punct SelecteazaPunct( Point pClicked)
{
foreach (Punct v in varfuri)
{
var distance = Distanta(v.Position, pClicked);
if (distance <= _radius)
{
return v;
}
}
return null;
}

private double Distanta( Point start, Point end)
{
return Math .Sqrt( Math .Pow(start.X – end.X, 2) + Math .Pow(start .Y – end.Y, 2));

49 }

private Point GetStringPoint( Point start, Point end)
{
int X = (start.X + end.X) / 2;
int Y = (start.Y + end.Y) / 2;
return new Point (X, Y);
}

private void Clear()
{
varfuri = new List<Punct >();
_graph = new List<Muchie >();
_rezolvat = false ;
_primpunct = _urmpunct = null;
}

#endregion
}
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;

namespace Kruskal
{
static class Program
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread ]
static void Main()
{
Application .EnableVisualStyles();
Application .SetCompatibleTextRenderingDefault( false );
Application .Run( new frmMain ());
}
}
}

Project Kruskal

namespace Kruskal
{
using System.Collections.Generic;

public interface IKruskal

50 {
IList<Muchie > Solve( IList <Muchie > graph, out int totalCost);
}
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace Kruskal
{
public class Muchie : IComparable
{
#region Members

private Punct v1, v2;
private int cost;
private Point stringPosition;

#endregion

#region Public Properties

public Punct V1
{
get
{
return v1;
}
}

public Punct V2
{
get
{
return v2;
}
}

public int Cost
{
get
{
return cost;
}
}

51 public Point StringPosition
{
get
{
return stringPosition;
}
}

#endregion

#region Constructor

public Muchie( Punct v1, Punct v2, int cost, Point stringPosition)
{
this.v1 = v1;
this.v2 = v2;
this.cost = cost;
this.stringPosition = stringPosition;
}

#endregion

#region IComparable Members

public int CompareTo( object obj)
{
Muchie e = (Muchie )obj;
return this.cost.CompareTo(e.cost);
}

#endregion
}
}

using System;
using System.Drawing;

namespace Kruskal
{
public class Punct
{
#region Members

private int name;

#endregion

#region Public Properties

public int Name

52 {
get
{
return name;
}
}

public int Rang { get; set; }

public Punct Origine { get; set; }

public Point Position { get; set; }

#endregion

#region Constructor

public Punct( int name, Point position)
{
this.name = name;
this.Rang = 0;
this.Origine = this;
this.Position = position;
}

#endregion

#region Methods

internal Punct GasesteOrigine()
{
if (this.Origine != this)//sunt unicul parinte ? (sunt unica origine ?)
{
this.Origine = this.Origine.GasesteOrigine(); // Nu? atunci gaseste -mi originea.
}

return this.Origine;
}

internal static void Join( Punct origine1, Punct origine2)
{
if (origine2.Rang < origine1.Rang) // rangul originine2 este mai mic decat rangul
origine2?
{
origine2.Origine = origine1; //da! atunci origine1 este parintele origine2.
}
else // rangul origine2 este mai mare sau egal cu origine1
{
origine1.Origine = origine2; //faceti -l pe origine2 parinte
if (origine1.Rang == origine2.Rang) // amb ele ranguri sunt egale?

53 {
origine2.Rang++; //incrementeaza origine2, trebuie sa ajungem la o singura
origine pentru tot arborele
}
}
}

#endregion
}
}

namespace Kruskal
{
using System.Collections.Generic;
using System.Linq;

public class Kruskal : IKruskal
{
#region IKruskal

IList<Muchie > IKruskal .Solve( IList<Muchie > graph, out int totalCost)
{
QuickSort(graph, 0, graph.C ount – 1);
IList<Muchie > solvedGraph = new List<Muchie >();
totalCost = 0;

foreach (Muchie ed in graph)
{
Punct origine1 = ed.V1.GasesteOrigine();
Punct origine2 = ed.V2.Gasest eOrigine();

if (origine1.Name != origine2.Name)
{
totalCost += ed.Cost;
Punct .Join(origine1, origine2);
solvedGraph.Add(ed);
}
}

return solvedGraph;
}

#endregion

#region Private Methods

private void QuickSort( IList <Muchie > graph, int left, int right)
{
int i, j, x;
i = left; j = right;

54 x = gr aph[(left + right) / 2].Cost;

do
{
while ((graph[i].Cost < x) && (i < right))
{
i++;
}

while ((x < graph[j].Cost) && (j > left))
{
j–;
}

if (i <= j)
{
Muchie y = graph[i];
graph[i] = graph[j];
graph[j] = y;
i++;
j–;
}
}
while (i <= j);

if (left < j)
{
QuickSort(graph, left, j);
}

if (i < right)
{
QuickSort(graph, i, right);
}
}

#endregion
}
}