tema 1-1_arbori minimali si drum minim in grafuri

CAPITOLUL 1

TEORIA GRAFURILOR.

OPTIMIZRI N REELE DE TRANSPORT I DISTRIBUIE

1.1. Modelarea problemelor de transport i distribuie

ntr-o mare varietate de contexte se pune problema deplasrii unei cantiti Q ce poate fi materie, energie, informaie, etc. din unele locuri numite surse n alte locuri numite destinaii, aceast deplasare realizndu-se pe anumite rute de legtur. Unitile indivizibile ale cantitii Q care se deplaseaz de-a lungul rutelor se vor numi uniti de flux.

O clasificare a problemelor de transport i distribuie

Pentru Cercetarea Operaional, problema enunat va prezenta interes numai dac respect urmtoarele ipoteze: a) cel puin o surs poate aproviziona mai multe destinaii i cel puin o destinaie poate primi uniti de flux de la mai multe surse.

Rutele de legtur pot avea i alte puncte comune n afara surselor i destinaiilor, numite puncte intermediare sau de tranzit. Nu sunt excluse legturile directe ntre surse sau ntre destinaii. n principiu, orice rut poate fi parcurs n ambele sensuri, dar pot exista i rute cu sens unic.

Ansamblul surselor, destinaiilor, al punctelor intermediare i al rutelor de legtur se va numi reea de transport; el se identific cu un graf neorientat sau parial orientat ca n figura 1.1. b) Unele rute de legtur pot avea limitri superioare i / sau inferioare pentru volumul unitilor de flux ce se deplaseaz ntr-un sens sau altul. Aceste limitri poart numele de capaciti (inferioare, respectiv superioare). n continuare, vom avea n vedere numai cazul n care toate capacitile inferioare sunt egale cu zero, capacitile superioare fiind exprimate prin numere pozitive. c) Exist un cost al deplasrii unei uniti de flux de la un punct al reelei la altul, cost care poate fi exprimat n bani, timp sau distan. Sunt situaii n care acest cost poate semnifica profitul obinut de pe urma deplasrii. Pe aceeai rut, costurile i capacitile pot fi diferite n funcie de sensul de parcurgere al rutei.

Ipoteza a) va fi ntotdeauna presupus n timp ce ipotezele b) i c) pot fiina separat sau simultan.

1) n prezena ipotezei c) i absena condiiei b) se pune problema deplasrii cantitii de flux Q de la surse la destinaii la un cost total minim. Dac sursele sunt n legtur direct cu destinaiile obinem problema clasic de transport, care va face obiectul Capitolului 4 al cursului. Cazul general, n care exis i puncte intermediare, este cunoscut sub numele de problema transferului i el nu face obiectul cursului de fa. n cazul particular al unei singure surse s, al unei singure destinaii t i a unei singure uniti de flux se

Figura 1.1.

b)

3

100

300 1

2

5

4

400 200

100

300

50

: surs (furnizor) : destinaie (consumator)

a)

F1

F2

C1

120

C2

230 C3

c11

c12

c13

c21

c22

c23

CURSUL 1

Capitolul 1 Teoria grafurilor. Optimizri n reele de transport i distribuie

2

obine problema drumului de cost minim de la s la t, problem de care ne vom ocupa n seciunea 1.4 a acestui capitol.

2) n prezena ipotezei b) i absena ipotezei c) se pune problema dac reeaua, ale crei rute sunt capacitate, este capabil s permit acoperirea integral a cererilor n punctele de destinaie. Pentru aceasta, se va rezolva problema determinrii volumului maxim Q* de uniti de flux ce pot fi deplasate de la surse la destinaii. Dac Q* < Q vor exista destinaii a cror cerere este acoperit doar n parte i atunci se ridic problema mririi capacitii de transfer a reelei. Am descris succint problema fluxului maxim, problem ce va fi abordat n cadrul cursului de Cercetri Operaionale din anul 2.

3) n prezena simultan a ipotezelor b) i c) se pune problema satisfacerii cererilor n punctele de destinaie la un cost de transport minim. Ca i n cazul precedent vom avea n vedere o problem modificat: vom determina mai nti cantitatea maxim de flux ce poate fi deplasat de la surse la destinaii i apoi modul de organizare al deplasrii astfel nct costul operaiei s fie minim. Aceasta este problema fluxului (maxim) de cost minim, problem abordat, de asemenea, n cadrul cursului de Cercetri Operaionale din anul 2.

n seciunile urmtoare vom trata dou probleme de optimizare n reele de transport: problema determinrii unui arbore maximal (de acoperire) de valoare (cost) minim i problema drumului de cost minim de la s la t .

1.2 Concepte utilizate n teoria grafurilor

n seciunea 1.1 am vizualizat elementele unei reele de transport printr-un desen compus din puncte i arce care unesc unele din aceste puncte (vezi figura 1.1). Un asemenea desen constituie forma uzual de prezentare a unui concept deosebit de important, att n sine ct i pentru studiul unei impresionante varieti de probleme din cele mai diverse domenii, domeniul economic fiind prioritar.

Am socotit deci necesar s includem aici cteva elemente privitoare la conceptul de graf, cci despre el este vorba. Aceste elemente vor fi foarte utile pentru nelegerea consideraiilor teoretice dezvoltate n legtur cu rezolvarea problemei de transport i de asemenea constituie cadrul natural de abordare i a celorlalte probleme amintite n clasificarea dat n seciunea precedent.

Un graf este un cuplu G = (V, E) format dintr-o mulime nevid V, ale crei elemente se numesc

vrfuri sau noduri i o mulime E de elemente, zise muchii, cu proprietatea c fiecrei muchii e E i sunt

asociate dou noduri x, y V, nu neaprat distincte, numite extremitile muchiei e. Un subgraf al grafului

G = (V, E) este un graf G = (V, E) n care V V, E E i orice muchie e E are aceleai extremiti att n G ct i n G.

Dup cum se vede, definiia general nu exclude existena muchiilor cu o singur extremitate (aceste muchii se numesc bucle), nici existena mai multor muchii cu aceleai extremiti (figura 1.2.a)

a) b)

Figura 1.2.

Graful G se va numi simplu dac nu are bucle i oricare dou noduri sunt extremiti pentru cel mult o muchie. Vom spune c G este finit dac vrfurile i muchiile sale sunt n numr finit.

n continuare, vom avea n vedere n exclusivitate grafuri finite i simple aa cum este cel reprezentat grafic n figura 1.2.b).

Fie e = x, y o muchie a grafului G = (V, E); extremitile sale pot fi ordonate n dou moduri: (x, y) i (y, x). Cele dou perechi se numesc rute orientate sau arce generate de muchia subiacent e; spunem c arcul (x, y) are extremitatea iniial x i extremitatea final y i c (y, x) este arcul opus lui (x, y). A orienta

x

y

z

u

t

v


3

muchia x, y nseamn a alege unul din arcele (x, y) sau (y, x); dac a fost ales arcul (x, y) vom spune c (x, y) este un arc permis i c arcul (y, x) este blocat. Dac o asemenea alegere nu a fost fcut vom spune c

muchia x, y este neorientat. n acest caz, convenim ca ambele arce (x, y) i (y, x), generate de muchia

x, y, s fie considerate permise. n fine, a da o orientare n graful G nseamn a orienta unele din muchiile sale; orientarea poate fi total sau parial dup cum toate muchiile grafului au fost orientate sau numai o parte din ele. Este clar c n acelai graf G pot fi date mai multe orientri; dac G are m muchii, atunci exist 2

m orientri totale diferite ale acestuia!

Un graf orientat (parial orientat, neorientat) este un graf n care s-a dat o orientare total (o orientare parial, respectiv nu s-a dat nici o orientare); de exemplu, graful din figura 1.1.a) este (total) orientat iar cel din figura 1.1.b) numai parial. Graful din figura 1.2.b) este neorientat.

n unele situaii este util s se pun n eviden arcele permise ale unui graf (parial) orientat; realizarea grafic, intuitiv a acestei operaii este fcut n figura 1.3.

Se constat uor c dac G este (total) neorientat, numrul arcelor permise este de dou ori mai mare dect numrul muchiilor din G.

n continuare vom introduce o serie de noiuni frecvent utilizate n teoria grafurilor. Unele din ele se refer la muchii i de aceea se numesc generic concepte neorientate altele se refer la rutele orientate permise, drept care se mai numesc i concepte orientate. Vom considera un graf (finit, simplu) G = (V, E), n care (eventual) s-a dat o orientare pe unele din muchii (posibil pe toate).

Un lan n graful G este o succesiune de noduri = (x0, x1, ... , xp-1, xp) cu proprietatea c x0, x1,

x1, x2, ..., xp-1, xp sunt muchii n G. Vom spune c x0 i xp sunt extremitile lanului i c trece prin

nodurile intermediare x1, ... , xp-1. Lanul se zice simplu dac nu trece de dou ori prin acelai nod. Prin

definiie lungimea lanului este dat de numrul muchiilor componente. Astfel, lanurile de lungime unu se identific cu muchiile grafului G; un lan de lungime doi este constituit din dou muchii adiacente (au o extremitate n comun).

Un ciclu este un lan ale crui extremiti coincid.

n figura 1.2.b) succesiunile de noduri = (x, y, t, u, v) i = (x, z, y, t, z, v) sunt lanuri: este un

lan simplu de lungime 4 n timp ce are lungimea 5 i nu este simplu. Succesiunea = (x, y, t, u, x) este un ciclu de lungime 4.

Un drum n graful G este o succesiune de noduri = (x0, x1, ... , xp -1, xp) cu proprietatea c (x0, x1),

(x1, x2), ..., (xp -1, xp) sunt arce permise. Nodul x0 este extremitatea iniial a drumului iar xp extremitatea final. Un circuit este un drum ale crui extremiti coincid. Este clar c orice drum este un lan, reciproca

nefiind adevrat ntotdeauna. n figura 1.3, = (z, t, x) este un drum de lungime 2 iar = (x, y, t, x) este un

circuit de lungime 3; n acelai graf, = (z, x, y) este un lan care nu este un drum deoarece arcul (z, x) este blocat.

Graful G = (V,E) se zice conex dac oricare dou noduri ale sale sunt extremitile unui lan. Dac G nu este

conex, exist partiiile V = V1V2 .... Vs i

E = E1E2....Es astfel nct G1 = (V1,E1) , G2 = (V2,E2) , ..., Gs = (Vs,Es) sunt grafuri conexe. Subgrafurile G1, G2,...., Gs se

numesc componentele conexe ale grafului G. Graful din figura

1.3 este conex (ca i cele din figurile anterioare); graful din figura 1.4 are trei componente conexe.

Graful G G2

G1 G3

Figura 1.4.

Figura 1.3.

x y

z t

x y

z t


4

Graful G = (V,E) se numete bipartit dac mulimea nodurilor sale poate fi descompus n dou submulimi nevide i disjuncte S i T, astfel nct orice muchie din G are o extremitate n S i cealalt n T.

Este clar c graful asociat unei probleme clasice de transport este bipartit (figura 1.1.a), nodurile care reprezint furnizorii formnd mulimea S iar nodurile corespunztoare consumatorilor alctuind mulimea T.

Calitatea unui graf de a fi bipartit nu depinde de modul

particular de reprezentare aa cum arat exemplul din figura 1.5.

Adiacen i inciden. Fie G = (V, E) un graf i xi, xj V. Nodurile xi i xj sunt noduri adiacente dac exist o muchie e = [xi, xj] care le unete. Dac e = [xi, xj], muchia e i nodul xi sau muchia e i nodul xj sunt incidente. Dou muchii e1 i e2 ale grafului sunt muchii adiacente dac sunt incidente n acelai nod (au o extremitate n comun).

1.3. Arbori de valoare minim

Fie G = (V, E) un graf neorientat, cu mulimea nodurilor V = x1, x2,, xn. Notm cu E(x)

mulimea muchiilor incidente ntr-un nod x, cu numrul elementelor E(x). Un nod se numete

suspendat (sau nod frunz) dac exist o singur muchie incident n x (altfel spus E(x) = 1). Un nod x

este izolat dac nu exist nici o muchie incident n x ( E(x) = 0 ). Un arbore este un graf neorientat, conex i fr cicluri (figura 1.6.).

Propoziia 1.1* Un arbore H = (V, E), avnd V = n noduri i E = m muchii are urmtoarele proprieti echivalente:

1) H este conex i fr cicluri; 2) H este fr cicluri i are n 1 muchii; 3) H este conex i are n 1 muchii; 4) H este fr cicluri i dac se unesc printr-o muchie dou noduri neadiacente, se creeaz un

ciclu i numai unul (figura 1.7); 5) H este conex i dac i se suprim o muchie se creeaz dou componente conexe (orice

muchie din H este o punte ntre dou noduri), graful se disconecteaz (figura 1.8); 6) Orice pereche de noduri este legat printr-un lan i numai unul.

* Pentru demonstraiile teoremelor, lemelor i propoziiilor acestui capitol a se vedea: Ciobanu Gh., Nica V., Musta

Floare, Mrcine Virginia, Mitru D., Cercetri Operaionale. Optimizri n reele. Teorie i aplicaii economice, Editura MatrixRom, Bucureti, 2002

Figura 1.6.

**

* *

**

adaug *

**

d c

a b

T S

c

b

d

a

Figura 1.5.

Figura 1.7


5

Figura 1.8

Un arbore H ntr-un graf G este un subgraf care - de sine stttor - este un arbore. H se zice maximal dac conine toate nodurile grafului G (figura 1.9).

S considerm un graf G = (V, E) conex. O muchie e E este valorizat dac i se asociaz o valoare

nenegativ v(e) 0. Aceste valori pot reprezenta costuri, timpi de parcurgere, lungimi, profituri ale legturilor definite prin muchiile grafului. Un graf G este valorizat dac toate muchiile sale sunt valorizate.

Valoarea unui arbore H = (V, Y) coninut n graful G = (V, E), Y E este, prin definiie, suma valorilor muchiilor sale:

v(H) = Ye

ev . (1.1)

Problema extremal pe care dorim s o rezolvm este problema arborelui de valoare minim: s se

determine un arbore de maximal H* = (V, Y*) coninut ntr-un graf G = (V, E), Y* E de valoare minim:

v(H*) = v(H)H

min (1.2)

unde v(H) este valoarea unui arbore determinat cu relaia (1.1).

Problema determinrii unui arbore de valoare minim const n determinarea unui arbore maximal H* care acoper graful dat G astfel nct acesta s fie:

(1) conex (fiecare nod s fie conectat cu oricare alt nod); (2) fr legturi redundante (un singur lan este suficient pentru a conecta un nod cu oricare alt nod); (3) de valoare minim (avnd n vedere valorile asociate muchiilor).

Similar, se definete problema arborelui de valoare maxim, care const n determinarea unui arbore H* care acoper graful dat G i care verific proprietile (1) i (2), de mai sus, iar proprietatea (3) este nlocuit cu:

v(H*) = v(H)

Hmax

unde v(H) este valoarea unui arbore determinat de relaia (1.1).

n situaia n care valorile muchiilor grafului nu sunt distincte, problema nu admite, n general, soluie unic. Pentru determinarea tuturor soluiilor, se va alege la fiecare etap k numai o muchie dintre cele

scoate

G Arbore maximal n G Arbore nemaximal n G

Figura 1.9.


6

cu valori egale i se verific pentru fiecare dintre acestea dac formeaz ciclu cu muchiile deja alese n etapele 1,2, , k-1.

n activitatea economic, de multe ori apare problema determinrii unor arbori de valoare optim (minim sau maxim), ntruct exist procese economice sau activiti economice care pot fi reprezentate cu ajutorul unui arbore n condiii convenabile. Aceast problem are importan practic n trasarea reelelor de comunicaii i a reelelor de distribuie, n general, n studiul reelelor de transport:

aprovizionarea cu ap potabil sau cu energie electric sau termic a unor puncte de consum de la un punct central;

conectarea printr-o reea de drumuri a unor puncte de interes economic sau turistic;

evoluii posibile ale unui sistem pornind de la o stare iniial;

construirea unei reele telefonice radiale, a unei reele de televiziune sau internet de la un punct central;

schemele bloc ale programelor pentru calculatoare;

studiul circuitelor electrice n electrotehnic, etc.

Procedeul de construcie efectiv a unui arbore care acoper un graf dat G este prezentat n cele ce urmeaz:

1.3.2. Algoritmul Kruskal1)

Fie G = (V, E) un graf conex cu n = V i cu muchiile valorizate v(e) 0, e E.

Etapa de iniializare: Din mulimea muchiilor E se alege o muchie e1 cu valoarea v(e1) cea mai mic. Dac exist mai multe muchii cu aceeai valoare se alege una dintre acestea. Fie Y mulimea muchiilor alese. Iniial Y = {e1} i |Y| = 1.

Etapa iterativ: Din mulimea muchiilor neselectate E Y se alege o muchie ei cu valoarea v(ei) cea mai mic, pentru care

Y ei nu conine un ciclu. Se ia Y ei Y i |Y| + 1 |Y|.

STOP: Etapa iterativ se oprete atunci cnd sunt alese n-1 muchii. H = (V, Y) este arborele de acoperire de valoare minim. Arborele de valoare minim H = (V, Y) este determinat de muchiile alese. n cazul n care exist mai multe muchii de valori egale, arborele de valoare minim nu este, n general, unic. Este preferabil, n aceste situaii, s fie determinai toi arborii de valoare minim i dintre acetia un manager (decident) s l aleag pe cel mai convenabil corespunztor unui alt criteriu economic. Algoritmul Kruskal este foarte simplu. El intr n categoria algoritmilor de tip "greedy" (lacom) deoarece la fiecare pas al algoritmului se alege cea mai bun variant. Totui, acest algoritm din tiina managementului produce ntotdeauna soluia optim. Algoritmul Kruskal poate fi utilizat i pentru determinarea arborilor de acoperire de valoare maxim, prin nlocuirea, n algoritm: "se alege muchia cu valoarea cea mai mic" cu "se alege muchia cu valoarea cea mai mare".

Exemplul 1.1: Problema sistemului de comunicaii

ntr-un ora se studiaz posibilitatea ca principalele instituii s fie conectate ntr-un sistem printr-o reea de telecomunicaii. Schema tuturor legturilor posibile, precum i costul executrii acestor legturi ntre ase dintre instituiile oraului sunt indicate n graful din figura 1.10. Valorile indicate pe arce reprezint costurile (n uniti monetare) asociate realizrii legturilor dintre instituii. S se determine modul n care vor fi interconectate cele ase instituii astfel nct costul realizrii sistemului de telecomunicaii s fie minim.

1)

J. B. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proceedings of the

American Mathematical Society 7, 48-50, 1956.


7

Rezolvare:

Pentru rezolvarea acestei probleme se aplic algoritmul Kruskal. Muchia cu cel mai mic cost este [A,C] cu v[A, C] = 3 u.m.. Aceasta este prima alegere. n continuare, pot fi alese muchiile [D, E] i [D, F], fiecare avnd costul de 4 u.m.. Pentru c fiecare din aceste muchii nu formeaz ciclu cu muchia [A, C] i nici toate cele trei muchii nu formeaz ciclu, se alege a doua oar i a treia oar cte una din muchiile [D, E] i [D,F]. Muchiile [A, D] i [C, E] cu costul v[A, D] = v[C, E] = 5 u.m. pot fi alese, n continuare. Se alege una din muchii, cealalt formeaz un ciclu. Deci, pot exista dou variante conform figurilor 1.11.a) i 1.11.b) prin alegerea fie a muchiei [A, D] fie a muchiei [C, E].

Urmtoarea alegere este fie muchia [E, F] fie muchia [B, D] ambele avnd costul v[E, F] = v[B, D] = 6 u.m.. Dar, muchia [E, F] formeaz ciclu n ambii arbori pariali mpreun cu muchiile [D, E] i [D, F]. n acest caz, se alege muchia [B, D] n ambii arbori pariali.

Rezult dou soluii optime, deci doi arbori de valoare minim prezentai n figura 1.11, cu v(H1) = v(H2) = 22. Alegerea ntre aceti arbori va avea n vedere i alte considerente economice pe lng costul instalrii sistemului de telecomunicaii.

Exemplul 1.2: Problema modernizrii reelei de drumuri

Prefectura judeului X i-a fixat ca obiectiv modernizarea reelei drumurilor care leag localitile judeului conform grafului din figura 1.12. Pe fiecare muchie este nscris valoarea numeric n uniti monetare [u.m.] a costului modernizrii tronsonului respectiv. n prima etap se caut s se modernizeze numai unele drumuri astfel nct fiecare localitate s fie conectat la cel puin un drum modernizat i costul ntregii operaii de modernizare (parial) s fie minim.

B

A

C

D

E

F

6

7 5

3

7 4

5

4

6

Figura 1.10

B

A

C

D

E

F

6

5

3 4

4

Figura 1.11

B

A

C

D

E

F

6

3 4

5

4

b) H2 a) H1

1

2

4

3 8

5

7

6

5

3

8

6 1

3

2

3

10

4

8 2 10

7

7

Figura 1.12


8

Rezolvarea problemei se reduce la determinarea unui arbore maximal de valoare minim. TEM: Aplicai algoritmul Kruskal pentru determinarea variantei optime de modernizare a drumurilor.

1.4. Drumuri de valoare minim

1.4.1. Problema drumului de valoare minim

Fie G = (V, E) un graf finit (orientat, neorientat sau parial orientat).

Dac e E este o muchie cu extremitile xi i xj atunci aceast muchie are o orientare permis prin arcele (xi, xj) i (xj, xi). n acest mod, un graf neorientat este tratat ca graf orientat G = (V, U). n continuare, ne referim numai la grafuri orientate finite.

Dac arcul u este dat prin extremitile sale u = (xi, xj), cu xi, xj V, valoarea arcului va fi dat prin notaiile v(xi, xj) sau vij. Dac u este o muchie n graful G = (V, E) atunci v(u) = v(xi, xj) = v(xj, xi), deci pe

ambele sensuri arcele au aceeai valoare. Pe o muchie neorientat ji, putem avea ns i jivjiv ,, . Valorile asociate arcelor pot reprezenta n practic distanele ntre dou localiti, costurile executrii unei lucrri pe tronsoanele respective, costurile trecerii unei linii de fabricaie de la un produs la altul, timpii de execuie ai unor activiti, msura siguranei transmisiunii unui semnal, etc.

Pentru un drum ntre nodul xi X i nodul xj X, precizat prin specificarea arcelor componente, se definete valoarea drumului ca fiind suma valorilor arcelor componente:

v() = u

uv . (1.3)

Din noiunile introductive tim c un drum este o succesiune de arce permise:

= (u1, u2, ..., uq) , ui U

cu proprietatea c pentru orice 1 i q 1, extremitatea final a unui arc ui coincide cu extremitatea iniial

a arcului ui+1. Altfel spus, de-a lungul drumului arcele componente sunt orientate n acelai sens, de la nodul iniial al arcului u1 ctre nodul final al arcului uq. Numrul arcelor componente definete lungimea l()

a drumului . Drumurile de lungime 1 se identific cu arcele permise ale grafului. Dac u1 = (x0, x1), u2 = (x1, x2), ..., uq = (xq-1, xq) sunt arcele date prin extremitile lor, atunci un drum

poate fi definit i prin succesiunea de noduri:

= (x0, x1, x2, ..., xq) Nodul x0 este extremitatea de start a drumului iar nodul xq extremitatea final. Dac extremitile

sale coincid (x0 = xq) atunci drumul este un circuit. Un drum este elementar dac nodurile sale sunt distincte (drumul trece o singur dat prin fiecare nod

al su). Un drum este simplu dac arcele sale sunt distincte (drumul trece o singur dat prin fiecare arc al su). Evident, orice drum elementar este i simplu. Reciproca nu este, n general, adevrat. Mulimea

drumurilor elementare dintr-un graf finit este finit. Un drum dintr-un graf G este inclus n drumul ' ( ') dac toate arcele drumului sunt arce i ale drumului '. Evident, v() v(').

O problem extremal ntr-un graf orientat G = (V, U) const n determinarea unui drum elementar (sau a drumurilor elementare), ntre dou noduri date, de valoare minim (sau de valoare maxim).

Fie s i t dou noduri oarecare ale grafului G. Notm cu G*(s, t) un subgraf al grafului G format din mulimea drumurilor din graful considerat G = (V, U) ntre nodurile s i t, n care sunt incluse i drumurile de lungime 1. Problema drumurilor de valoare minim ntre nodurile s i t se definete ca problema determinrii

drumului * de la nodul s la nodul t n graful G*(s, t), de valoare minim:

v(*) = min{v() G*(s, t)}. (1.4)

CURSUL 2


9

Este posibil ca problema (1.4) s nu admit soluii optime (de exemplu n cazul existenei circuitelor de valoare negativ). n acest caz, exist o infinitate de drumuri de la s la t a cror mulime de valori poate fi nemrginit inferior. Un circuit n graful G de valoare strict negativ este numit circuit absorbant. Deoarece problemele de determinare a drumurilor de valoare minim ntre nodurile date se rezolv considernd toate drumurile posibile, nu numai cele elementare, vom presupune verificat urmtoarea condiie: n graful G nu exist circuite de valoare strict negativ.

Determinarea drumului de valoare minim poate avea loc ntr-un graf n care valorile sau ponderile arcelor sunt nenegative. n grafuri n care exist arce cu ponderi negative, sunt necesare eforturi mai mari pentru rezolvare; n acest caz se va presupune ndeplinit condiia: nu exist circuite de valoare strict negativ (absorbante).

Dac i ' sunt drumuri elementare n G avnd aceleai extremiti, atunci drumurile pot fi comparabile: fie v(') v(), fie v() v().

n cazul n care exist drumuri de la s la t, evaluarea i compararea acestora, conform afirmaiei anterioare, se poate limita la drumurile elementare cu aceleai extremiti. Numrul drumurilor elementare fiind finit unul dintre ele va fi drumul de la s la t de valoare minim.

Dac graful G nu este conex i nodurile s i t nu fac parte din aceeai component conex (figura 1.13.a) sau orientrile pe arce nu permit atingerea nodului t din nodul s (figura 1.13.b), exist posibilitatea ca n graful G s nu existe drumuri de la s la t.

n acest context vom spune c nodul i este atins din nodul s dac exist un drum de la s la i format din arce permise. Ne ocupm de rezolvarea problemei determinrii drumului de valoare minim de la s la toate

celelalte noduri ale grafului, sP , i a cazului su particular tsP , - determinarea drumului de valoare minim de la s la t, n ipoteza: toate valorile arcelor permise sunt nenegative: Uuuv ;0 .

1.4.2. Metoda Dijkstra)

1. Preliminarii

1) Fiecrui nod Vi i s-a asociat o variabil id numit n continuare eticheta nodului i. Prin definiie 0sd . n oricare moment al aplicrii algoritmului variabilei id reine valoarea unui drum de la

)

Dijkstra, E.W. A Note on two Problems in Connection with Graphs, Numerische Math. 1, 269-271, 1959

s

t

s t

Figura 1.13.a

Figura 1.13.b


10

s la i gsit de algoritm pn n acel moment. Dac algoritmul nu a gsit nc un drum de la s la i variabila

id are valoarea +. La finalul aplicrii metodei, eticheta indic valoarea celui mai scurt drum de la nodul s la nodul i. Pe parcursul aplicrii algoritmului etichetele se corecteaz n sensul micorrii valorilor

lor. n momentul n care o etichet id atinge valoarea minim ea devine permanent. 2) Fiecrui nod Vi diferit de s i se asociaz o alt variabil PRED i numit indicator de

preceden cu urmtoarea semnificaie: n oricare moment al aplicrii algoritmului, PRED i conine ultimul nod dinaintea lui i pe drumul de la s la i gsit de algoritm pn n acel moment. Atta timp ct un asemenea

drum nu a fost gsit id , indicatorul PRED i nu este definit el fiind o locaie vid (PRED(i) = ). 3) Iniializm o list P n care vom include toate nodurile Vi pentru care algoritmul a gsit un

drum de valoare minim de la i la s (lista nodurilor cu eticheta declarat permanent). La start P se reduce la nodul de plecare s.

4) Iniializm o list T n care vom include toate nodurile Vj care sunt vecine cu noduri din lista

P: un nod j este vecin cu i dac arcul ji, este permis. T este lista nodurilor cu eticheta declarat temporar.

Nodurile cu etichet permanent din lista P se selecteaz din lista T a nodurilor candidate. Corectarea unei etichete se face dup urmtoarea schem echivalent (figura 1.14).

Referitor la un arc permis Uji , cu valoarea 0, jiv presupunem c algoritmul a gsit un drum de la s la i a crui valoare e reinut n eticheta id i un drum de la s la j a crui valoare se gsete n locaia jd . Figura 1.14 pune n eviden cele dou drumuri de la s la j.

- drumul ji, de valoare jivid , ; - ,,vechiul drum de valoare jd . Dac jdjivid , atunci primul drum are o valoare mai mic i ca urmare va fi reinut de

algoritm ca fiind cel mai bun drum de la s la j gsit pn n acest moment. Memorarea acestui nou drum se

face prin corectarea etichetei jd care ia valoarea jividjd , i actualizarea indicatorului de preceden PRED (j): PRED (j) = i.

Cu aceste pregtiri trecem la prezentarea algoritmului Dijkstra.

2. Algoritmul Dijkstra

START: Iniializm:

Lista nodurilor cu eticheta permanent: sP ; Lista nodurilor cu eticheta temporar: ViT / exist arcul permis Uis , ; Etichetele: idsiTipentruisvidsd ,;0 n rest; Predecesorii: PRED Tipentrusi i PRED j nedefinit n rest.

ITERAIE: Pas 1: Dac lista T e vid, STOP: algoritmul a gsit toate nodurile ce pot fi atinse din s de-a lungul

unor drumuri de valoare minim, toate nodurile sunt n lista P i valorile minime ale drumurilor de la s la

i

s j

id

jiv ,

jd

Figura 1.14


11

aceste noduri sunt indicate de etichetele corespunztoare. Identificarea drumului de valoare minim se face cu ajutorul indicatorului de preceden, din aproape n aproape, de la t (sau de la fiecare nod al grafului) ctre s.

Dac T se trece la pasul 2.

Pas 2: Se selecteaz nodul Ti cu proprietatea: Tiidid ,min Se transfer nodul

i din lista T n lista P ( i devine nod cu eticheta permanent). Drumul de la s la i gsit pn n momentul selectrii este un drum de valoare minim. Se adaug la lista T toate nodurile

sVj care nu figurau n aceast list, noduri adiacente lui i pentru care exist arcul Uji , . Pas 3: Pentru fiecare nod Tj , vecin cu i se compar jd cu suma jivid ,)( * (vezi figura

1.14 cu i schimbat n i ). Situaii posibile:

Dac jdjivid , se trece la examinarea altui nod din T vecin cu i ; Dac jdjivid , se fac actualizrile:

jividjd , i PRED ij

dup care se trece la examinarea altui nod din lista T vecin cu i .

Dup examinarea tuturor vecinilor lui i din T se revine la Pasul 1 n cadrul unei noi iteraii.

STOP: Algoritmul se termin n urmtoarele situaii:

La Pasul 1: dac lista T e vid, T ; La Pasul 2: Dac ne intereseaz numai drumul de valoare minim de la s la un nod t algoritmul

descris se termin n momentul n care nodul selectat este t : i = t.

NOT:

1) Dac algoritmul se termin la Pasul 1 i d(t) = +, n graful G NU exist nici un drum de la s la t (vezi situaiile din figura 1.13).

2) Aplicarea Algoritmului Dijkstra nu rezolv doar problema gsirii drumului de valoare minim de la s la t ci a TUTUROR drumurilor de valoare minim de la s la toate celelalte noduri ale grafului G.

Exemplul 1.3. Aplicai metoda DISKTRA pentru a determina drumurile de valoare minim de la nodul s la nodurile ce pot fi atinse din s n graful din figura 1.15.

Figura 1.15

Fiecrei muchii i este asociat un cost valabil n ambele sensuri de parcurgere pe muchiile neorientate.

Rezolvare: Valorile iniiale i intermediare ale variabilelor id i PRED(i) sunt date n tabelul 1. START: Iniializm:

Listele sP , zyxT ,, idzdydxdsd ;3,8,4;0 n rest; PRED Tipentrusi i PRED j nedefinit n rest.

t

x y

z

s

w

3

3

3

4

8 2

2

1


12

Iteraia 1: Se calculeaz ziTiid 33,8,4min,min Transferm z din lista T n lista P: zsP , i includem n lista T nodul t care este vecin cu

tyxTzi ,,: . Examinm toi vecinii lui zi din lista T: exist un singur vecin, nodul t. Deoarece

tdtzvzd 633, actualizm 6td i PRED zt (valorile actualizate se trec n tabelul 1 n linia ITERAIA 1, celelalte valori nu se modific).

Iteraia 2: Se calculeaz xiTiid 46,8,4min,min Actualizm listele P i T: xzsP ,, , tyT , Observm c vecinii lui xi cu etichet nepermanent, adic y i t sunt deja n lista T.

Trecem la corectarea dac este cazul a etichetelor yd i td : ydyxvxd 8734, actualizm: 7yd i PRED xy tdtxvxd 6514, actualizm 5td i PRED xt .

Celelalte etichete i indicatori de preceden rmn neschimbai.

Iteraia 3: Calculm tiTiid 55,7,min . Actualizm yTtxzsP ;,,, .

ti nu are vecini cu etichet nepermanent, nici n T, nici n afara lui T. n aceast iteraie nu are loc nici o corectare de indicatori.

Iteraia 4: yi

TytxzsP ;,,,, yi nu are nici un vecin cu etichet nepermanent.

STOP, pentru c T . Tabelul 1

ITERAIA d(s) d(x) PRED(x) d(y) PRED (y)

d(z) PRED

(z)

d(t) PRED

(t)

d(w) PRED (w)

START 0* 4 s 8 s 3 s + - + - ITERAIA 1 - 4 s 8 s 3* s 6 z + - ITERAIA 2 - 4* s 7 x - - 5 x + - ITERAIA 3 - - - 7 x - - 5* x + - ITERAIA 4 - - - 7* x - - - - + -

STOP 0 4* s 7 x 3 s 5 x + -

Drumurile de valoare minim se construiesc cu ajutorul indicelui de preceden i sunt vizualizate n figura 1.16.

Figura 1.16

x y

z

s w

3

t

4

3

1 d(s) = 0

d(x) = 4

PRED(x) = s

d(z) = 3

PRED(z) = s

d(y) = 7

PRED(y) = x

d(t) = 5

PRED(t) = x

d(w) = +

PRED(w) =


13

Aa cum se observ, dei graful din figura 1.15 este conex, datorit orientrilor existente pe muchii, nodul w nu poate fi atins din s (nu se gsete n lista P). Lungimile drumurilor de valoare minim de la s la toate celelalte noduri ale grafului sunt date de etichetele fiecrui nod (de exemplu, valoarea celui mai scurt drum de la s la y este 7 i el trece prin nodul x PRED(y) = x iar PRED(x) = s).

Exemplul 1.4. Probleme propuse ca TEM:

1. n reeaua din figura 1.17, nodurile A, B, C, D, E i T reprezint puncte de atracie turistic din cadrul unei staiuni montane, muchiile reprezint traseele care fac posibil legtura dintre aceste puncte, iar valorile numerice nscrise pe muchii indic timpul necesar deplasrii, timpi valabili n ambele sensuri de parcurgere a traseelor. Aplicai riguros algoritmul lui Dijkstra pentru

determinarea drumurilor cel mai rapid de

parcurs de la nodul S - hotelul la care suntei cazai, la toate celelalte puncte de atracie turistic din staiune.

Figura 1.17

2. i) Utiliznd algoritmul lui Dijkstra determinai cele mai scurte drumuri de la nodul A la celelalte noduri ale grafului din figura 1.18.

ii) Ce modificri intervin n graful G*(A) al drumurilor de lungime minim dac muchiile {I, G} i {D, J} nu pot fi parcurse dect de la I la G, respectiv de la D la J?

Figura 1.18

3. Aplicai metoda DISKTRA pentru a determina drumurile de valoare minim de la nodul s la nodurile ce pot fi atinse de s din graful din figura 1.19.

s 2 3

6 7 8

4 5

4 3

4

5 6

1

0

6

3

5 2 1

4 7 2

9

Figura 1.19

A H

G

I J E

F

D C B

7 4 3 5 3 4

5

8 5 2

7

6 10

7

8 8

8

S

A

C

B

D T

E

5

4

5

7

6

1 6

2

1 4

5

tema 1-1_arbori minimali si drum minim in grafuri

Documents