Drumuri Optime într-un Graf

Î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(x¬i,xj) sau cu vij, drum minim l(dm) = min (d(x¬1,xn)) , oricare d U si drum maxim l(dM) = maz (d(x¬1,xn)) oricare d U În aceste condiţii putem enunţa problema drumului optim astfel:

"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 n×n!× ). 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. 1. Dacă în graf nu există decât arce de valoare negativă atunci există drum de valoare maximă.

Obs. 1. Dacă în graf nu există circuite atunci există şi drum de valoare minimă ş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: ( un drum în care nodul iniţial şi cel final coincid este un circuit )

Pasul 1. Se construieşte mulţimea A formată din nodurile pentru care toate arcele incidente sunt incidente spre interior ( noduri în care toate arcele "intră" sau, altfel spus, noduri din care nu "pleacă" nici un arc).

Pasul 2. 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 în A). Dacă nu există nici un astfel de arc se trece la pasul 4.

Pasul 3. 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.

Pasul 4. 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.

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 cinci categorii:

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

2. Algoritmi prin ajustări succesive: (Ford);

3. Algoritmi prin inducţie (Dantzig);

4. Algoritmi prin ordonare prealabilă a vârfurilor grafului;

5. Algoritmi prin extindere selectivă (Dijkstra).

A. Algoritmul lui Bellman – Kalaba (formulare teoretică şi algoritm de rezolvare)

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