Cuprins

Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.

Extras din document

Cuprins
CAPITOLUL I
CONCEPTUL DE GRAF FINIT.REPREZENTARE.EXEMPLE.
I.1. Conceptul de graf finit.Notiuni generale.
I.2. Concepte de baza in teoria grafurilor.
I.3. Reprezentarea grafurilor orientate.
CAPITOLUL II
ALGORITMI DE DETERMINARE A DISTANTELOR MINIME DINTRE ViRFURILE UNUI DIGRAF.
II.1.Notiuni generale.
II.2.Algoritmi de gasire a drumului optim.
CAPITOLUL III
ALGORITMI DE DETERMINARE A UNOR CIRCUITE NEGATIVE DINTR-UN DIGRAF.APLICATII.
III.1. Drumuri si circuite hamiltoniene.
III.2.Determinarea drumurilor hamiltoniene
A. Algoritmul lui Foulkes
B. Algoritmul lui Chen pentru determinarea drumurilor hamiltoniene in grafuri fara circuite
C. Algoritmul lui Kaufmann
D. Un algoritm bazat pe algoritmul ungar

Alte date

? Implementrea unor algoritmi de calcul a distantelor minime in grafuri finite?

CAPITOLUL I

CONCEPTUL DE GRAF FINIT.REPREZENTARE.EXEMPLE.

I.1. Conceptul de graf finit.Notiuni generale.

În general, pentru situatiile care necesita la rezolvare un oarecare efort mintal (si un caz tipic este cel al celor din economie), se cauta, in primul rand, o metoda de reprezentare a lor care sa permita receptarea intregii probleme dintr-o privire (pe cat posibil) si prin care sa se evidentieze cat mai clar toate aspectele acesteia.

În acest scop se folosesc imagini grafice gen diagrame, schite, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate in special pentru vizualizarea sistemelor si situatiilor complexe. În general, vom reprezenta componentele acestora prin puncte in plan iar relatiile (legaturile, dependentele, influentele etc) dintre componente prin arce de curba cu extremitatile in punctele corespunzatoare. Între doua puncte pot exista unul sau mai multe segmente (in functie de cate relatii dintre acestea, care ne intereseaza, exista) iar segmentelor li se pot asocia sau nu orientari (dupa cum se influenteaza cele doua componente intre ele), numere care sa exprime intensitatea relatiilor dintre componente etc.

Este evident, totusi, ca aceasta metoda are limite, atat din punct de vedere uman (prea multe puncte si segmente vor face desenul atat de complicat incat se va pierde chiar scopul pentru care a fost creat – claritatea si simplitatea reprezentarii, aceasta devenind neinteligibila) cat si din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

Din acest motiv, alaturi de expunerea naiv-intuitiva a ceea ce este un graf, data mai sus, se impune atat o definitie riguroasa cat si alte modalitati de reprezentare a acestora, adecvate in general rezolvarilor matematice.

Definitia I.1.1. Se numeste multigraf un triplet G = (X, A, f) in care X si A sunt doua multimi iar f este o functie, definita pe produsul cartezian al lui X cu el insusi (X2 = X×X), care ia valori in multimea partilor multimii A (notata P(A))

Multimea X se numeste multimea nodurilor multigrafului si elementele sale se numesc noduri (sau varfuri) ale multigrafului, iar A reprezinta multimea relatiilor (legaturilor) posibile intre doua noduri ale multigrafului.

Definitia I.1.2. Se numeste graf orientat un multigraf in care multimea A are un singur element: A = {a}.

Exemplul I.1.1. Fie graful urmator:

Fig. I.1.1.

Multimea nodurilor acestui graf este X={x1,x2,x3,x4}, iar multimea arcelor sale este U={[x1,x2], [x1,x4], [x2,x1], [x3,x2], [x3,x4]}.

În acest caz multimea partilor multimii A are doar doua elemente: multimea vida ? si intreaga multime A. Daca unei perechi orientate

(xi, xj) din X2 i se asociaza prin functia f multimea A atunci spunem ca exista arc de la nodul xi la nodul xj iar perechea (xi,xj) se va numi arcul (xi,xj).

Nodul xi se numeste nod initial sau extremitate initiala a arcului (xi,xj) iar nodul xj se numeste nod final sau extremitate finala a arcului (xi,xj). Arcul (xi,xj) este incident spre interior varfului xj si incident spre exterior varfului xi. Daca pentru un arc nodul initial coincide cu nodul final atunci acesta se numeste bucla. Nodurile xi si xj se vor numi adiacente daca exista cel putin unul din arcele (xi,xj) si (xj,xi).

Daca unei perechi orientate (xi, xj) din X2 i se asociaza prin functia f multimea vida ? atunci spunem ca nu exista arc de la nodul xi la nodul xj.

Este evident ca a cunoaste un graf orientat este echivalent cu a cunoaste varfurile si arcele sale. Din acest motiv putem defini un graf orientat prin perechea (X,U), unde X este multimea nodurilor sale iar U multimea arcelor sale.

De asemenea, putem cunoaste un graf orientat cunoscand multimea nodurilor si, pentru fiecare nod, multimea arcelor incidente spre exterior. Din acest motiv putem defini un graf orientat ca o pereche (X,?) unde X este perechea nodurilor iar ? este o functie definita pe X cu valori in multimea partilor lui X, valoarea acesteia intr-un nod xi, ?(xi) ? X fiind multimea nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea initiala.

Definitia I.1.3. Se numeste graf neorientat un multigraf in care multimea A are un singur element iar functia f are proprietatea:

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

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

Fig. I.1.2.

Se observa proprietatea de simetrie intre oricare 2 noduri ale grafului.

În aceste conditii, daca f[(xi,xj)] = f[(xj,xi)] = A atunci perechea neorientata {xi,xj} este o muchie iar daca f[(xi,xj)] = f[(xj,xi)] = ? spunem ca nu exista muchie intre varfurile xi si xj.

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

I.2. Concepte de baza in teoria grafurilor.

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

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