tipuri de grafuri

26
Notiuni generale. În general, pentru situaţiile care necesită la rezolvare un oarecare efort mintal (şi un caz tipic este cel al celor din economie), se caută, în primul rând, o metodă de reprezentare a lor care să permită receptarea întregii probleme dintr-o privire (pe cât posibil) şi prin care să se evidenţieze cât mai clar toate aspectele acesteia. În acest scop se folosesc imagini grafice gen diagrame, schiţe, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate în special pentru vizualizarea sistemelor şi situaţiilor complexe. În general, vom reprezenta componentele acestora prin puncte în plan iar relaţiile (legăturile, dependenţele, influenţele etc) dintre componente prin arce de curbă cu extremităţile în punctele corespunzătoare. Între două puncte pot exista unul sau mai multe segmente (în funcţie de câte relaţii dintre acestea, care ne interesează, există) iar segmentelor li se pot asocia sau nu orientări (după cum se influenţează cele două componente între ele), numere care să exprime intensitatea relaţiilor dintre componente etc. Este evident, totuşi, că această metodă are limite, atât din punct de vedere uman (prea multe puncte şi segmente vor face desenul atât de complicat încât se va pierde chiar scopul pentru care a fost creat – claritatea şi simplitatea reprezentării, aceasta devenind neinteligibilă) cât şi din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

description

definitia grafurilortipuri de grafurialgoritmi pentru determinarea drumului minim intr-un graf

Transcript of tipuri de grafuri

Notiuni generale.

În general, pentru situaţiile care necesită la rezolvare un oarecare efort

mintal (şi un caz tipic este cel al celor din economie), se caută, în primul rând,

o metodă de reprezentare a lor care să permită receptarea întregii probleme

dintr-o privire (pe cât posibil) şi prin care să se evidenţieze cât mai clar toate

aspectele acesteia.

În acest scop se folosesc imagini grafice gen diagrame, schiţe, grafice

etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea

sunt utilizate în special pentru vizualizarea sistemelor şi situaţiilor complexe.

În general, vom reprezenta componentele acestora prin puncte în plan iar

relaţiile (legăturile, dependenţele, influenţele etc) dintre componente prin arce

de curbă cu extremităţile în punctele corespunzătoare. Între două puncte pot

exista unul sau mai multe segmente (în funcţie de câte relaţii dintre acestea,

care ne interesează, există) iar segmentelor li se pot asocia sau nu orientări

(după cum se influenţează cele două componente între ele), numere care să

exprime intensitatea relaţiilor dintre componente etc.

Este evident, totuşi, că această metodă are limite, atât din punct de

vedere uman (prea multe puncte şi segmente vor face desenul atât de

complicat încât se va pierde chiar scopul pentru care a fost creat – claritatea

şi simplitatea reprezentării, aceasta devenind neinteligibilă) cât şi din punct de

vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un

om).

Din acest motiv, alături de expunerea naiv-intuitivă a ceea ce este un

graf, dată mai sus, se impune atât o definiţie riguroasă cât şi alte modalităţi de

reprezentare a acestora, adecvate în general rezolvărilor matematice.

Definiţia 1 Se numeşte multigraf un triplet G = (X, A, f) în care X şi A

sunt două mulţimi iar f este o funcţie, definită pe produsul vectorial al lui X cu

el însuşi (X2 = X×X), care ia valori în mulţimea părţilor mulţimii A (notată P(A))

Mulţimea X se numeşte mulţimea nodurilor multigrafului şi elementele

sale se numesc noduri (sau vârfuri) ale multigrafului, iar A reprezintă

mulţimea relaţiilor (legăturilor) posibile între două noduri ale multigrafului.

Definiţia 2 Se numeşte graf orientat un multigraf în care mulţimea A

are un singur element: A = {a}.

În acest caz mulţimea părţilor mulţimii A are doar două elemente:

mulţimea vidă ∅ şi întreaga mulţime A. Dacă unei perechi orientate (xi, xj) din

X2 i se asociază prin funcţia f mulţimea A atunci spunem ca există arc de la

nodul xi la nodul xj iar perechea (xi,xj) se va numi arcul (xi,xj). Nodul xi se

numeşte nod iniţial sau extremitate iniţială a arcului (xi,xj) iar nodul xj se

numeşte nod final sau extremitate finală a arcului (xi,xj). Arcul (xi,xj) este

incident spre interior vârfului xj şi incident spre exterior vârfului xi. Dacă

pentru un arc nodul iniţial coincide cu nodul final atunci acesta se numeşte

buclă. Nodurile xi şi xj se vor numi adiacente dacă există cel puţin unul din

arcele (xi,xj) şi (xj,xi).

Dacă unei perechi orientate (xi, xj) din X2 i se asociază prin funcţia f

mulţimea vidă ∅ atunci spunem că nu există arc de la nodul xi la nodul xj.

Este evident că a cunoaşte un graf orientat este echivalent cu a

cunoaşte vârfurile şi arcele sale. Din acest motiv putem defini un graf orientat

prin perechea (X,U), unde X este mulţimea vârfurilor sale iar U mulţimea

arcelor sale.

De asemenea, putem cunoaşte un graf orientat cunoscând mulţimea

nodurilor şi, pentru fiecare nod, mulţimea arcelor incidente spre exterior. Din

acest motiv putem defini un graf orientat ca o pereche (X,Γ) unde X este

perechea nodurilor iar Γ este o funcţie definită pe X cu valori înmulţimea

părţilor lui X, valoarea acesteia într-un nod xi, Γ(xi) ⊆ X fiind mulţimea

nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea

iniţială.

Definiţia 3 Se numeşte graf neorientat un multigraf în care mulţimea

A are un singur element iar funcţia f are proprietatea:

f[(xi,xj)] = f[(xj,xi)] , oricare ar fi nodurile xi şi xj din X

În aceste condiţii, dacă f[(xi,xj)] = f[(xj,xi)] = A atunci perechea

neorientată {xi,xj} este o muchie iar dacă f[(xi,xj)] = f[(xj,xi)] = ∅ spunem că nu

există muchie între vârfurile xi şi xj.

Deoarece, în cele mai multe din cazurile practice care vor fi analizate în acest

capitol, situaţia este modelată matematic printr-un graf orientat, vom folosi,

pentru simplificarea expunerii, denumirea de graf în locul celei de graf

orientat iar în cazul în care graful este neorientat vom specifica acest fapt la

momentul respectiv.

Moduri de prezentare ale unui graf

A. O primă modalitate de reprezentare este listarea efectivă a tuturor

nodurilor şi a arcelor sale.

B. Putem reprezenta graful dând pentru fiecare nod mulţimea nodurilor

cu care formează arce în care el este pe prima poziţie.

C. Putem reprezenta geometric graful, printr-un desen în plan,

reprezentând fiecare nod printr-un punct(cerculeţ) şi fiecare arc

printr-un segment de curbă care are ca extremităţi nodurile arcului şi

pe care este trecută o săgeată orientată de la nodul iniţial spre cel

final.

D. Putem folosi o reprezentare geometrică în care nodurile sunt

reprezentate de două ori, în două şiruri paralele, de la fiecare nod din

unul din şiruri plecând săgeţi spre nodurile cu care formează arce în

care el este pe prima poziţie, de pe al doilea şir (reprezentarea prin

corespondenţă).

E. Un graf poate fi reprezentat printr-o matrice pătratică booleană, de

dimensiune egală cu numărul de noduri, în care o poziţie aij va fi 1

dacă există arcul (xi,xj) şi 0 în caz contrar, numită matricea

adiacenţelor directe.

F. Un graf poate fi reprezentat printr-o matrice pătratică latină, de

dimensiune egală cu numărul de noduri, în care pe o poziţie aij va fi

xixj dacă există arcul (xi,xj) şi 0 în caz contrar.

Exemplu: Dacă în reprezentarea A avem graful G = (X,U), unde X = {x1, x2, x3,

x4, x5, x6} şi U = {(x1,x1), (x1,x2), (x1,x4), (x1,x5), (x2,x3), (x2,x4), (x2,x6), (x3,x1),

(x3,x2), (x4,x5), (x5,x2), (x6,x4)}, atunci în celelalte reprezentări vom avea:

În teoria grafurilor, problema celui mai scurt drum constă în găsirea unui drum astfel încât

suma “costurilor” muchiilor constituente să fie minimă. Un exemplu îl constituie găsirea celei

mai rapide modalităţi de a trece de la o locaţie la alta pe o hartă; în acest caz nodurile sunt

reprezentate de către locaţiile respective, iar muchiile reprezintă segmentele de drum, şi

sunt ponderate, costurile constituind timpul necesar parcurgerii acelui segment.

Formal, fiind dat un graf ponderat (adică, o mulţime de vârfuri V, o mulţime a muchiilor E, şi

o funcţie de cost:

f : E →R

cu valori reale) şi un element v al lui V, să se găsească un drum P de la v la fiecare v′ din V

astfel încât

să fie minim între toate drumurile ce leagă v de v′ .

Uneori mai poate fi recunoscută sub numele de problema drumului cel mai scurt

corespunzător perechii singulare, cu scopul deosebirii acesteia de următoarele generalizări:

• problema drumului cel mai scurt corespunzător sursei unice, o problemă mai

generală, în care trebuie să găsim cele mai scurte drumuri de la un nod sursă v la toate

celelalte noduri ale grafului.

• problema drumului cel mai scurt corespunzător tuturor perechilor reprezintă o

problemă şi mai generală, în care trebuie să găsim cele mai scurte drumuri între oricare

pereche de noduri (vârfuri) v, v′ din graf. Ambele generalizări amintite au algoritmi mai

performanţi în practică decât simpla rulare a algoritmului corespunzător drumului cel mai

scurt în cazul perechii-unice (singulare) pentru toate perechile relevante de vârfuri.

Algoritmi

Cei mai importanţi algoritmi care rezolvă această problemă sunt:

• Algoritmul lui Dijkstra – rezolvă problema sursei unice, dacă toate muchiile sunt

ponderate pozitiv Acest algoritm poate genera cele mai scurte drumuri de la un

anumit punct de placare s la toate celelalte noduri.

• Algoritmul Bellman-Ford – rezolvă problema sursei unice şi pentru costuri negative

ale muchiilor.

• Algoritmul Floyd-Warshall – rezolvă problema celor mai scurte drumuri

corespunzătoare tuturor perechilor.

• Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele

parțial de cost minim pentru un graf conex ponderat.

Algoritmul lui Dijkstra

Prezentare algoritm

Algoritmul lui Dijkstra este un algoritm care calculeaza drumurile minime de la un nod dat

pana la toate celalalte noduri. Grafurile pe care se aplica acest algoritm sunt, in general,

ponderate si orientate si au un anumit cost de care se va tine seama in calcularea drumului

minim.

Un graf orientat este acel graf care poate avea muchie intre doua noduri cu o singura

directie: ori se merge de la nodul A in nodul B, ori se merge de la nodul B in nodul A

(ambele variante in acelasi timp sunt imposibile, altfel am avea un graf neorientat).

Un graf ponderat, este un graf in care avem asociat un cost fiecarei muchii. In cazul in

care avem un graf neponderat, putem asocia ca drum de la un nod la altul minimul de muchii

prin care se trece.

Algorimul lui Dijkstra, pentru a se putea rula, are nevoie ca date de intrare de un graf

cu “n” noduri, de matricea de adiacenta a acestuia si de costul fieacrei muchii (toate acestea

reprezentand un graf cu toate elementele sale) si nodul de start.

Dupa rularea algoritmului, acesta obtine un vector in care pune distanta minima de la

nodul de start pana la fiecare nod in parte astfel:

D = [ dist A-A ; dist A-B ; dist A-C ; … ; dist A-N ]

si un vector in care salveaza parintele direct al nodului la care afiseaza distanta minima.

Acesta este un vector “T” care are “n” elemente.

EXEMPLU DE DATE INTRARE – IESIRE:

Numarul de noduri: 3

Matrice de adiacenta:

0 1 0

0 0 1

0 0 0

Matrice de cost:

0 1 0

0 0 2

0 0 0

Nod de start: A

Acestea sunt datele de intrare care definesc graful desenat mai sus.

Datele de iesire vor fi:

D = [ 0 ; 1 ; 3 ] -> distanta A-A=0, distanta A-B=1 si distanta A-C=3;

T = [ - ; A ; B ] -> din A plecam, punem -, in nodul B ajungem cu costul minim 1 direct din

nodul de start, in nodul C ajungem cu costul minim 3 si parintele sau direct (ultimul parinte)

este nodul B;

Modul de functionare al algoritmului:

Algoritmul lui Dijkstra are tot atatia pasi cate noduri are graful nostru. La fiecare pas

se actualizeaza vectorul D si vectorul T cu noile valori gasite (in cazul in care acestea

convin). Pentru rularea algoritmului lui Dijkstra, mai avem nevoie de un vector in care ne

vom nota daca s-a plecat dintr-un nod vreodata sau nu. Este necesar sa facem acest lucru

pentru ca trebuie sa plecam cel mult odata din fiecare nod. Inainte sa plecam dintr-un nod si

sa facem instructiunile necesare, vom nota acest nod ca extras / activ si nu vom mai putea

pleca in alt pas tot din el.

Se initializeaza vectorul de distante cu valoarea 9999 reprezentand o valoare infinita,

urmand ca pe parcursul programului aceasta sa fie ajustata.

La primul pas se va pleca din nodul de start, se va bifa acesta ca extras/ales si se va

completa in vectorul D distanta pana la fiecare nod in parte (daca exista muchie), iar in

vectorul T se va trece nodul de start pe aceeasi pozitie pe care s-a completat distanta in

vectorul D.

La urmatorul pas se alege, din vectorul D, nodul a carui cifra reprezinta cel mai mic

drum cu conditia ca acel nod sa nu fi fost extras / ales, altfel se trece la urmatoarea valoare

cea mai mica.

In cazul in care are muchie cu alte noduri se aduna costul acelei muchii cu costul

calculat pana la nodul din care am pornit si in cazul in care aceasta este mai mica decat

valoarea inregistrata in vectorul D se inlocuieste cu aceasta, iar in vectorul T, pe aceeasi

pozitie trecem nodul actual.Se repeta astfel cele spuse mai sus pana cand ajungem sa plecam

din toate nodurile o singura data.

In urma acestor “n” pasi, vom gasi parcurgerea grafului in functie de costul minim.

Exemplu practic:

Avem urmatoarele orase si rutele posibile dintre acestea cu tot cu numarul de kilometrii

(practic, acesta ar fi un graf neorientat, dar il vom considera orientat pentru aplicarea

algoritmului lui Dijkstra)

PASUL I : Consideram ca trebuie sa plecam din orasul Craiova. Observam pe figura

urmatoare legaturile din Craiova (directe) catre celalate orase si schimbarile ce au loc in

vectorul D si in vectorul T.

Consideram nodurile in ordine alfabetica: BALCESTI, CRAIOVA, PITESTI, SLATINA,

VALCEA

D = [ 40; 0; 100; 60; ∞ ] si T = [Craiova; Craiova; Craiova; Craiova; -]

PASUL II: Valoarea cea mai mica din vectorul D este 40 care ii corespunde orasului

Balcesti. Verificam muchiile care pleaca din Balcesti si vedem ca avem drum spre Valcea cu

costul 80. Adunam 80 la drumul obtinut pana in Balcesti si daca acesta este mai mic decat

drumul pana in Valcea obtinut la pasii anteriori, il actualizam in vectorul D.

D = [40; 0; 100; 60; 120] si T = [Craiova; Craiova; Craiova; Craiova; Balcesti]

PASUL III: Cautam cea mai mica valoare din vectorul D cu observatia sa nu se fi plecat din

acel oras niciodata. Vedem ca cea mai mica valoare este 60 si este vorba de orasul Slatina.

Asadar, la acest pas vom pleca din Slatina. Avem drum in Pitesti (30) si in Valcea (40).

CRAIOVA – SLATINA – PITESTI = 60 + 30 = 90 (mai scurt decat Craiova – Pitesti)

CRAIOVA – SLATINA VALCEA = 60 + 40 = 100 (mai scurt decat Craiova – Balcesti –

Valcea)

D = [40; 0; 90; 60; 100] si

T = [Craiova; Craiova; Slatina; Craiova; Slatina]

PASUL IV: Cautam cea mai mica valoare din vectorul D cu observatia sa nu se fi plecat din

acel oras niciodata. Vedem ca cea mai mica valoare este 90 si este vorba de orasul Pitesti.

Asadar, la acest pas vom pleca din Pitesti. Nu avem drum catre nici un alt oras, asadar la

acest pas valorile din D si din T vor ramane nemodificate.

D = [40; 0; 90; 60; 100] si T = [Craiova; Craiova; Slatina; Craiova; Slatina]

PASUL V: Cautam cea mai mica valoare din vectorul D cu observatia sa nu se fi plecat din

acel oras niciodata. Vedem ca cea mai mica valoare este 100 si este vorba de orasul Valcea.

Asadar, la acest pas vom pleca din Valcea. Avem drum catre Pitesti si acest drum are 70 km:

CRAIOVA – SLATINA – VALCEA – PITESTI = 100 + 70 = 170, dar drumul actual pana in

Pitesti este de 90 km, deci nu se va modifica aceasta valoare, deoarece drumul prin Valcea

este mai lung.

D = [40; 0; 90; 60; 100] si T = [Craiova; Craiova; Slatina; Craiova; Slatina].

A. Algoritmul lui Kruskal

Pasul 1. Dintre toate muchiile grafului se alege muchia de valoare minimă (maximă). Dacă

minimul este multiplu se alege la întâmplare una din muchiile respective. Deoarece

acest "la întâmplare" trebuie cumva tradus în limbajul calculatorului, în cazul

implementării unui program bazat pe acest algoritm, vom perturba din start valorile

muchiilor, la k muchii cu aceiaşi valoare V adunând respectiv valorile ε, 2ε, ... , kε,

unde ε este foarte mic (în orice caz, kε mai mic decât diferenţa dintre valoarea

acestor arce si valoarea imediat superioară a unui arc), pozitiv.

Pasul 2. Dintre toate muchiile rămase, se alege cea de valoare minimă (maximă);

Pasul 3. Dintre toate muchiile rămase, se alege cea de valoare minimă (maximă), astfel încât

să nu se formeze cicluri cu cele deja alese;

Pasul 4. Se reia algoritmul de la pasul 3 până se colectează n-1 muchii.

Deşi s-a demonstrat că algoritmul găseşte întotdeauna arborele optim, el are

dezavantajul că este foarte laborios (de fiecare dată trebuie calculat minimul unei mulţimi

mari sau foarte mari – există situaţii în practică în care graful are sute de mii de arce) şi, în

plus, trebuie aplicat un algoritm special ca să respectăm condiţia de a nu se forma cicluri, la

alegerea unui nou arc.

O metodă posibilă este ca, după adăugarea fiecărui arc, să se împartă graful în

componente conexe şi să alegem apoi un arc care nu are ambele extremităţile în aceeaşi

componentă conexă.

De asemenea este clar că, în cazul existenţei arcelor de valori egale, deoarece se alege la

întâmplare, există mai multe variante de evoluţie a alegerii arcelor. Totuşi, cu toate că pot fi

mai multe grafuri la care se poate ajunge prin acest algoritm, ele vor avea toate aceeaşi

valoare (minima (sau maxima) posibilă).

B. Algoritmul lui Sollin

Pasul 1. Pentru fiecare nod se alege muchia adiacentă de valoare minimă (maximă).

Pasul 2. Se evidenţiază componentele conexe, existente în graful parţial format din arcele

alese până în acest moment.

Pasul 3. Pentru fiecare componentă conexă se alege muchia adiacentă de valoare minimă

(maximă). Prin muchie adiacentă unei componente conexe înţelegem o muchie care

are o singură extremitate printre nodurile componentei respective.

Pasul 4. Se reia algoritmul de la pasul 2 până rămâne o singură componentă conexă. Aceasta

este arborele optim căutat.

Acest algoritm asigură de asemenea găsirea arborelui optim, necesită mult mai puţine

calcule (la fiecare alegere se calculează minimul doar pentru muchiile adiacente unui singur

nod), evită automat formarea ciclurilor, dar, pentru grafuri foarte mari, la un moment dat pot

exista atât de multe componente conexe care trebuie memorate succesiv, încât calculul devine

greoi sau, pe calculator, depăşeşte posibilităţile de memorare ale calculatorului.

C. O variantă a algoritmului lui Kruskal

Pasul 1. Dintre toate muchiile grafului se alege cea de valoare minimă (maximă);

Pasul 2. Dintre toate muchiile adiacente componentei conexe formată din arcele alese până în

acest moment, se alege cea de valoare minimă (maximă);

Pasul 3. Se reia pasul 2 până se colecţionează n-1 muchii.

Algoritmul are toate avantajele algoritmului lui Sollin şi, în plus, lucrează cu o singură

componentă conexă, fiind mult mai uşor de implementat pe calculator şi mult mai rapid în

execuţie.

Exemplu: Administraţia unei localităţi montane a hotărât construirea unor linii de

teleferic care să lege oraşul de cele 8 puncte turistice importante din jurul acestuia. În urma

unui studiu au fost puse în evidenţa toate posibilităţile şi costurile de conectare a obiectivele

turistice între ele şi cu oraşul, acestea fiind prezentate în figura 4.2.

Se cere găsirea variantei de construcţie de cost minim, care să asigure accesul din oraş la

oricare din obiectivele turistice.

Rezolvare

Condiţia de cost minim implică două obiective:

1. Să se construiască minimul de arce necesare;

2. Să se construiască cele mai ieftine legături.

Referitor la numărul de arce necesar, facem observaţia că, dacă din oraş se va putea

ajunge la orice obiectiv turistic, atunci se va putea ajunge şi de la orice staţiune la oricare alta

(trecând prin oraş), deci trebuie ca arcele alese pentru construcţie să formeze la un loc un graf

conex.

În concluzie, căutăm un graf parţial conex cu un număr minim de arce, adică un

arbore. În plus, suma costurilor arcelor sale trebuie să fie minimă. Vom aplica pe rând cei trei

algoritmi pentru găsirea acestuia:

A. Kruskal

La primul pas poate fi ales unul din arcele OP3 sau OP7, ele având valoarea minimă 2.

Putem alege oricum primul arc dintre cele două pentru că la al doilea pas va fi ales celălalt.

La pasul trei poate fi ales unul din arcele OP5, OP6 sau P1P6 care au valoarea minimă 3.

Nici în acest caz nu are vre-o importanţă ordinea alegerii, deoarece pot fi alese succesiv toate

trei fără a se forma nici un ciclu.

Al şaselea arc poate fi ales dintre arcele P4P5 şi P1P2, care au valoarea minimă 4. Nici

în acest caz nu are vre-o importanţă ordinea alegerii, deoarece pot fi alese succesiv ambele,

fără a se forma nici un ciclu.

Următoarea valoare disponibilă a unui arc este 5, dar arcul opt nu poate fi ales dintre

arcele OP1, P6P7, deşi au valoarea minimă 5. Arcul OP1 nu poate fi ales deoarece s-ar forma

ciclul OP1P6, iar P6P7 ar duce la ciclul OP6P7. Următoarea valoare minimă este 6, pentru arcul

P5P7 dar nu poate fi ales deoarece se formează ciclul OP5P7.

Valoarea următoare, 7, o au arcele OP4, P2P3 şi P5P8. OP4 nu poate fi ales deoarece s-ar forma

ciclul OP5P4. Arcul P2P3 nu poate fi ales deoarece s-ar forma ciclul OP6P1P2P3. Arcul P5P8 nu

formează nici un ciclu şi el va fi al optulea arc ales. În acest caz, deoarece s-au adunat 8 arce

într-un graf cu 9 noduri, am obţinut graful căutat.

B. Sollin Vom alege:

pentru nodul O

→ arcul OP3

pentru nodul P1

→ arcul P1P6

pentru nodul P2

→ arcul P1P2

pentru nodul P3

→ arcul OP3

pentru nodul P4

→ arcul P4P5

pentru nodul P5

→ arcul OP5

pentru nodul P6

→ arcul P1P6

pentru nodul P7

→ arcul OP7

pentru nodul P8

→ arcul P5P8

Rezultă graful parţial:

După cum se vede, s-au format două componente conexe: C1 = {P1,P2,P6}

C2 = {O,P3,P4,P5,P7,P8}. Vom alege: pentru C1 → arcul OP6

pentru C2 → arcul OP6

şi obţinem o singură componentă conexă, care este arborele căutat.

C. Varianta algoritmului lui Kruskal Succesiunea alegerii arcelor va fi:

Algoritmul lui Floyd-Warshall

Algoritmii din această secţiune determină drumul de cost minim dintre oricare două

noduri dintr-un graf. Pentru a rezolva această problemă s-ar putea aplica unul din algoritmii

de mai sus, considerând ca sursă fiecare nod, pe rând, dar o astfel de abordare ar fi

ineficientă. Algoritmul Floyd-Warshall compară toate drumurile posibile din graf dintre

fiecare 2 noduri, şi poate fi utilizat şi în grafuri cu muchii de cost negativ. Estimarea drumului

optim poate fi reţinut într-o structură tridimensională d[v1, v2, k], cu semnificaţia − costul

minim al drumului de la v1 la v2, folosind ca noduri intermediare doar noduri până la nodul

k. Dacă nodurile sunt numerotate de la 1, atunci d[v1, v2, 0] reprezintă costul muchiei directe

de la v1 la v2, considerând +∞ dacă aceasta nu există. Exemplu, pentru v1 = 1, respectiv 2:

Pornind cu valori ale lui k de la 1 la |V|, ne interesează să găsim cea mai scurtă cale de

la fiecare v1 la fiecare v2 folosind doar noduri intermediare din mulţimea {1, ..., k}. De

fiecare dată, comparăm costul deja estimat al drumului de la v1 la v2, deci d[v1, v2, k-1]

obţinut la pasul anterior, cu costul drumurilor de la v1 la k şi de la k la v2, adică d[v1, k, k-1]

+ d[k, v2, k-1], obţinute la pasul anterior. Atunci, d[v1, v2, |V|] va conţine costul drumului

minim de la v1 la v2.

Aplicaţii şi generalizări

Algoritmul Floyd-Warshall poate fi folosit, printre altele, la rezolvarea următoarelor

probleme:

• Cele mai scurte drumuri în grafuri orientate (algoritmul Floyd)

• „Închiderea” tranzitivă a grafurilor orientate (algoritmul Warshall). În formularea

originală a algoritmului a lui Warshall, graful nu este ponderat şi este reprezentat cu ajutorul

unei matrice de adiacenţă booleană. Mai mult, operaţia de adunare este înlocuită de

conjuncţia logică (AND) iar operaţia de scădere de disjuncţia logică (OR).

• Găsirea unei expresii regulare, indicând limbajul regulat, acceptat de către un

automat finit (algoritmul lui Kleene)

• Inversarea matricelor reale (algoritmul Gauss-Jordan)

• Rout-area optimală. În cazul acestei aplicaţii preocuparea principală o constituie

găsirea drumului caracterizat de flux 60 maxim între două vârfuri. Aceasta reprezintă că, în

loc să considerăm minimul ca în cazul pseudocodului de mai sus, vom fi interesaţi de maxim.

Costurile muchiilor constituie restricţii în ceea ce priveşte fluxul. Costurile drumului

reprezintă „blocaje”.

Astfel, operaţia de sumare de mai sus este înlocuită cu operaţia corespunzătoare minimului.

• Testarea bipartiţiei unui graf neorientat.

Algoritmul lui Bellman – Kalaba

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.

Fie G = {x1, x2, ... ,xn} un graf orientat finit. Presupunem (fără a restrânge generalitatea, că am numerotat nodurile astfel încât nodul spre care căutăm drumurile de valoare minimă (maximă) de la celelalte noduri să fie xn.

Pasul 1. Se construieşte matricea pătratică M cu dimensiunea egală cu numărul de noduri ale grafului ale cărei elemente sunt:

Pasul 2. Se adaugă succesiv liniile Li la matricea M, elementele acestora calculându-se prin relaţiile de recurenţă:

1. L1j = mjn j = 1,...,n (prima linie este ultima coloană, transpusă, a matricii M)

2. Lij = min (Li-1,j , (mn1,kmin=

jk + Li-1,k)) într-o problemă de minim

sau Lij = max (Li-1,j , (mn1,kmax=jk + Li-1,k)) într-o problemă de maxim

Pasul 3. După calcularea fiecărei linii noi se compară elementele ei cu cele ale precedentei:

− Dacă Lij = Li-1,j pentru orice j = 1,...,n atunci se opreşte recurenţa şi ultima linie calculată conţine valorile minime ale drumurilor de la celelalte noduri la nodul xn.

− i+1 Dacă există cel puţin un indice j cu Lij ≠ Li-1,j se trece la calcularea noii linii L

Observaţie: Pentru grafuri foarte mari, algoritmul necesită un volum mare de memorie, prin necesitatea memorării matricei M, care este greu de manipulat. Chiar dacă din cele n 2 arce posibile graful ar avea doar un procent foarte mic matricea grafului va avea tot n2 poziţii de memorat şi analizat.

Exemplu: Presupunem dat graful orientat de mai jos, în care se doreşte găsirea drumului de valoare minimă de la nodul x1 la nodul x9.

iar după calcularea liniilor Li obţinem:

Deoarece L4 = L5 oprim calcularea liniilor după calcularea liniei 5. În această linie se află valorile celor mai scurte de la toate nodurile la nodul x9. Drumul dorit de noi (x1 → x9) are valoarea dată de prima poziţie a liniei 5, fiind egal cu 13.

Pentru a găsi acest drum, plecăm înapoi de la linia 4 şi avem: