Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim

“Diferența dintre școală și viață?

În școală, înveți o lecție, apoi dai un test.

În viață, ai de dat un test care te învață o lecție.”

(Tom Bodett)

CUVÂNT ÎNAINTE

Scopul acestei lucrări este cercetarea și programarea algoritmilor pseudopolinomiali referitoare la problemele de flux de cost minim. Aceste probleme sunt unele din problemele bazice combinatorice de optimizare, care au o implementare largă pentru multe probleme practice. Modelele de fluxuri optime se aplică la cercetarea şi soluţionarea problemelor din economie, tehnică, biologie, medicină şi altele.

Primul capitol, intitulat Noțiuni introductive, conține noțiuni generale referitoare la grafuri sub formă de definiții și exemple. În programarea algoritmilor pseudopolinomiali pentru fluxuri de cost minim s-a folosit reprezentarea fluxurilor sub formă matricială: matricea de adiacență, matricea costurilor, matricea fluxurilor, datele fiind citite dintr-un fișier text.

Capitolul II – Parcurgeri de grafuri, prezintă două metode de “vizitare” a nodurilor grafurilor orientate, cea folosită în rezolvarea algoritmilor vizați fiind metoda de parcurgere în lățime (BF).

Capitolul III – Distanțe și drumuri minime detaliază problemele de drum minim, referindu-se în principal la Algoritmul Dijkstra, deoarece acest algoritm s-a inclus în implementarea algoritmilor pentru fluxuri de cost minim.

Capitolul IV, intitulat Fluxuri de cost minim, reprezintă capitolul principal al lucrării, deoarece conține algoritmii pseudopolinomiali cercetați din cadrul problemelor de flux de cost minim.

Ultimul capitol conține, în cazul fiecărui algoritm implementat, fișierul sursă al algoritmului, un exemplu de fișier de intrare, precum și rezultatul execuției softului.

Implementarea algoritmilor pseudopolinomiali pentru problemele de flux de cost minim, în limbajul de programare Java a fost o adevărată lecție de viață, o provocare, datorită faptului că, pornind de la zero (la începutul anului universitar), am ajuns să programez corect algoritmii propuși. După zeci și zeci de rulări, ciclări infinite, rezultate eronate afișate, calcule și fluxuri desenate pe hârtie, metode refăcute de câteva ori, s-au “născut” și algoritmii corecți. Implementările sunt structurate pe metode bine puse la punct, gândite și formulate simplu și clar.

Am convingerea că acești primi pași în limbajul Java vor continua pentru implementarea altor algoritmilor, mai ales datorită vocației mele de dascăl.

CAPITOLUL I

NOȚIUNI INTRODUCTIVE

1.1. VOCABULARUL DE BAZĂ ÎN TEORIA GRAFURILOR

Definiția 1.1. Se numește graf orientat un triplet G=(N,A,g) format dintr-o mulțime de N elemente numite noduri sau vârfuri, dintr-o familie A de elemente numite arce și dintr-o aplicație numită funcție de incidență, prin care fiecărui element din a i se asociază o pereche ordonată (x,y) cu x y; dacă eliminăm condiția x y atunci arcul de forma (x,x) se numește buclă, iar G se numește graf general orientat.

În continuare vom presupune că graful orientat G este finit, adică mulțimea nodurilor N={ , x, } este finită și familia arcelor A={ , a, } este un șir finit. Cardinalul mulțimii N notat |N|=n, se numește ordinul grafului orientat G.

Un graf orientat G=(N,A,g) se reprezintă grafic în modul următor:

 Fiecare nod x se reprezintă printr-un punc sau cerculeț în plac;

 Fiecare arc a , a=(x,y) se reprezintă printr-o linie care unește cele două noduri și pe care se află o săgeată cu sensul de la x la y.

Exemplul 1.1. Graful din figura 1.1. este de ordinul 8.

Definiția 1.2. Două grafuri orientate G1=(N1,A1,g1) și G2=(N2,A2,g2) se numesc izomorfe, dacă există o bijecție cu proprietatea că aplicația , definită prin , este o bijecție.

Definiția 1.3. Dacă oricare pereche ordonată (x,y) este imaginea a cel mult q, q>1, elemente din A, atunci G=(N,A,g) se numește multigraf orientat. În paragrafele următoare ne vom ocupa de grafuri orientate cu q=1. În acest caz funcția g este injectivă și familia A este o mulțime. Un astfel de graf se numește digraf și se notează G=(N,A).

Definiția 1.4. Se numește graf neotientat un triplet G=(N,A,g) format dintr-o mulțime N de elemente numite noduri sau vârfuri, dintr-o familie A de elemente numite muchii și dintr-aplicație numită funcție de incidență, prin care fiecărui element a i se asociază o pereche ; dacă considerăm , unde aplicație , atunci aplicația g asociază fiecărui element a , fie o pereche de noduri care se notează sau , fie un nod care se notează și se numește buclă, iar G se numește graf general neorientat.

În continuare presupunem că graful neorientat G este finit, adică mulțimea nodurilor N este finită și familia muchiilor A este un șir finit.

Un graf neorientat G=(N, A, g) se reprezintă grafic la fel ca în cazul grafurilor orientate cu deosebirea că o muchie se reprezintă printr-o linie care unește cele două noduri fără săgeata care precizează sensul în cazul arcului. De asemenea, la fel ca în cazul grafurilor orientate se definește izomorfismul a două grafuri neorientate.