Teoria grafurilor

Intr-o mare varietate de contexte se pune problema deplasarii unei cantitati Q ce poate fi materie, energie, informatie, etc. din unele locuri numite surse in alte locuri numite destinatii, aceasta deplasare realizandu-se pe anumite rute de legatura. Unitatile indivizibile ale cantitatii Q care se deplaseaza de-a lungul rutelor se vor numi unitati de flux.

O clasificare a problemelor de transport si distributie

Pentru Cercetarea Operationala, problema enuntata va prezenta interes numai daca respecta urmatoarele ipoteze:

a) cel putin o sursa poate aproviziona mai multe destinatii si cel putin o destinatie poate primi unitati de flux de la mai multe surse.

Rutele de legatura pot avea si alte puncte comune in afara surselor si destinatiilor, numite puncte intermediare sau de tranzit. Nu sunt excluse legaturile directe intre surse sau intre destinatii. In principiu, orice ruta poate fi parcursa in ambele sensuri, dar pot exista si rute cu sens unic.

Ansamblul surselor, destinatiilor, al punctelor intermediare si al rutelor de legatura se va numi retea de transport; el se identifica cu un graf neorientat sau partial orientat ca in figura 1.1.

b) Unele rute de legatura pot avea limitari superioare si / sau inferioare pentru volumul unitatilor de flux ce se deplaseaza intr-un sens sau altul. Aceste limitari poarta numele de capacitati (inferioare, respectiv superioare). In continuare, vom avea in vedere numai cazul in care toate capacitatile inferioare sunt egale cu zero, capacitatile superioare fiind exprimate prin numere pozitive.

c) Exista un cost al deplasarii unei unitati de flux de la un punct al retelei la altul, cost care poate fi exprimat in bani, timp sau distanta. Sunt situatii in care acest cost poate semnifica profitul obtinut de pe urma deplasarii. Pe aceeasi ruta, costurile si capacitatile pot fi diferite in functie de sensul de parcurgere al rutei.

Ipoteza a) va fi intotdeauna presupusa in timp ce ipotezele b) si c) pot fiinta separat sau simultan.

1) In prezenta ipotezei c) si absenta conditiei b) se pune problema deplasarii cantitatii de flux Q de la surse la destinatii la un cost total minim. Daca sursele sunt in legatura directa cu destinatiile obtinem problema clasica de transport, care va face obiectul Capitolului 4 al cursului. Cazul general, in care exisa si puncte intermediare, este cunoscut sub numele de problema transferului si el nu face obiectul cursului de fata. In cazul particular al unei singure surse s, al unei singure destinatii t si a unei singure unitati de flux se obtine problema drumului de cost minim de la s la t, problema de care ne vom ocupa in sectiunea 1.4 a acestui capitol.

2) In prezenta ipotezei b) si absenta ipotezei c) se pune problema daca reteaua, ale carei rute sunt capacitate, este capabila sa permita acoperirea integrala a cererilor in punctele de destinatie. Pentru aceasta, se va rezolva problema determinarii volumului maxim Q* de unitati de flux ce pot fi deplasate de la surse la destinatii. Daca Q* < Q vor exista destinatii a caror cerere este acoperita doar in parte si atunci se ridica problema maririi capacitatii de transfer a retelei. Am descris succint problema fluxului maxim, problema ce va fi abordata in cadrul cursului de Cercetari Operationale din anul 2.

3) In prezenta simultana a ipotezelor b) si c) se pune problema satisfacerii cererilor in punctele de destinatie la un cost de transport minim. Ca si in cazul precedent vom avea in vedere o problema modificata: vom determina mai intai cantitatea maxima de flux ce poate fi deplasata de la surse la destinatii si apoi modul de organizare al deplasarii astfel incat costul operatiei sa fie minim. Aceasta este problema fluxului (maxim) de cost minim, problema abordata, de asemenea, in cadrul cursului de Cercetari Operationale din anul 2.

In sectiunile urmatoare vom trata doua probleme de optimizare in retele de transport: problema determinarii unui arbore maximal (de acoperire) de valoare (cost) minim si problema drumului de cost minim de la s la t .

1.2 Concepte utilizate in teoria grafurilor

In sectiunea 1.1 am vizualizat elementele unei retele de transport printr-un desen compus din puncte si arce care unesc unele din aceste puncte (vezi figura 1.1). Un asemenea desen constituie forma uzuala de prezentare a unui concept deosebit de important, atat in sine cat si pentru studiul unei impresionante varietati de probleme din cele mai diverse domenii, domeniul economic fiind prioritar.

Am socotit deci necesar sa includem aici cateva elemente privitoare la conceptul de graf, caci despre el este vorba. Aceste elemente vor fi foarte utile pentru intelegerea consideratiilor teoretice dezvoltate in legatura cu rezolvarea problemei de transport si de asemenea constituie cadrul natural de abordare si a celorlalte probleme amintite in clasificarea data in sectiunea precedenta.

Un graf este un cuplu G = (V, E) format dintr-o multime nevida V, ale carei elemente se numesc varfuri sau noduri si o multime E de elemente, zise muchii, cu proprietatea ca fiecarei muchii e ? E ii sunt asociate doua noduri x, y ? V, nu neaparat distincte, numite extremitatile muchiei e. Un subgraf al grafului G = (V, E) este un graf G' = (V', E') in care V' ? V, E' ? E si orice muchie e? E' are aceleasi extremitati atat in G' cat si in G.

Dupa cum se vede, definitia generala nu exclude existenta muchiilor cu o singura extremitate (aceste muchii se numesc bucle), nici existenta mai multor muchii cu aceleasi extremitati (figura 1.2.a)

a) b)

Figura 1.2.

Graful G se va numi simplu daca nu are bucle si oricare doua noduri sunt extremitati pentru cel mult o muchie. Vom spune ca G este finit daca varfurile si muchiile sale sunt in numar finit.

In continuare, vom avea in vedere in exclusivitate grafuri finite si simple asa cum este cel reprezentat grafic in figura 1.2.b).

Fie e = ?x, y? o muchie a grafului G = (V, E); extremitatile sale pot fi ordonate in doua moduri: (x, y) si (y, x). Cele doua perechi se numesc rute orientate sau arce generate de muchia subiacenta e; spunem ca arcul (x, y) are extremitatea initiala x si extremitatea finala y si ca (y, x) este arcul opus lui (x, y). A orienta