Grafuri

GrafuriOrientate si neorientateGeneralitati-Grafuri neorientate Se numete graf neorientat o pereche ordonat de multimi notat G=(V, M) unde: V : este o multime finit i nevid, ale crei elemente se numesc noduri sau vrfuri; M : este o multime, de perechi neordonate de elemente distincte din V, ale crei elemente se numesc muchii. Exemplu de graf neorientat: G=(V, M) unde: V={1,2,3,4} M={(1,2), (2,3),(1,4)} n teoria grafurilor neorientate, se ntlnesc frecvent notiunile: - extremittile unei muchii fiind data muchia m=[x,y], se numesc extremitti ale sale nodurile x i y; - vrfuri adiacente dac ntr-un graf exist muchia m=[x,y], se spune despre nodurile x i y ca sunt adiacente; - incident dac m1 i m2 sunt dou muchii ale aceluiai graf, se numesc incidente dac au o extremitate comun.

Grafuri orientate Grafurile orientate sunt grafuri n care arcele care conecteaz nodurile au un singur sens. Aceast restricie face mult mai dificil evidenierea i exploatarea diverselor proprieti ale grafurilor de acest tip. Prelucrarea unui astfel de graf este identic cu o cltorie cu maina ntr-un ora cu foarte multe strzi cu sens unic sau cu o cltorie cu avionul ntr-o ar n care liniile aeriene nu sunt dus-ntors.

algoritmul lui DijkstraPentru a rezolva problema drumurilor minime cu origine unic, o manier clasic de abordare o reprezint utilizarea unui algoritm bazat pe tehnica greedy adesea cunoscut sub denumirea de algoritmul lui Dijkstra Algoritmul se bazeaz pe o structur de date mulime M care conine nodurile pentru care cea mai scurt distan la nodul origine este deja cunoscut. Iniial M conine numai nodul origine. n fiecare pas al execuiei algoritmului, se adaug mulimii M un nod x care nu aparine nc mulimii i a crui distan de la origine este ct mai scurt posibil. Presupunnd c toate arcele au ponderi pozitive, ntotdeauna se poate gsi un drum minim care leag originea de nodul x, drum care trece numai prin nodurile coninute de M. Un astfel de drum se numete drum special. Pentru nregistrarea lungimii drumurilor speciale corespunztoare nodurilor grafului se utilizeaz un tablou D care este actualizat n fiecare pas al algoritmului. n momentul n care M include toate nodurile grafului, toate drumurile sunt speciale i n conscin, tabloul D memoreaz cea mai scurt distan de la origine la fiecare nod al grafului.

Procedura DijkstraPROCEDURE Dijkstra; {Determin costurile celor mai scurte drumuri care conecteaz nodul 1, considerat drept origine, cu toate celelalte noduri ale unui graf orientat} BEGIN [1] M:= [1]; {nodul origine} [2] FOR i:= 2 TO n DO {iniilizarea lui D} [3] D[i]:= COST[1,i]; [4] FOR i:= 1 TO n-1 DO BEGIN [5] *alege un nod x aparinnd mulimii N - M astfel nct D[x] s fie minim; [6] *adaug pe x lui M; [7] FOR fiecare nod y din N - M DO [8] D[y]:= min(D[y],D[x] + COST[x,y]) END END; {Dijkstra}

Algoritmul lui Tarjan O alt metod ingenioas de determinare a componentelor puternic conectate(conexe) ale unui graf orientat a fost publicat de R.E. Tarjan n anul 1972. Metoda se bazeaz tot pe tehnica cutrii n adncime. n legtur cu aceast secven se fac cteva precizri: (1) Graful se consider reprezentat printr-o structur de adiacene implementat cu ajutorul listelor nlnuite simple. (2) Funcia Tarjan prezentat, utilizeaz variabila min pentru a determina cel mai nalt nod care poate fi atins prin intermediul unui arc de tip napoi, pentru orice descendent al nodului k pe care l primete ca i parametru. Acest lucru este realizat ntr-o manier similar funciei care determin componentele biconexe ale unui graf

---------------------------------------------------- FUNCTION Tarjan(k: integer): integer; {Determinarea componentelor puternice } VAR t: legatura; m,min: integer; BEGIN id:= id + 1; marc[k]:= id; min:= id; Stiva[p]:= k; p:= p + 1; t:= Stradj[k]; WHILE t z DO BEGINIF marc[t^.nume] = 0 THEN m:= Tarjan(t^.nume); ELSE m:= marc[t^.nume]; IF m < min THEN min:= m; t:= t^.urm END; IF min = marc[k] THEN BEGIN REPEAT p:= p - 1; write(nume(Stiva[p])); marc[Stiva[p]]= N+1 UNTIL Stiva[p] = k; writeln END; Tarjan:= min; END;Informaticieni influentiRobert Floyd Robert Floyd(n.8 iunie1936,New York,SUA d.25 septembrie2001) a fost un informatician american, laureat alPremiului Turingn1978pentru influena pe care a exercitat-o asupra metodologiilor de creare de software eficient i fiabil. El a inventat tehnica de verificare a programelor folosind aseriuni logice, n lucrarea saAssigning Meaning to Programs.

Edsger Wybe Dijkstra(n.11 mai1930,Rotterdam- d.6 august2002,Nuenen)i-a luat licena nfizic teoreticlaUniversitatea din Leiden. Dup o perioad de lucru ca cercettor laBurroughs Corporation, a lucrat laUniversitatea Tehnic din Eindhoveni mai apoi laUniversitatea din Austin, Texas, de unde s-a retras n2000.Dijkstra a rmas celebru pentrualgoritmul drumului minimntr-ungraf, algoritm care-i poart numele.

Bibliografiewww.wikipedia.com/grafuri

Proiect realizat de:Duca IoanPorumb Valentin