Concepte de baza in teoria grafurilor

semigraf interior al unui nod x_k: este multimea arcelor = care sunt incidente spre interior nodului x_k;

semigraf exterior al unui nod x_k: este multimea arcelor = care sunt incidente spre exterior nodului x_k;

semigradul interior al unui nod x_k: este numarul arcelor care sunt incidente spre interior nodului x_k = cardinalul lui si se noteaza cu ;

semigradul exterior al unui nod x_k: este numarul arcelor care sunt incidente spre exterior nodului x_k = cardinalul lui si se noteaza cu ;

gradul unui nod x_k: este suma semigradelor nodului x_k: = + ;

nod izolat: este un nod cu gradul 0;

nod suspendat: este un nod cu gradul 1;

arce adiacente: arce care au o extremitate comuna;

drum intr-un graf: o multime ordonata de noduri ale grafului: (x₁, x₂, , x_k), cu proprietatea ca exista in graf toate arcele de forma (x_i,x_i+1) i = 1,,k-1;

lungimea unui drum: este numarul arcelor care il formeaza;

drum elementar: un drum in care fiecare nod apare o singura data;

drum simplu: un drum in care fiecare arc apare o singura data;

putere de atingere a unui nod x_i I X in graful G: numarul de noduri la care se poate ajunge din x_i. Puterea de atingere se noteaza cu p(x_i), 1 i n si evident p(x_i) .

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

drum eulerian: un drum simplu care contine toate arcele grafului;

lant: un drum in care arcele nu au neaparat acelasi sens de parcurgere;

circuit: un drum in care nodul initial coincide cu cel final;

circuit elementar: un drum in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;

circuit simplu: un drum in care fiecare arc apare o singura data;

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

ciclu: este un circuit in care arcele nu au neaparat acelasi sens de parcurgere;

ciclu elementar: un ciclu in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;

ciclu simplu: un ciclu in care fiecare arc apare o singura data;

Observatie: Intr-un graf neorientat notiunile de drum si lant sunt echivalente si de asemenea cele de circuit si ciclu.

graf partial al unui graf G = (X,U): este un graf G'(X,U') cu U' U;

subgraf al unui graf G = (X,G): este un graf G'(X',G') unde X' X si G'(x_i) = G(x_i) X' pentru orice x_i I X';

graf redus al unui graf G = (X,U): este un graf G^*(X^*,U^*) unde X^* este formata din multimile unei partitii de multimi nevide ale lui X, iar (,) exista doar daca i j si exista cel putin un arc in U, de la un nod din la un nod din .

graf tare conex: este un graf in care intre oricare doua noduri exista cel putin un drum;

graf simplu conex: este un graf in care intre oricare doua noduri exista cel putin un lant;

Observatie: Pentru grafuri neorientat notiunile de tare conex si simplu conex sunt echivalente, graful numindu-se doar conex;

componenta tare conexa a unui graf G = (X,U): este un subgraf al lui G care este tare conex si nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, intre oricare doua noduri din componenta exista cel putin un drum si nu mai exista nici un nod in afara componentei legat printr-un drum de un nod al componentei).

Gasirea drumurilor intr-un graf orientat

Daca privim graful ca imagine a unui sistem, nodurile reprezentand componentele sistemului, atunci o interpretare imediata a unui arc (x_i,x_j) este urmatoarea: componenta x_i influenteaza direct componenta x_j.

Daca nodurile au semnificatia de stari posibile ale unui sistem atunci un arc (x_i,x_j) semnifica faptul ca sistemul poate trece direct din starea x_i in starea x_j.

In ambele cazuri se vede ca avem de-a face doar cu informatii despre legaturi directe; totusi, chiar daca o componenta x_i nu influenteaza direct componenta x_j ea o poate influenta prin intermediul altor componente, existand un sir de componente intermediare: x₁ x₂ ,, x_k, fiecare influentand-o direct pe urmatoarea si x_i direct pe x₁ iar x_k direct pe x_j.

Astfel, daca dintr-o stare x_i nu se poate trece direct intr-o stare x_j s-ar putea totusi in mai multe etape, prin alte stari intermediare. Deoarece gasirea acestor influente sau treceri posibile este de obicei foarte importanta iar pentru un sistem cu mii sau zeci de mii de componente acest lucru nu mai poate fi facut 'din ochi', este necesara formalizarea notiunii de 'influente' si 'treceri' posibile, nu neaparat directe. Acest lucru a si fost facut mai sus, deoarece este evident ca 'x_i influenteaza x_j' sau 'din starea x_i se poate trece in starea x_j' este echivalent cu existenta in graf a unui drum de la nodul x_i la nodul x_j.

In continuare vom da un algoritm prin care putem gasi toate drumurile dintr-un graf orientat cu un numar finit de noduri.

Pasul 1.    Se construieste matricea booleana a adiacentelor directe corespunzatoare grafului, notata cu A. In aceasta se afla, evident, toate drumurile de lungime 1.

Este interesant de vazut ce legatura exista intre aceasta matrice si drumurile de lungime 2. Fie doua noduri x_i si x_j oarecare din graf. Existenta unui drum de lungime 2 intre ele presupune existenta unui nod x_k, din graf, cu proprietatea ca exista atat arcul (x_i,x_k) cat si arcul (x_i,x_k). Pentru a vedea daca acesta exista, luam pe rand fiecare nod al grafului si verificam daca exista sau nu ambele arce ((x_i,x_k) si (x_i,x_k)). Aceasta este echivalent cu a verifica daca, in matricea booleana a adiacentelor directe, exista vreun indice k astfel incat elementul k al liniei i si elementul k al coloanei j sa fie ambele egale cu 1. Daca folosim operatiile algebrei booleene de adunare si inmultire:

atunci verificarile de mai sus sunt echivalente cu a verifica daca elementul de pe pozitia (i,j) din A² este egal cu 1. Valoarea 1 spune doar ca exista cel putin un drum de lungime 2 de la x_i la x_j. Daca dorim sa vedem si cate sunt, vom folosi regulile de inmultire si adunare obisnuita.

De asemenea, se poate observa ca existenta unui drum de lungime 3 de la x_i la x_j presupune existenta unui nod x_k astfel incat sa existe un drum de lungime 2 de la x_i la x_k si un arc de la x_k la x_j, care este echivalent cu a verifica daca exista vreun indice k astfel incat elementul k al liniei i din matricea A² si elementul k al coloanei j din A sunt ambele egale cu 1 sau, mai simplu, daca elementul (i,j) din A³ este 1.

Din cele de mai sus se observa ca existenta drumurilor de lungime k este data de valorile matricei A^k, daca s-au folosit regulile algebrei booleene si numarul lor este dat de A^k, daca s-au folosit regulile obisnuite.

Pasul 2.    Vom calcula succesiv puterile lui A pana la puterea A^n-1

Daca intre nodurile x_i si x_j exista un drum de lungime n atunci el va contine un numar de noduri mai mare sau egal nu n+1 si, cum in graf sunt doar n varfuri, este clar ca cel putin unul, sa zicem x_k, va aparea de doua ori. Vom avea in acest caz un drum de la x_i pana la prima aparitie a lui x_k, si un drum de la ultima aparitie a lui x_k la x_j. Eliminand toate nodurile dintre prima aparitie a lui x_k si ultima aparitie a sa vom obtine un drum de la x_i la x_j, in care x_k apare o singura data. Aplicand acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obtine un drum de la x_i la x_j, in care fiecare nod apare o singura data (deci un drum elementar), care are evident cel mult n-1 arce. In concluzie, daca exista vreun drum de la x_i la x_j atunci exista si un drum elementar si, deci, va exista o putere a lui A, intre A¹ si A^n-1, in care pozitia (i,j) este diferita de 0. Pentru deciderea existentei unui drum intre oricare doua noduri este suficienta, deci, calcularea doar a primelor n-1 puteri ale lui A.

Pasul 3.    Se calculeaza matricea D = A + A² + + A^n-1

Daca ne intereseaza doar existenta drumurilor dintre noduri, nu si numarul lor, vom folosi inmultirea si adunarea booleana si conform observatiei de mai sus:

d_ij =

In acest caz, observand ca:

A (A + I)^n-2 = A + A² + A³ + + A^n-1 = A + A² + A³ + + A^n-1 = D

rezulta ca e suficient sa calculam doar puterea n-2 a matricei A + I si apoi s-o inmultim cu A. Avantajul acestei metode, in ceea ce priveste economia de timp, este sustinut si de urmatoarea observatie: daca D contine toate perechile de arce intre care exista drum atunci:

D = (A + A² + + A^n-1) + Aⁿ + Aⁿ⁺¹ + + A^n+k = D oricare ar fi k 0 T

T A (A + I)^n-2+k = (A + A² + + A^n-1) + Aⁿ + Aⁿ⁺¹ + + A^n+k-1 = D = A (A + I)^n-2

A (A + I)^n-2+k = A (A + I)^n-2 oricare ar fi k

deci de la puterea k = n-2 toate matricile A^k sunt egale. Putem, deci, calcula direct orice putere a lui A+I mai mare sau egala cu n-1 (de exemplu calculand (A+I)², (A+I)⁴, (A+I)⁸, , , r fiind prima putere a lui 2 pentru care 2^r n-2).

Procedeul de mai sus nu asigura decat aflarea faptului daca exista sau nu drum intre doua noduri, eventual ce lungime are si cate sunt de aceasta lungime. Totusi, in problemele practice cel mai important este sa stim care sunt efectiv aceste drumuri. Deoarece toate drumurile pot fi descompuse in drumuri elementare si in problemele practice in general acestea sunt cele care intereseaza, pasii urmatori ai algoritmului vor fi dedicati gasirii lor.

Pentru gasirea acestora se foloseste reprezentarea grafului prin matricea latina de la cazul F.

Pasul 4.    Construim matricea latina L asociata grafului, unde:

l_ij =

si matricea , definita prin:

=

numita matricea latina redusa.

Gasirea unui drum de lungime 2 de la x_i la x_j presupune gasirea unui nod cu proprietatea ca exista arcele (x_i,x_k) si (x_k,x_j) si memorarea vectorului (x_i, x_k, x_j). Aceasta este echivalent cu a gasi un indice k astfel incat elementul de pe pozitia k a liniei i, din matricea L, sa fie x_i,x_k si elementul de pe pozitia k al coloanei j, din matricea , sa fie x_j. Vom inmulti deci matricea L cu matricea , folosind insa niste reguli de calcul speciale, numite inmultire si adunare latina.

Definitia 1: Se numeste alfabet o multime de semne numite simboluri sau litere unde I este o multime oarecare de indici, finita sau nu.

Definitia 2: Se numeste cuvant un sir finit de simboluri notat .

Definitia 3: Se numeste inmultire latina o operatie definita pe multimea cuvintelor unui alfabet, notata '', astfel:

=

(produsul a doua cuvinte se obtine prin concatenarea lor)

Inmultirea latina este asociativa, are ca element neutru cuvantul vid, nu e comutativa si un element este inversabil doar daca este cuvantul vid.

Definitia 3: Se numeste adunare latina o functie definita pe multimea cuvintelor unui alfabet cu valori in multimea partilor multimi cuvintelor, notata '' astfel:

=

(suma a doua cuvinte este multimea formata din cele doua cuvinte)

Pasul 5.    Se calculeaza succesiv matricile:

L² = L , L³ = L² , ,L^k+1 = L^k

folosind operatiile de inmultire si adunare latina, alfabetul fiind multimea nodurilor grafului, unde operatia de inmultire este usor modificata, produsul dintre doua elemente ale matricilor fiind 0, daca unul dintre ele este 0 sau au un nod comun si este produsul latin al lor, in caz contrar.

Din felul cum a fost construita, matricea L^k va contine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (cate are graful cu totul) rezulta ca:

primele n-1 puteri ale lui L contin toate drumurile elementare din graf;

puterile lui L mai mari sau egale cu n au toate elementele egale cu 0;

matricea L^n-1 contine toate drumurile hamiltoniene din graf (daca exista).

Observatie: Deoarece obtinerea matricii D prin metoda de mai sus presupune un volum foarte mare de calcule (de exemplu, daca graful are 100 de noduri, ridicarea unei matrici de 100100 la puterea 100) pentru obtinerea acesteia se poate aplica si urmatorul algoritm:

Pas 1. Se construieste matricea de adiacenta A;

Pas 2. Pentru fiecare linie i se aduna boolean la aceasta toate liniile j pentru care a_ij = 1.

Pas 3. Se reia pasul 2 pana cand, dupa o aplicare a acestuia, matricea ramane aceeasi (nu mai apare nici un 1)

Ultima matrice obtinuta este matricea drumurilor D numita si matricea conexiunilor totale.

Aceasta metoda, desi mai simpla nu spune insa si care sunt aceste drumuri, pentru gasirea lor aplicandu-se, de exemplu, inmultirea latina

Drumuri si circuite hamiltoniene

Una dintre cele mai cunoscute probleme economice este problema comis voiajorului. Comis voiajorul este un individ care trebuie sa prezinte s-au sa distribuie marfa comandata la o serie de centre distribuite in general neliniar pe o anumita zona teritoriala (localitatile dintr-un judet, magazinele dintr-un cartier, persoanele dintr-un sat etc). Daca numarul de obiective care trebuie vizitate este mare sau foarte mare iar timpul disponibil foarte limitat atunci devine vitala o asemenea organizare a trecerii pe la fiecare obiectiv incat sa se efectueze in timpul minim posibil. Acest timp minim se traduce prin drumul cel mai scurt, iar cel mai scurt drum este evident cel in care se trece pe la fiecare obiectiv o singura data. In plus, la sfarsit trebuie sa se afle in punctul initial, adica sediul firmei la care lucreaza.

O reprezentare a regiunii aprovizionate, in care centrele pe la care se trece sunt vizualizate prin puncte iar caile de acces la acestea prin segmente de curbe, va fi evident un graf, problema reducandu-se la a gasi circuitul hamiltonian de lungime minima.

In timp, s-au evidentiat o multitudine de probleme reductibile la gasirea unui drum (sau circuit) hamiltonian intr-un graf, cum ar fi:

Problema postasului (gasirea traseului cel mai scurt care trece pe la toate locuintele ce apartin de oficiul postal la care lucreaza acesta);

Problema adunarii deseurilor (cel mai scurt drum care trece pe la toate punctele de depozitate a deseurilor);

Problema succesiunii operatiilor (executarea mai multor operatii pe o masina in acea ordine in care suma timpilor consumati cu pregatirea masinii pentru trecerea de la o operatie la urmatoarea sa fie minim)

Ordinea lipirii unor componente electronice pe o placa, etc;

Determinarea drumurilor hamiltoniene

Problema determinarii drumului (circuitului) hamiltonian de valoare optima s-a dovedit deosebit de dificila, neexistand nici acum un algoritm care sa rezolve problema in timp polinomial si nici macar o metoda simpla prin care sa se decida daca intr-un graf dat exista sau nu drumuri hamiltoniene.

Exista insa mai multi algoritmi, care reusesc, intr-un caz sau altul, sa rezolve problema satisfacator si in timp util.

A.   Algoritmul lui Foulkes

Pasul 1.    Se scrie matricea booleana A asociata grafului G.

Pasul 2.    Se determina matricea D a drumurilor grafului G prin procedeul expus la inceputul capitolului si apoi matricea M = I + D.

Pasul 3.    Se imparte multimea nodurilor grafului in submultimi disjuncte astfel:

Se considera in matricea M liniile pline (cu toate elementele 1). Nodurile ce corespund liniilor pline cu 1 formeaza submultimea C₁.

Se elimina liniile si coloanele care corespund nodurilor din submultimea stabilita.

Se reia rationamentul de la punctul 1 pe matricea redusa obtinuta la punctul 2 obtinandu-se urmatoarea submultime si in continuare toate celelalte pana se epuizeaza toate liniile matricei.

Pasul 4.    Se construieste graful G' in care:

Nodurile care formeaza o submultime sunt reprezentate prin puncte in interiorul unui dreptunghi si intre acestea se traseaza arcele existente in graful initial G.

Se traseaza legaturile dintre submultimi. Ele sunt reprezentate prin arcele existente in graful initial G intre nodurile submultimii C₁ si cele ale submultimii C₂, intre nodurile submultimii C₂ si cele ale submultimii C₃ etc.

Pasul 5.    Se gasesc drumurile hamiltoniene

Un drum hamiltonian se gaseste plecand de la un varf din submultimea C₁, trecand prin toate varfurile acesteia cu un drum hamiltonian, din ultimul varf la care se ajunge in C₁ trecand la un varf din C₂, parcurgand in continuare un drum hamiltonian in a doua submultime si tot asa, trecand prin toate submultimile si parcurgand, deci, toate nodurile grafului initial, o singura data. Aplicand acest procedeu in toate modurile posibile se obtin toate drumurile hamiltoniene din graful initial G. (Observatie: poate sa nu existe nici un drum hamiltonian in graful G, caz in care algoritmul se opreste deoarece la un anumit pas nu mai exista nici o linie plina cu 1).

Observatie. Algoritmul lui Foulkes reduce gasirea drumurilor hamiltoniene in graful initial G (care in problemele practice este foarte mare) la gasirea mai multor drumuri hamiltoniene mai mici in componente tare conexe ale grafului. Daca un graf are o singura componenta tare conexa, algoritmul lui Foulkes nu este eficient, in acest caz trebuind aplicati alti algoritmi cum ar fi cel bazat pe inmultirea latina.

B. Algoritmul lui Chen pentru determinarea drumurilor hamiltoniene in grafuri fara circuite-tema referat

C. Algoritmul lui Kaufmann

Pasul 1.    Construim matricea latina L asociata grafului, unde:

l_ij =

Pasul 2.    Construim matricea , definita prin:

=

numita matricea latina redusa.

Pasul 3.    Se calculeaza succesiv matricile:

L² = L, L³ = L², , L^k+1 = L^k,

folosind operatiile de inmultire si adunare latina, alfabetul fiind multimea nodurilor grafului, unde operatia de inmultire este usor modificata, produsul dintre doua elemente ale matricilor fiind 0, daca unul dintre ele este 0 sau au un nod comun, si este produsul latin al lor, in caz contrar.

Din felul cum a fost construita, matricea L^k va contine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (cate are graful cu totul) rezulta ca:

primele n-1 puteri ale L contin toate drumurile elementare din graf;

puterile lui L mai mari sau egale cu n au toate elementele egale cu 0;

matricea L^n-1 contine toate drumurile hamiltoniene din graf.

Pasul 4.    Daca se doresc si circuitele atunci se verifica pentru fiecare drum hamiltonian daca poate fi completat pana la un circuit (adica daca exista in graf arcul care uneste nodul final cu cel initial);

Pasul 5.    Daca se doreste si drumul (sau circuitul) de valoare optima (maxima sau minima) se calculeaza suma valorilor pentru fiecare drum si/sau circuit si se alege cel cu valoarea optima.

In concluzie, metoda inmultirii latine (A. Kaufmann - J. Melgrange) determina toate drumurile elementare din graf, prin calcularea matricelor M⁽¹⁾, M⁽²⁾, M⁽³⁾, ., M^(n-1).

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

Aceasta metoda a inmultirii latine (algoritmul lui Kaufmann) este utila, mai ales, in cazul grafurilor tare conexe, unde algoritmul lui Foulkes nu este eficient. Totusi, metoda este greu de aplicat in grafuri cu un numar mare de noduri. In acest caz este preferabil sa se construiasca graful condensat, sa se determine drumurile hamiltoniene in fiecare in parte cu algoritmul lui Kaufmann si apoi, ca la algoritmul lui Foulkes, sa se caute drumurile hamiltoniene in graful initial.

D. Un algoritm bazat pe algoritmul ungar-tema referat

6. Drumuri optime intr-un graf

In marea majoritate a problemelor care pot fi modelate prin grafuri nu ne intereseaza numai daca exista sau nu legaturi intre componentele reprezentate prin nodurile grafului ci si intensitatea acestora. Aceasta intensitate are semnificatia unei valori numerice (pozitive sau negative) asociate arcului corespunzator legaturii a carei intensitate o masoara.

In aplicatiile economice aceasta valoare poate fi:

lungimea drumului dintre doua localitati;

costul parcurgerii rutei reprezentate prin arcul corespunzator;

durata parcurgerii rutei respective;

cantitatea transportata pe ruta respectiva;

capacitatea maxima a rutei respective;

castigul 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 aparea in aceste situatii este gasirea, pentru o anumita pereche de noduri (sau mai multe perechi), a drumului optim intre acestea.

Pentru formalizarea problemei vom introduce notiunea de valoare a unui drum, care este egala cu suma valorilor arcelor care il compun. Vom nota in continuare valoarea unui arc (x_i,x_j) cu v(x_i,x_j) sau cu v_ij. In aceste conditii putem enunta problema drumului optim astfel:

'Dat un graf G = (X,U) si o functie care asociaza fiecarui arc o valoare reala, sa se gaseasca, pentru o pereche data de noduri, drumul (drumurile) de valoare optima (minima sau/si maxima) intre cele doua noduri si valoarea acestuia (acestora)'

Deoarece este vorba de gasirea minimului unei multimi de numere reale, prima intrebare care se pune este daca aceasta admite minim. Daca multimea nodurilor grafului este infinita atunci pot exista o infinitate de drumuri elementare distincte intre cele doua noduri si multimea valorilor acestora poate avea orice forma (inchisa sau nu, marginita sau nu) devenind foarte greu de caracterizat cazurile cand minimul dorit exista. Deoarece totusi majoritatea covarsitoare a problemelor economice se modeleaza prin grafuri cu numar finit de noduri, ne vom limita in continuare doar la acestea.

Un numar finit de noduri n atrage dupa sine existenta unui numar finit de arce (cel mult n²) si a unui numar finit de drumuri elementare ( cel mult n n! ). Deoarece oricarui drum d ii corespunde un drum elementar d_e (obtinut prin eliminarea tuturor subcircuitelor lui d) putem calcula valoarea oricarui drum ca suma intre valoarea drumului elementar corespunzator si valorile unor subcircuite ale sale, fiecare inmultita cu numarul de parcurgeri ale circuitului respectiv.

In concluzie, daca exista un circuit de valoare negativa inseamna ca exista drumuri de valoare oricat de mica (cele care contin acest circuit), obtinuta prin parcurgerea acestuia de oricate ori dorim) si, deci, multimea valorilor drumurilor este nemarginita inferior, neexistand drum de valoare minima. Daca exista un circuit de valoare pozitiva atunci exista drumuri de valoare oricat de mare si multimea valorilor drumurilor este nemarginita superior, neexistand drum de valoare maxima.

Daca nu exista circuite de valoare negativa atunci valoarea oricarui drum este mai mare sau egala cu a drumului elementar corespunzator, deci drumul de valoare minima (daca exista) va fi un drum elementar. Cum multimea drumurilor elementare este finita (si deci si multimea valorilor lor) va avea minorant si am lamurit problema compatibilitatii problemei. Analog, daca nu exista circuite de valoare pozitiva atunci valoarea oricarui drum este mai mica sau egala cu a drumului elementar corespunzator, deci drumul de valoare maxima (daca exista) va fi un drum elementar. Cum multimea drumurilor elementare este finita (si deci si multimea valorilor lor), va avea majorant.

Obs. 1. Daca in graf nu exista decat arce de valoare pozitiva atunci exista drum de valoare minima.

Obs. 1. Daca in graf nu exista decat arce de valoare negativa atunci exista drum de valoare maxima.

Obs. 1. Daca in graf nu exista circuite atunci exista si drum de valoare minima si drum de valoare maxima.

Deoarece din cele de mai sus se sesizeaza importanta existentei circuitelor intr-un graf vom da in continuare un algoritm de depistare a existentei circuitelor intr-un graf:

Pasul 1.    Se construieste multimea A formata din nodurile pentru care toate arcele incidente sunt incidente spre interior ( noduri in care toate arcele 'intra' sau, altfel spus, noduri din care nu 'pleaca' nici un arc).

Pasul 2.    Se gasesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealalta extremitate in A (noduri din care se poate 'ajunge' doar in A). Daca nu exista nici un astfel de arc se trece la pasul 4.

Pasul 3.    Se adauga arcele gasite la pasul 2 la multimea A apoi se reia algoritmul de la pasul 2, pentru noua multime A.

Pasul 4.    Daca A contine multimea tuturor nodurilor atunci graful nu contine circuite. Daca au ramas noduri in afara lui A atunci graful contine circuite.

Algoritmi de gasire a drumului optim

Din cauza varietatii nelimitate a grafurilor posibile, nu exista un algoritm care sa rezolve orice problema in timp util, dar s-au elaborat o multime de algoritmi, fiecare fiind cel mai eficace in anumite cazuri. Acesti algoritmi pot fi grupati in cinci categorii:

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

Algoritmi prin ajustari succesive: (Ford);

Algoritmi prin inductie (Dantzig);

Algoritmi prin ordonare prealabila a varfurilor grafului;

Algoritmi prin extindere selectiva (Dijkstra).

1. Algoritmul lui Bellman - Kalaba

Algoritmul se aplica in grafuri finite care nu au circuite de valoare negativa (pentru o problema de minim) sau care nu au circuite de valoare pozitiva (intr-o problema de maxim) si gaseste drumurile de valoare minima (maxima) de la toate nodurile grafului la un nod oarecare, fixat. Daca dorim sa cunoastem drumurile de valoare minima (maxima) intre oricare doua noduri vom aplica algoritmul, pe rand, pentru fiecare nod al grafului.

Fie G = un graf orientat finit. Presupunem (fara a restrange generalitatea, ca am numerotat nodurile astfel incat nodul spre care cautam drumurile de valoare minima (maxima) de la celelalte noduri sa fie x_n.

Pasul 1.    Se construieste matricea patratica M cu dimensiunea egala cu numarul de noduri ale grafului ale carei elemente sunt:

m_ij =

Pasul 2.    Se adauga succesiv liniile L_i la matricea M, elementele acestora calculandu-se prin relatiile de recurenta:

L_1j = m_jn j = 1,,n (prima linie este ultima coloana, transpusa, a matricii M)

L_ij = min (L_i-1,j , (m_jk + L_i-1,k)) intr-o problema de minim

sau L_ij = max (L_i-1,j , (m_jk + L_i-1,k)) intr-o problema de maxim

Pasul 3.    Dupa calcularea fiecarei linii noi se compara elementele ei cu cele ale precedentei:

Daca L_ij = L_i-1,j pentru orice j = 1,,n atunci se opreste recurenta si ultima linie calculata contine valorile minime ale drumurilor de la celelalte noduri la nodul x_n.

Daca exista cel putin un indice j cu L_ij L_i-1,j se trece la calcularea noii linii L_i+1

Pasul 4.    Pentru gasirea drumului care da valoarea minima de la un nod x_j la nodul x_n se gasesc, incepand inapoi de la ultima linie, pe care s-au obtinut valorile finale, notata L_f, nodurile ,, , care formeaza drumul cautat, unde = x_j, = x_n si fiecare alt indice k_i+1 este cel pentru care s-a obtinut minimul(maximul) de pe pozitia k_i al liniei L_i.

Observatie: Pentru grafuri foarte mari, algoritmul necesita un volum mare de memorie, prin necesitatea memorarii matricei M, care este greu de manipulat. Chiar daca din cele n² arce posibile graful ar avea doar un procent foarte mic matricea grafului va avea tot n² pozitii de memorat si analizat.

Exemplu: Presupunem dat graful orientat de mai jos, in care se doreste gasirea drumului de valoare minima de la nodul x₁ la nodul x₉.

Matricea M va fi

iar dupa calcularea liniilor L_i obtinem:

Deoarece L₄ = L₅ oprim calcularea liniilor dupa calcularea liniei 5. In aceasta linie se afla valorile celor mai scurte de la toate nodurile la nodul x₉. Drumul dorit de noi (x₁ x₉) are valoarea data de prima pozitie a liniei 5, fiind egal cu 13.

Pentru a gasi acest drum, plecam inapoi de la linia 4 si avem:

DISTRIBUIE DOCUMENTUL

Vizualizari: 4064
Importanta:

Comenteaza documentul:

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved

Distribuie URL
https://www.scrigroup.com/calculatoare/ELEMENTE-DE-TEORIA-GRAFURILOR-92383.php

Adauga cod HTML in site
<a href="https://www.scrigroup.com/calculatoare/ELEMENTE-DE-TEORIA-GRAFURILOR-92383.php" target="_blank" title=" - https://www.scrigroup.com/calculatoare/ELEMENTE-DE-TEORIA-GRAFURILOR-92383.php">ELEMENTE DE TEORIA GRAFURILOR - Moduri de reprezentare ale unui graf</a>