Implementarea Unor Algoritmi de Calcul a Distantelor Minime In Grafuri Finite

CAPITOLUL I

CONCEPTUL DE GRAF FINIT.REPREZENTARE.EXEMPLE.

I.1. Conceptul de graf finit.Noțiuni generale.

În general, pentru situațiile care necesită la rezolvare un oarecare efort mintal (și un caz tipic este cel al celor din economie), se caută, în primul rând, o metodă de reprezentare a lor care să permită receptarea întregii probleme dintr-o privire (pe cât posibil) și prin care să se evidențieze cât mai clar toate aspectele acesteia.

În acest scop se folosesc imagini grafice gen diagrame, schițe, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate în special pentru vizualizarea sistemelor și situațiilor complexe. În general, vom reprezenta componentele acestora prin puncte în plan iar relațiile (legăturile, dependențele, influențele etc) dintre componente prin arce de curbă cu extremitățile în punctele corespunzătoare. Între două puncte pot exista unul sau mai multe segmente (în funcție de câte relații dintre acestea, care ne interesează, există) iar segmentelor li se pot asocia sau nu orientări (după cum se influențează cele două componente între ele), numere care să exprime intensitatea relațiilor dintre componente etc.

Este evident, totuși, că această metodă are limite, atât din punct de vedere uman (prea multe puncte și segmente vor face desenul atât de complicat încât se va pierde chiar scopul pentru care a fost creat – claritatea și simplitatea reprezentării, aceasta devenind neinteligibilă) cât și din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

Din acest motiv, alături de expunerea naiv-intuitivă a ceea ce este un graf, dată mai sus, se impune atât o definiție riguroasă cât și alte modalități de reprezentare a acestora, adecvate în general rezolvărilor matematice.

Definiția I.1.1. Se numește multigraf un triplet G = (X, A, f) în care X și A sunt două mulțimi iar f este o funcție, definită pe produsul cartezian al lui X cu el însuși (X2 = XX), care ia valori în mulțimea părților mulțimii A (notată P(A))

Mulțimea X se numește mulțimea nodurilor multigrafului și elementele sale se numesc noduri (sau vârfuri) ale multigrafului, iar A reprezintă mulțimea relațiilor (legăturilor) posibile între două noduri ale multigrafului.

Definiția I.1.2. Se numește graf orientat un multigraf în care mulțimea A are un singur element: A = {a}.

Exemplul I.1.1. Fie graful urmator:

Fig. I.1.1.

Mulțimea nodurilor acestui graf este X={x1,x2,x3,x4}, iar mulțimea arcelor sale este U={[x1,x2], [x1,x4], [x2,x1], [x3,x2], [x3,x4]}.

În acest caz mulțimea părților mulțimii A are doar două elemente: mulțimea vidă și întreaga mulțime A. Dacă unei perechi orientate

(xi, xj) din X2 i se asociază prin funcția f mulțimea A atunci spunem ca există arc de la nodul xi la nodul xj iar perechea (xi,xj) se va numi arcul (xi,xj).

Nodul xi se numește nod inițial sau extremitate inițială a arcului (xi,xj) iar nodul xj se numește nod final sau extremitate finală a arcului (xi,xj). Arcul (xi,xj) este incident spre interior vârfului xj și incident spre exterior vârfului xi. Dacă pentru un arc nodul inițial coincide cu nodul final atunci acesta se numește buclă. Nodurile xi și xj se vor numi adiacente dacă există cel puțin unul din arcele (xi,xj) și (xj,xi).

Dacă unei perechi orientate (xi, xj) din X2 i se asociază prin funcția f mulțimea vidă atunci spunem că nu există arc de la nodul xi la nodul xj.

Este evident că a cunoaște un graf orientat este echivalent cu a cunoaște vârfurile și arcele sale. Din acest motiv putem defini un graf orientat prin perechea (X,U), unde X este mulțimea nodurilor sale iar U mulțimea arcelor sale.

De asemenea, putem cunoaște un graf orientat cunoscând mulțimea nodurilor și, pentru fiecare nod, mulțimea arcelor incidente spre exterior. Din acest motiv putem defini un graf orientat ca o pereche (X,) unde X este perechea nodurilor iar este o funcție definită pe X cu valori în mulțimea părților lui X, valoarea acesteia într-un nod xi, (xi) X fiind mulțimea nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea inițială.

Definiția I.1.3. Se numește graf neorientat un multigraf în care mulțimea A are un singur element iar funcția f are proprietatea:

f[(xi,xj)] = f[(xj,xi)] , oricare ar fi nodurile xi și xj din X.

Exemplul I.1.2. Figura de mai jos reprezinta un graf neorientat.

Fig. I.1.2.

Se observă proprietatea de simetrie între oricare 2 noduri ale grafului.

În aceste condiții, dacă f[(xi,xj)] = f[(xj,xi)] = A atunci perechea neorientată {xi,xj} este o muchie iar dacă f[(xi,xj)] = f[(xj,xi)] = spunem că nu există muchie între vârfurile xi și xj.

Pentru simplificarea expunerii vom folosii denumirea de graf in locul celei de graf orientat,iar dacă se vor folosi grafurile neorientate se va specifica acest lucru.

I.2. Concepte de bază în teoria grafurilor.

c1. semigraf interior al unui nod xk: este mulțimea arcelor = {(xj,xk)/ (xj,xk) U} care sunt incidente spre interior nodului xk;

c2. semigraf exterior al unui nod xk: este mulțimea arcelor = {(xk,xi)/ (xk,xi) U} care sunt incidente spre exterior nodului xk;

Exemplul I.2.1.

Fig. I.2.1.

Pentru graful din figura I.2.1. avem:

c3. semigradul interior al unui nod xk: este numărul arcelor care sunt incidente spre interior nodului xk = cardinalul lui și se notează cu ;

c4. semigradul exterior al unui nod xk: este numărul arcelor care sunt incidente spre exterior nodului xk = cardinalul lui și se notează cu ;

c5. gradul unui nod xk: este suma semigradelor nodului xk:= + ;

Exemplul I.2.2.

Pentru graful reprezentat în figura I.2.1. avem:

c6. nod izolat: este un nod cu gradul 0;

c7. nod terminal: este un nod cu gradul 1;

Exemplul I.2.3.

Fig. I.2.2.

Se observă că nodul x4 este nod terminal având ; iar nodul x5 este nod izolat având

c8. arce adiacente: arce care au o extremitate comună;

c9. drum într-un graf: o mulțime ordonată de noduri ale grafului:

(x1, x2, …, xk), cu proprietatea că există în graf toate arcele de forma (xi,xi+1), unde i = 1,…,k-1;

c10. lungimea unui drum: este numărul arcelor care îl formează;

c11. drum elementar: un drum în care fiecare nod apare o singură dată;

c12. drum simplu: un drum în care fiecare arc apare o singură dată;

Exemplul I.2.4.

Fig. I.2.3.

Pentru graful de mai sus avem drumul elementar [x1; x2; x3; x4; x5]

c13. puterea de atingere a unui nod xi X în graful G: numărul de noduri la care se poate ajunge din xi. Puterea de atingere se notează cu p(xi), 1in și evident p(xi) .

c14. drum hamiltonian: un drum elementar care trece prin toate nodurile grafului;

c15. lanț: un drum în care arcele nu au neapărat același sens de parcurgere;

Exemplul I.2.5.

Fig. I.2.4.

Pentru graful reprezentata mai sus avem drumul hamiltonian

L = [x1; x2; x3; x4; x5].

c16. circuit: un drum în care nodul inițial coincide cu cel final;

c17. circuit elementar: un drum în care fiecare nod apare o singură dată, cu excepția celui final, care coincide cu cel inițial;

Exemplul I.2.6.

Fig. I.2.5.

Pentru graful reprezentat mai sus avem circuitul [x1; x2; x3; x4; x2; x5; x1]; iar [x1; x2; x3; x4; x1;] este circuit elementar.

c18. circuit simplu: un drum în care fiecare arc apare o singură dată;

c19. circuit hamiltonian: un circuit care trece prin toate nodurile grafului;

Exemplul I.2.7.

Pentru graful reprezentat în figura I.2.5. avem circuitul hamiltonian

[x1; x2; x3; x4; x5; x1].

c20. ciclu: este un circuit în care arcele nu au neapărat același sens de parcurgere;

c21. ciclu elementar: un ciclu în care fiecare nod apare o singură dată, cu excepția celui final, care coincide cu cel inițial;

c22. ciclu simplu: un ciclu în care fiecare arc apare o singură dată;

Observație:

Într-un graf neorientat noțiunile de drum și lanț sunt echivalente și de asemenea cele de circuit și ciclu.

c23. graf parțial al unui graf G = (X,U): este un graf G'(X,U') cu U' U;

Exemplul I.2.8.

Fie graful din figura I.2.6. a) cu X={x1; x2; x3; x4; x5; x6} și U={[x1,x2]; [x1,x3]; [x1,x4]; [x1,x5]; [x2,x4]; [x3,x5]; [x3,x6]; [x4,x5]; [x5,x6]}. Eliminând muchiile [x1,x3]; [x1,x5]; [x3,x5] și [x3,x6] se obține, (fig. I.2.6. b)) graf parțial al grafului dat cu aceeași mulțime de noduri

X={x1; x2; x3; x4; x5; x6} și mulțimea muchiilor .

b)

Fig. I.2.6.

c24. subgraf al unui graf G = (X,): este un graf G'(X',') unde X' X și '(xi) = (xi) X' pentru orice xi X';

Exemplul I.2.9.

Folosind graful din figura I.2.6. considerăm și se obține subgraful din figura I.2.7.

Fig. I.2.7.

Se poate spune că un subgraf se obține prin suprimarea într-un graf a unei mulțimi de noduri și a tuturor muchiilor adiacente acestora.

c25. graf redus al unui graf G = (X,U): este un graf G*(X*,U*) unde X* este formată din mulțimile unei partiții de mulțimi nevide ale lui X, iar (,) există doar dacă i j și există cel puțin un arc în U, de la un nod din la un nod din .

I.3. Reprezentarea grafurilor orientate.

Fie G=(X, U) un graf orientat cu m arce și n vârfuri. Pentru simplificarea notației, vom identifica vârfurile prin indicii lor.

Reprezentarea unui astfel de graf se poate realiza prin:

Matricea de adiacență (booleană) asociată grafului, adică o matrice A(n x n) ale cărei elemente sunt:

(1≤i, j≤n)

Necesarul de memorie pentru matricea de adiacență a unui graf este și nu depinde de numărul de muchii ale grafului.

Exemplul I.3.1. Fie matricea de adiacență urmatoare:

Graful orientat G=(X, U) cu X={x1, x2, x3, x4} corespunzător matricei A este urmatorul:

Fig. I.3.1.

Se observă că:

matricea A nu este neapărat simetrică ;

inițializarea tabloului bidimensional A, necesită 0 (n2) operații elementare;

orice algoritm care realizează o astfel de reprezentare a unui graf va avea complexitatea o (n2).

Matricea de incidență vârf – arc pentru grafuri orientate fără bucle. Ea este o matrice B(n x m) cu elemente de forma urmatoare:

Exemplul I.3.2.Matricea de incidență pentru graful orientat din figura I.3.2.

Fig.I. 3.2.

Observații:

numărul elementelor egale cu 1 de pe linia k reprezintă +(xk);

numarul elementelor egale cu -1 de pe linia k reprezintă -(xk);

o linie care are toate elementele egale cu 0 corespunde unui vârf izolat.

Matricea drumurilor. Aceasta este o matrice D(n x n) cu elementele :

Exemplul I.3.3. Pentru graful din figura I.3.3. matricea drumurilor este urmatoarea:

Fig. I.3.3

Observații:

dacă d[i, j]=1 atunci există un circuit care trece prin vârful xi;

dacă linia j și coloana j conține numai zerouri atunci vârful xj este izolat.

(D) Liste de adiacență. Fie G=(X,U) un graf orientat cu n noduri identificate prin indicii lor și m arce. Pentru fiecare nod x din X se consideră lista Spațiul total de memorie utilizat va fi O(n+m). Listele de adiacență pot fi reprezentate static și dinamic.

static, prin intermediul unui tablou bidimensional T[2,n+m] în care:

T[1,j]=j, oricare ar fi  ;

T[2,j] este indicele (coloana) primului element din L[j] ;

dacă este vârf izolat, atunci T[2,j]=0;

dacă T[2,j]=k, atnuci T[1,k] este primul element in L[j], iar T[2,k] este adresa următorului element din lista ce conține pe j ;

dacă r este adresa ultimului element z din L[j] atunci T[1,r]=z, T[2,r]=0.

Exemplul I.3.4. Să considerăm următorul digraf:

Fig.I.3.4.

În exemplul de mai sus se arată modul de reprezentare prin liste

de adiacență a unui digraf G având șase vârfuri și opt muchii.

CAPITOLUL II

ALGORITMI DE DETERMINARE A DISTANȚELOR MINIME DINTRE VÂRFURILE UNUI DIGRAF.

II.1.Noțiuni generale.

Î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 intensitatea 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ăonține pe j ;

dacă r este adresa ultimului element z din L[j] atunci T[1,r]=z, T[2,r]=0.

Exemplul I.3.4. Să considerăm următorul digraf:

Fig.I.3.4.

În exemplul de mai sus se arată modul de reprezentare prin liste

de adiacență a unui digraf G având șase vârfuri și opt muchii.

CAPITOLUL II

ALGORITMI DE DETERMINARE A DISTANȚELOR MINIME DINTRE VÂRFURILE UNUI DIGRAF.

II.1.Noțiuni generale.

Î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 intensitatea 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 aplicațiile economice această valoare poate fi:

lungimea drumului dintre două localități;

costul parcurgerii rutei reprezentate prin arcul corespunzător;

durata parcurgerii rutei respective;

cantitatea transportată pe ruta respectivă;

capacitatea maximă a rutei respective;

câștigul realizat prin trecerea de la o stare la alta a sistemului;

consum de energie pentru efectuarea trecerii respective;

punctaj realizat etc.

Una din problemele care poate apărea în aceste situații este găsirea, pentru o anumită pereche de noduri (sau mai multe perechi), a drumului optim între acestea.

Pentru formalizarea problemei vom introduce noțiunea de valoare a unui drum, care este egală cu suma valorilor arcelor care îl compun. Vom nota în continuare valoarea unui arc (xi,xj) cu v(xi,xj) sau cu vij. În aceste condiții putem enunța problema drumului optim astfel:

"Fiind dat un graf G = (X,U) și o funcție care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/și maximă) între cele două noduri și valoarea acestuia (acestora)"

Deoarece este vorba de găsirea minimului unei mulțimi de numere reale, prima întrebare care se pune este dacă aceasta admite minim. Dacă mulțimea nodurilor grafului este infinită atunci pot exista o infinitate de drumuri elementare distincte între cele două noduri și mulțimea valorilor acestora poate avea orice formă (închisă sau nu, mărginită sau nu) devenind foarte greu de caracterizat cazurile când minimul dorit există. Deoarece totuși majoritatea covârșitoare a problemelor economice se modelează prin grafuri cu număr finit de noduri, ne vom limita în continuare doar la acestea.

Un număr finit de noduri n atrage după sine existența unui număr finit de arce (cel mult n2) și a unui număr finit de drumuri elementare ( cel mult nn! ). Deoarece oricărui drum d îi corespunde un drum elementar de (obținut prin eliminarea tuturor subcircuitelor lui d) putem calcula valoarea oricărui drum ca sumă între valoarea drumului elementar corespunzător și valorile unor subcircuite ale sale, fiecare înmulțită cu numărul de parcurgeri ale circuitului respectiv.

În concluzie, dacă există un circuit de valoare negativă înseamnă că există drumuri de valoare oricât de mică (cele care conțin acest circuit), obținută prin parcurgerea acestuia de oricâte ori dorim) și, deci, mulțimea valorilor drumurilor este nemărginită inferior, neexistând drum de valoare minimă. Dacă există un circuit de valoare pozitivă atunci există drumuri de valoare oricât de mare și mulțimea valorilor drumurilor este nemărginită superior, neexistând drum de valoare maximă.

Dacă nu există circuite de valoare negativă atunci valoarea oricărui drum este mai mare sau egală cu a drumului elementar corespunzător, deci drumul de valoare minimă (dacă există) va fi un drum elementar. Cum mulțimea drumurilor elementare este finită (și deci și mulțimea valorilor lor) va avea minorant și am lămurit problema compatibilității problemei. Analog, dacă nu există circuite de valoare pozitivă atunci valoarea oricărui drum este mai mică sau egală cu a drumului elementar corespunzător, deci drumul de valoare maximă (dacă există) va fi un drum elementar. Cum mulțimea drumurilor elementare este finită (și deci și mulțimea valorilor lor), va avea majorant.

Obs. 1. Dacă în graf nu există decât arce de valoare pozitivă atunci există drum de valoare minimă.

Obs. 2. Dacă în graf nu există decât arce de valoare negativă atunci există drum de valoare maximă.

Obs. 3. Dacă în graf nu există circuite atunci există atât drum de valoare minimă, cât și drum de valoare maximă.

Deoarece din cele de mai sus se sesizează importanța existenței circuitelor într-un graf vom da în continuare un algoritm de depistare a existenței circuitelor într-un graf:

Se construiește mulțimea A formată din nodurile care sunt extremități ale arcelor incidente spre interior ( noduri în care toate arcele "intră" sau, altfel spus, noduri din care nu "pleacă" nici un arc).

Se găsesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealaltă extremitate în A (noduri din care se poate "ajunge" doar in A). Dacă nu există nici un astfel de arc se trece la pasul 4.

Se adaugă arcele găsite la pasul 2 la mulțimea A apoi se reia algoritmul de la pasul 2, pentru noua mulțime A.

Dacă A conține mulțimea tuturor nodurilor atunci graful nu conține circuite. Dacă au rămas noduri în afara lui A atunci graful conține circuite.

II.2.Algoritmi de găsire a drumului optim.

Din cauza varietății nelimitate 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 trei categorii:

Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);

Algoritmi prin ajustări succesive: (Ford);

Algoritmi prin extindere selectivă (Dijkstra).

A. 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 valoare minimă (maximă) de la toate nodurile grafului la un nod oarecare, fixat.

Algoritmul permite de altfel și detectarea eventualelor circuite absorbante ale grafului (un circuit absorbant este un circuit cu cost total negativ).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 G = {x1, x2, … ,xn} 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 xn.

Se construiește matricea pătratică M cu dimensiunea egală cu numărul de noduri ale grafului ale cărei elemente sunt:

mij =

Se adaugă succesiv liniile Li la matricea M, elementele acestora calculându-se prin relațiile de recurență:

L1j = mjn j = 1,…,n (prima linie este ultima coloană, transpusă, a matricii M);

Lij = min (Li-1,j , (mjk + Li-1,k)) într-o problemă de minim

sau Lij = max (Li-1,j , (mjk + Li-1,k)) într-o problemă de maxim;

După calcularea fiecărei linii noi se compară elementele ei cu cele ale precedentei:

Dacă Lij = Li-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 xn;

Dacă există cel puțin un indice j cu Lij Li-1,j se trece la calcularea noii linii Li+1;

Pentru găsirea drumului care dă valoarea minimă de la un nod xj la nodul xn se găsesc, începând înapoi de la ultima linie, pe care s-au obținut valorile finale, notată Lf, nodurile ,,…,care formează drumul căutat, unde = xj, = xn și fiecare alt indice ki+1 este cel pentru care s-a obținut minimul (maximul) de pe poziția ki al liniei Li.

Observație: Pentru grafuri foarte mari, algoritmul necesită un volum mare de memorie, datorită 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.

Exemplul II.2.1. Presupunem dat graful orientat de mai jos, în care se dorește găsirea drumului de valoare minimă de la nodul x1 la nodul x9.

Fig.II.2.1

Matricea M va fi

iar după calcularea liniilor Li obținem:

Deoarece L4 = L5 oprim calcularea liniilor după calcularea liniei 5. În această linie se află valorile celor mai scurte de la toate nodurile la nodul x9. Drumul dorit de noi (x1 x9) 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:

B. 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 xi și xj. Printr-o eventuală renumerotare a nodurilor putem presupune că nodul de la care pornește drumul este x1, care va fi numit nod inițial, iar nodul la care se termină este xn, numit nod final.

Algoritmul este:

I se dă vârfului inițial valoarea 0 (zero): w(x0) = 0

Se construiește mulțimea A formată din nodul inițial: A = {x1}

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(xi) = , în problemele de minim

sau

w(xi) = , î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 x1 la xn. STOP

Se analizează mulțimea A:

Dacă xn A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de la x1 la xn. Pentru găsirea acestui drum se pornește înapoi de la nodul final xn și se găsesc nodurile ,, …, care formează drumul căutat, unde = xn, = x1 și fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

Dacă xn A se reia algoritmul de la pasul 3.

Exemplul II.2.2. Pentru graful din figura II.2.1 să determinăm valoarea drumului minim între nodurile x1 și x9 . Vom avea succesiv:

pas1: w(x1) = 0;

pas2: A = {x1} ;

pas3: Nodurile în care se poate ajunge doar din x1: {x5}

w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5;

pas4: x9 A;

pas3: A = {x1,x5} și nodurile în care se poate ajunge prin arce directe doar din x1 și x5 sunt: {x6}

w{x6) = min( w(x1) + v(x1,x6), w(x5) + v(x5,x6)) = min(0 + 3,5+3)=3;

pas4: x9 A;

pas3: A = {x1,x5,x6} și nodurile în care se poate ajunge prin arce directe doar din x1, x5 și x6 sunt: {x2,x7}

w{x2) = min( w(x1) + v(x1,x2), w(x5) + v(x5,x2), w(x6) + v(x6,x2)) = min(0 + 4,5 + 8,3 + 8) = 4;

w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7;

pas4: x9 A;

pas3: A = {x1,x2,x5,x6,x7} și nodurile în care se poate ajunge prin arce directe doar din x1, x2, x5, x6 și x7 sunt: {x3,x8}

w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7;

w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13;

pas4: x9 A;

pas3: A = {x1,x2,x3,x5,x6,x7,x8} și nodurile în care se poate ajunge prin arce directe doar din x1, x2,x3,x5, x6, x7 și x8 sunt: {x4}

w{x4) = min( w(x2) + v(x2,x4), w(x3) + v(x3,x4),w(x5) + v(x5,x4), w(x8) + v(x8,x4)) = min(4 + 9,7 + 3,5 + 7,13 + 4) = 10;

pas4: x9 A;

pas3: A = {x1,x2,x3,x4,x5,x6,x7,x8} și nodurile în care se poate ajunge prin arce directe doar din x1, x2, x3, x4, x5, x6, x7 și x8 sunt: {x9}

w{x9) = min( w(x3) + v(x3,x9), w(x4) + v(x4,x9), w(x7) + v(x7,x9), w(x8) + v(x8,x9)) = min(7 + 9, 10 + 3, 7 + 8, 13 + 7) = 13;

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

Avem succesiv:

w(x9) = w(x4) + v(x4,x9)

w(x4) = w(x3) + v(x3,x4)

w(x3) = w(x5) + v(x5,x3)

w(x5) = w(x1) + v(x1,x5)

deci drumul căutat este: x1 x5 x3 x4 x9

Observația 1. 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 x1 la xn care trece prin unul din nodurile circuitului nu vom putea da valoare nici lui xn, cu toate că există drum de la x1 la xn.

Observația 2: Algoritmul necesită pentru memorare și manipulare doar cunoașterea, pentru fiecare nod, a nodurilor spre care "pleacă" arce din acesta și valorile acestor arce, fiind mult mai ușor de aplicat sau implementat pe calculator. El are însă dezavantajul că se poate aplica doar în grafuri fără circuite.

C. Algoritmul Ford generalizat

Algoritmul lui Ford generalizat a fost creat cu scopul de a putea găsi drumul optim și în grafurile care au circuite. Cu ajutorul lui se găsește drumul de valoare optimă între două noduri fixate xi și xj.

Printr-o eventuală renumerotare a nodurilor putem presupune că nodul de la care pornește drumul este x1, care va fi numit nod inițial, iar nodul la care se termină este xn, numit nod final.

Algoritmul este:

I se dă vârfului inițial valoarea 0 (zero): w(x0) = 0 și tuturor celelalte valoarea + (într-o problemă de minim) sau – (într-o problemă de maxim).

În ordinea crescătoare a indicilor nodurilor se calculează pentru fiecare nod, pe bază fostelor valori, noile valori cu formula:

w*(xi) = în problemele de minim

sau

w*(xi) = în problemele de maxim

Se compară noile valori w*(xi) cu fostele valori w(xi):

Dacă w*(xi) = w(xi) pentru orice nod xi atunci:

1) dacă w(xn) < (la problema de minim) sau w(xn) > – (la problema de maxim), valoarea nodului xn reprezintă valoarea drumului de valoare minimă(maximă) de la x1 la xn. Pentru găsirea acestui drum se pornește înapoi de la nodul final xn și se găsesc nodurile ,, …, care formează drumul căutat, unde = xn, = x1 și fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

2) dacă w(xn) = + (-) atunci nu există nici un drum de la x1 la xn. STOP

Dacă există cel puțin un nod pentru care w*(xi) < w(xi) se reia algoritmul de la pasul 2 pentru noile valori ale vârfurilor.

Observație: Algoritmul poate găsi drumul și în grafuri cu circuite dar este evident mult mai lent decât cel simplificat. Pentru scurtarea duratei de

execuție se poate modifica algoritmul în sensul că o valoare nou calculată a unui vârf va fi folosită imediat ca atare la calculul noilor valori ale celorlalte, nu doar după ce se calculează noile valori ale tuturor vârfurilor.

D. 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 foarte 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 optim. În plus, algoritmul se poate aplica și în drumuri cu circuite. Acest algoritm se poate aplica doar la probleme de minim.

Algoritmul are următorii pași:

I se dă vârfului inițial valoarea 0 (zero): w(x0) = 0;

Se construiește mulțimea A formată din nodul inițial: A = {x1};

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(xi) = î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 x1 la xn. STOP

Se analizează mulțimea A:

Dacă xn A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de la x1 la xn. Pentru găsirea acestui drum se pornește înapoi de la nodul final xn și se găsesc nodurile ,, …, care formează drumul căutat, unde = xn, = x1 și fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

Dacă xn A se reia algoritmul de la pasul 3.

Exemplul II.2.3. Vom aplica algoritmul la graful din figura II.2.1,pentru a putea face comparații:

pas1: w(x1) = 0;

pas2: A = {x1};

pas3: Nodurile în care se poate ajunge și din x1: {x2, x5, x6}

w{x2) = min( w(x1) + v(x1,x2)) = 0 + 4 = 4;

w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5;

w{x6) = min( w(x1) + v(x1,x6)) = 0 + 3 = 3;

min(w{x2),w{x5),w{x6)) = w{x6) = 3;

pas4: x9 A;

pas3: A = {x1,x6} și nodurile în care se poate ajunge prin arce directe din x1 sau x6 sunt: {x2,x5,x7}

w{x2) = min( w(x1) + v(x1,x2), w(x6) + v(x6,x2)) = min(0 + 4 , 3 + 8) = 4;

w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5;

w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 8;

min(w{x2),w{x5),w{x7)) = w{x2) = 4;

pas4: x9 A;

pas3: A = {x1,x2,x6} și nodurile în care se poate ajunge prin arce directe din x1, x2 sau x6 sunt: {x3,x4,x5,x7}

w{x3) = min( w(x2) + v(x2,x3)) = min(4 + 7) = 11;

w{x4) = min( w(x2) + v(x2,x4)) = min(2 + 9) = 11;

w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5;

w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 0;

min(w{x3),w{x4),w{x5),w{x7)) = w{x5) = 5;

pas4: x9 A;

pas3: A = {x1,x2,x5,x6} și nodurile în care se poate ajunge prin arce directe din x1, x2, x5, x6 și x7 sunt: {x3,x4,x7,x8}

w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7;

w{x4) = min( w(x2) + v(x2,x4), w(x5) + v(x5,x4)) = min(4 + 9,5 + 7) = 12;

w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7;

w{x8) = min( w(x5) + v(x5,x8)) = min(5 + 9) = 14;

min(w{x3),w{x4),w{x7),w{x8)) = w{x3) = w{x7) = 7;

pas4: x9 A;

pas3: A = {x1,x2,x3,x5,x6,x7} și nodurile în care se poate ajunge prin arce directe din x1, x2, x3, x5, x6, și x7 sunt: {x4,x8,x9}

w{x4) = min( w(x2) + v(x2,x4), w(x3) + v(x3,x4),w(x5) + v(x5,x4)) = min(4 + 9,7 + 3,5 + 7) =10;

w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13;

w{x9) = min( w(x3) + v(x3,x9), w(x7) + v(x7,x9)) = min(7 + 9,7 + 8) = 15;

min(w{x4),w{x8),w{x9)) = w{x4) = 10;

pas4: x9 A;

pas3: A = {x1,x2,x3,x4,x5,x6,x7} și nodurile în care se poate ajunge prin arce directe din x1, x2, x3, x4, x5, x6, și x7 sunt: {x8,x9}

w{x9) = min( w(x3) + v(x3,x9), w(x4) + v(x4,x9), w(x7) + v(x7,x9)) = min(7 + 9,10 + 3,7+8)=13;

w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13;

min(w{x8),w{x9)) = w{x8) = w{x9) = 13;

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

Avem succesiv:

w(x9) = w(x4) + v(x4,x9)

w(x4) = w(x3) + v(x3,x4)

w(x3) = w(x5) + v(x5,x3)

w(x5) = w(x1) + v(x1,x5)

deci drumul căutat este: x1 x5 x3 x4 x9.

CAPITOLUL III

ALGORITMI DE DETERMINARE A UNOR CIRCUITE NEGATIVE DINTR-UN DIGRAF.APLICAȚII.

III.1. Drumuri și circuite hamiltoniene.

Una dintre cele mai cunoscute probleme economice este problema comis voiajorului. Comis voiajorul este un individ care trebuie să prezinte s-au să distribuie marfa comandată la o serie de centre distribuite în general neliniar pe o anumită zonă teritorială (localitățile dintr-un județ, magazinele dintr-un cartier, persoanele dintr-un sat etc). Dacă numărul de obiective care trebuie vizitate este mare sau foarte mare iar timpul disponibil foarte limitat atunci devine vitală o asemenea organizare a trecerii pe la fiecare obiectiv încât să se efectueze în timpul minim posibil. Acest timp minim se traduce prin drumul cel mai scurt, iar cel mai scurt drum este evident cel în care se trece pe la fiecare obiectiv o singură dată. În plus, la sfârșit trebuie să se afle în punctul inițial, adică sediul firmei la care lucrează.

O reprezentare a regiunii aprovizionate, în care centrele 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ă.

În timp, s-au evidențiat o multitudine de probleme reductibile la găsirea unui drum (sau circuit) hamiltonian într-un graf, cum ar fi:

Problema poștașului (găsirea traseului cel mai scurt care trece pe la toate locuințele ce aparțin de oficiul poștal la care lucrează acesta);

Problema adunării deșeurilor (cel mai scurt drum care trece pe la toate punctele de depozitate a deșeurilor);

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 componente electronice pe o placă, etc;

III.2.Determinarea drumurilor hamiltoniene

Problema determinării drumului (circuitului) hamiltonian de valoare optimă s-a dovedit deosebit de dificilă, neexistând nici acum un algoritm care să rezolve problema în timp polinomial și nici măcar o metodă simplă prin care să se decidă dacă într-un graf dat există sau nu drumuri hamiltoniene.

Există însă mai mulți algoritmi, unii exacți alții heuristici, care reușesc, într-un caz sau altul, să rezolve problema satisfăcător și în timp util. Câțiva dintre acești algoritmi sunt prezentați în continuare.

Algoritmul lui Foulkes

Se scrie matricea de adiacență A asociată grafului G.

Se determină matricea D a drumurilor grafului G , apoi se calculează matricea M=I+D;

Se împarte mulțimea nodurilor grafului în submulțimi disjuncte astfel:

1.Se consideră în matricea M liniile pline (cu toate elementele 1). Nodurile ce corespund liniilor pline cu 1 formează submulțimea C1.

2.Se elimină liniile și coloanele care corespund nodurilor din submulțimea stabilită.

3.Se reia raționamentul de la punctul 1 pe matricea redusă obținută la punctul 2 obținându-se următoarea submulțime și în continuare toate celelalte până se epuizează toate liniile matricei.

Se construiește graful G' în care:

Nodurile care formează o submulțime sunt reprezentate prin puncte în interiorul unui dreptunghi și între acestea se trasează arcele existente în graful inițial G.

Se trasează legăturile dintre submulțimi. Ele sunt reprezentate prin arcele existente în graful inițial G între nodurile submulțimii C1 și cele ale submulțimii C2, între nodurile submulțimii C2 și cele ale submulțimii C3 etc.

Se găsesc drumurile hamiltoniene.

Un drum hamiltonian se găsește plecând de la un vârf din submulțimea C1, trecând prin toate vârfurile acesteia cu un drum hamiltonian, din ultimul vârf la care se ajunge în C1 trecând la un vârf din C2, parcurgând în continuare un drum hamiltonian în a doua submulțime și tot așa, trecând prin toate submulțimile și parcurgând, deci, toate nodurile grafului inițial, o singură dată. Aplicând acest procedeu în toate modurile posibile se obțin toate drumurile hamiltoniene din graful inițial G.

(Observație: poate să nu existe nici un drum hamiltonian în graful G, caz în care algoritmul se oprește deoarece la un anumit pas nu mai exista nici o linie plina cu 1).

Observație. Algoritmul lui Foulkes reduce găsirea drumurilor hamiltoniene în graful inițial G (care în problemele practice este foarte mare) la găsirea mai multor drumuri hamiltoniene mai mici în componente tare conexe ale grafului. Dacă un graf are o singură componentă tare conexă, algoritmul lui Foulkes nu este eficient, în acest caz trebuind aplicați alți algoritmi cum ar fi cel bazat pe înmulțirea latină.

B. 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 = {x1, x2, … , xn}. 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 xi la nodul xj atunci evident p(xi) > p(xj), deoarece în orice vârf în care se poate ajunge din xj se poate ajunge și din xi dar din xj nu se poate ajunge în xj pentru că nu există circuite.

Teorema II.2.1 (Chen) Un graf cu n noduri, fără circuite conține un drum hamiltonian dacă și numai dacă există relația:

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 xi se poate ajunge în toate nodurile cu indice mai mare și numai în acestea (altfel ar exista circuite) și deci puterea unui nod xi este n – i, de unde:

= (n – 1) + (n – 2) + … + 1 + 0 =

“” Ordonând vârfurile în ordinea descrescătoare a puterii lor de atingere (i > j p(xi) < p(xj)) și cum graful nu are circuite, vom obține o matrice D cu toate zerourile deasupra diagonalei (evident pe o poziție (i,i) nu se află nici un 1 iar dacă ar fi un 1 pe poziția (i,j) cu i > j ar însemna că din xi se poate ajunge în xj, deci în toate nodurile în care se poate ajunge din xj, iar din xj nu se poate ajunge în xi, deci p(xi) > p(xj) în contradicție cu ipoteza de ordonare a nodurilor). Cum deasupra diagonalei sunt poziții iar suma puterilor vârfurilor este chiar rezultă că toate pozițiile de deasupra diagonalei sunt 1. Aceasta înseamnă că există toate arcele de forma (xi,xi+1) (altfel n-ar exista drum de la xi la xi+1, deoarece toate drumurile au indicii nodurilor în ordine descrescătoare) și deci drumul hamiltonian (x1, x2, … , xn) q.e.d.

Teorema II.2.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 exista două noduri xi și xj în ordinea xi xj pe un drum și invers pe celălalt, existând deci un drum atât de la xi la xj cât și de la xj la xi, 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:

Se scrie matricea de adiacență A

Se calculează matricea drumurilor D

Dacă există un indice i cu dii = 1 atunci graful are circuite, nu se poate aplica algoritmul lui Chen și algoritmul se oprește. Dacă nu, se trece la pasul 4.

Se calculează puterile de atingere pentru fiecare nod.

Dacă nu se verifică relația atunci graful nu are drumuri hamiltoniene și algoritmul se oprește, altfel se trece la pasul 6.

Se ordonează nodurile în ordinea descrescătoare a puterilor lor de atingere și obținem drumul hamiltonian căutat.

C. Algoritmul lui Kaufmann

Construim matricea latină L asociată grafului, unde:

lij =

Construim matricea , definită prin:

=

numită matricea latină redusă.

Se calculează succesiv matricile:

L2 = L, L3 = L2, …, Lk+1 = Lk, …

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 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ă se doresc și circuitele atunci se verifică pentru fiecare drum hamiltonian dacă poate fi completat până la un circuit (adică dacă există în graf arcul care unește nodul final cu cel inițial);

Dacă se dorește și drumul (sau circuitul) de valoare optimă (maximă sau minimă) se calculează suma valorilor pentru fiecare drum și/sau circuit și se alege cel cu valoarea optimă.

În concluzie, metoda înmulțirii latine (A. Kaufmann – J. Melgrange) determină toate drumurile elementare din graf, prin calcularea matricelor M(1), M(2), M(3), …, M(n-1).

În matricea M(n-1) se citesc drumurile hamiltoniene.

Această metodă a înmulțirii latine (algoritmul lui Kaufmann) este utilă, mai ales, în cazul grafurilor tare conexe, unde algoritmul lui Foulkes nu este eficient. Totuși, metoda este greu de aplicat în grafuri cu un număr mare de noduri. În acest caz este preferabil să se construiască graful condensat, să se determine drumurile hamiltoniene în fiecare în parte cu algoritmul lui Kaufmann și apoi, ca la algoritmul lui Foulkes, să se caute drumurile hamiltoniene în graful inițial.

D. Un algoritm bazat pe algoritmul ungar

Fie G = (X,U) un graf orientat cu n noduri X = {x1, x2, … , xn}.

Se construiește graful bipartit H = (AB,V) în care A = B = X și V = U (adică am folosit pentru G reprezentarea prin corespondență).

Se găsește pentru graful H cuplajul maxim de valoare minimă.

Se construiește graful parțial al lui G format doar cu arcele cuplajului găsit. Este ușor de demonstrat că, componentele tare conexe ale acestuia sunt toate niște circuite. Dacă s-a format un singur circuit acesta este circuitul hamiltonian de valoare minimă. Dacă s-au format mai multe se trece la pasul 4.

Pentru fiecare arc aflat pe circuitul de lungime minimă (dacă sunt mai multe se iau în considerare arcele tuturor) se reia algoritmul de la pasul 1 pentru graful parțial rezultat din G prin eliminarea acestui arc.

Pentru fiecare graf parțial se continuă procedeul până se ajunge la unul din cazurile:

Cuplajului maxim găsit îi corespunde un singur circuit. Dacă acest circuit este primul obținut atunci valoarea sa i se atribuie unei variabile Z și circuitul este păstrat. Dacă nu este primul atunci valoarea sa se compară cu Z și, dacă este mai mică, ea devine noua valoare a lui Z și circuitul se păstrează, eliminându-l pe cel corespunzător fostei valori a lui Z. În caz contrar se trece la alt graf parțial neanalizat încă.

Cuplajul maxim are o valoare mai mare decât Z. Pentru acest graf parțial se abandonează ramificarea.

Se continuă analiza grafurilor parțiale până sunt analizate toate ramificațiile. Valoarea Z finală este valoarea circuitului de valoare minimă iar circuitul corespunzător este cel optim.

Analiza de mai sus poate fi schematizată printr-un arbore de tipul:

în care fiecare nod este un graf parțial de analizat, iar pentru fiecare arc, nodul inferior este un graf parțial care provine din graful corespunzător nodului superior, prin suprimarea unui arc de pe circuitele de lungime minimă corespunzătoare cuplajului maxim de valoare minimă al acestuia.

Observație: Algoritmul asigură găsirea circuitului de valoare minimă iar în cazul în care algoritmul lui Foulkes nu funcționează este o alternativă mai bună decât algoritmul lui Kaufmann. Totuși el nu lucrează în timp polinomial și în unele cazuri (de exemplu cazuri în care se formează foarte multe cicluri cu lungime minimă) necesită un număr imens de calcule.

În aceste cazuri se pot folosi metode euristice prin care se elimină din start o serie de arce, considerate a avea valori prea mari pentru a se putea afla pe circuitul hamiltonian de valoare minimă, apoi se aplică în graful parțial rămas unul din algoritmii de mai sus.