MATEMATICI ECONOMICE SI FINANCIARE SEMESTRUL 2

ELEMENTE DE TEORIA GRAFURILOR1. Noiuni generale n general, pentru situaiile care necesit la rezolvare un oarecare efort mental (i un caz tipic este cel al celor din economie), se caut, n primul rnd, o metod de reprezentare a lor care s permit receptarea ntregii probleme dintr-o privire (pe ct posibil) i prin care s se evidenieze ct mai clar toate aspectele acesteia. n acest scop se folosesc imagini grafice gen diagrame, schie, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate n special pentru vizualizarea sistemelor i situaiilor complexe. n general, vom reprezenta componentele acestora prin puncte n plan iar relaiile (legturile, dependenele, influenele etc) dintre componente prin arce de curb cu extremitile n punctele corespunztoare. ntre dou puncte pot exista unul sau mai multe segmente (n funcie de cte relaii dintre acestea, care ne intereseaz, exist) iar segmentelor li se pot asocia sau nu orientri (dup cum se influeneaz cele dou componente ntre ele), numere care s exprime intensitatea relaiilor dintre componente etc. Definiia 1 Se numete (multi)graf un triplet G = (X, A, f) n care X i A sunt dou mulimi iar f este o funcie, definit pe produsul cartezian al lui X cu el nsui (X2 = XX), care ia valori n mulimea prilor mulimii A (notat P(A)) Mulimea X se numete mulimea nodurilor multigrafului i elementele sale se numesc noduri (sau vrfuri) ale multigrafului, iar A reprezint mulimea relaiilor (legturilor) posibile ntre dou noduri ale multigrafului. Definiia 2 Se numete graf orientat un multigraf n care mulimea A are un singur element: A = {a}. n acest caz mulimea prilor mulimii A are doar dou elemente: mulimea vid i ntreaga mulime A. Dac unei perechi orientate (xi, xj) din X2 i se asociaz prin funcia f mulimea 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 numete nod iniial sau extremitate iniial a arcului (xi,xj) iar nodul xj se numete nod final sau extremitate final a arcului (xi,xj). Arcul (xi,xj) este incident spre interior vrfului xj i incident spre exterior vrfului xi. Dac pentru un arc nodul iniial coincide cu nodul final atunci acesta se numete bucl. Nodurile xi i xj se vor numi adiacente dac exist cel puin unul din arcele (xi,xj) i (xj,xi). Dac unei perechi orientate (xi, xj) din X2 i se asociaz prin funcia f mulimea vid atunci spunem c nu exist arc de la nodul xi la nodul xj. Este evident c a cunoate un graf orientat este echivalent cu a cunoate vrfurile i arcele sale. Din acest motiv putem defini un graf orientat prin perechea (X,U), unde X este mulimea vrfurilor sale iar U mulimea arcelor sale. De asemenea, putem cunoate un graf orientat cunoscnd mulimea nodurilor i, pentru fiecare nod, mulimea arcelor incidente spre exterior. Din acest motiv putem defini un graf orientat ca o pereche (X,) unde X este perechea nodurilor iar este o funcie definit pe X cu valori n 1

mulimea prilor lui X, valoarea acesteia ntr-un nod xi, (xi) X fiind mulimea nodurilor adiacente nodului xi, prin arce pentru care xi este extremitatea iniial. Definiia 3 Se numete graf neorientat un multigraf n care mulimea A are un singur element iar funcia f are proprietatea: f[(xi,xj)] = f[(xj,xi)] , oricare ar fi nodurile xi i xj din X n aceste condiii, 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 vrfurile xi i xj. Deoarece, n cele mai multe din cazurile practice care vor fi analizate n acest capitol, situaia 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. 2. Moduri de reprezentare ale unui graf A. O prim modalitate de reprezentare este listarea efectiv a tuturor nodurilor i a arcelor sale. B. Putem reprezenta graful dnd pentru fiecare nod mulimea nodurilor cu care formeaz arce n care el este pe prima poziie. C. Putem reprezenta geometric graful, printr-un desen n plan, reprezentnd fiecare nod printr-un punct(cercule) i fiecare arc printr-un segment de curb care are ca extremiti nodurile arcului i pe care este trecut o sgeat orientat de la nodul iniial 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 plecnd sgei spre nodurile cu care formeaz arce n care el este pe prima poziie, de pe al doilea ir (reprezentarea prin coresponden). E. Un graf poate fi reprezentat printr-o matrice ptratic boolean, de dimensiune egal cu numrul de noduri, n care o poziie aij va fi 1 dac exist arcul (xi,xj) i 0 n caz contrar, numit matricea adiacenelor directe. F. Un graf poate fi reprezentat printr-o matrice ptratic latin, de dimensiune egal cu numrul de noduri, n care pe o poziie 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 reprezentri vom avea: B x1 x2 x3 x4 x5 x6 {x1, x2, x4, x5} {x3, x4, x6} {x1, x2} {x5} {x2} {x4} C x1 x6 x5 D (reprezentarea prin coresponden) x1 x2 x3 x4 x5 x6 x4 x2 x3

x1

x2

x3

x4

x5

x6 2

E

x1 x2 x3 x4 x5 x6

x1 1 0 1 0 0 0

x2 1 0 1 0 1 0

x3 0 1 0 0 0 0

x4 1 1 0 0 0 1

x5 1 0 0 1 0 0

x6 0 1 0 0 0 0

F

x1 x2 x3 x4 x5 x6 x1 x2 x3 x4 x5 x6x1x1 x1x2 0 x1x4 x1x5 0 0 0 x 2x 3 x 2x 4 0 x 2x 6 x3x1 x3x2 0 0 0 0 0 0 0 0 x4x5 0 0 x5x2 0 0 0 0 0 0 0 x 6x 4 0 0

3. Concepte de baz n teoria grafurilor 1. semigraf interior al unui nod xk: este mulimea arcelor U k = {(xj,xk)/ (xj,xk) U} care xsunt incidente spre interior nodului xk; 2. semigraf exterior al unui nod xk: este mulimea arcelor U + k = {(xk,xi)/ (xk,xi) U} care x sunt incidente spre exterior nodului xk; 3. semigradul interior al unui nod xk: este numrul arcelor care sunt incidente spre interior nodului xk = cardinalul lui U k i se noteaz cu x k ; x 4. semigradul exterior al unui nod xk: este numrul arcelor care sunt incidente spre + exterior nodului xk = cardinalul lui U + k i se noteaz cu x k ; x+ 5. gradul unui nod xk: este suma semigradelor nodului xk: x k = x k + x k ;

nod izolat: este un nod cu gradul 0; nod suspendat: este un nod cu gradul 1; arce adiacente: arce care au o extremitate comun; drum ntr-un graf: o mulime ordonat de noduri ale grafului: (x1, x2, ..., xk), cu proprietatea c exist n graf toate arcele de forma (xi,xi+1) i = 1,...,k-1; 10. lungimea unui drum: este numrul arcelor care l formeaz; 11. drum elementar: un drum n care fiecare nod apare o singur dat; 12. drum simplu: un drum n care fiecare arc apare o singur dat; 13. putere de atingere a unui nod xi X n graful G: numrul de noduri la care se poate ajunge din xi. Puterea de atingere se noteaz cu p(xi), 1 i n i evident p(xi) x+i .

6. 7. 8. 9.

14. drum hamiltonian: un drum elementar care trece prin toate nodurile grafului; 15. drum eulerian: un drum simplu care conine toate arcele grafului; 16. lan: un drum n care arcele nu au neaprat acelai sens de parcurgere; 17. circuit: un drum n care nodul iniial coincide cu cel final; 18. circuit elementar: un drum n care fiecare nod apare o singur dat, cu excepia celui final, care coincide cu cel iniial; 19. circuit simplu: un drum n care fiecare arc apare o singur dat; 20. circuit hamiltonian: un circuit care trece prin toate nodurile grafului; 21. ciclu: este un circuit n care arcele nu au neaprat acelai sens de parcurgere; 22. ciclu elementar: un ciclu n care fiecare nod apare o singur dat, cu excepia celui final, care coincide cu cel iniial; 23. ciclu simplu: un ciclu n care fiecare arc apare o singur dat;3

Observaie: ntr-un graf neorientat noiunile de drum i lan sunt echivalente i de asemenea cele de circuit i ciclu. 24. graf parial al unui graf G = (X,U): este un graf G'(X,U') cu U' U; 25. subgraf al unui graf G = (X,): este un graf G'(X',') unde X' X i '(xi) = (xi) X' pentru orice xi X'; 26. graf redus al unui graf G = (X,U): este un graf G*(X*,U*) unde X* este format din mulimile unei partiii de mulimi nevide ale lui X, iar ( X * , X * ) exist doar dac i j i j i

exist cel puin un arc n U, de la un nod din X * la un nod din X * . i j

27. graf tare conex: este un graf n care ntre oricare dou noduri exist cel puin un drum; 28. graf simplu conex: este un graf n care ntre oricare dou noduri exist cel puin un lan; Observaie: Pentru grafuri neorientat noiunile de tare conex i simplu conex sunt echivalente, graful numindu-se doar conex; 29. component tare conex a unui graf G = (X,U): este un subgraf al lui G care este tare conex i nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, ntre oricare dou noduri din component exist cel puin un drum i nu mai exist nici un nod n afara componentei legat printr-un drum de un nod al componentei).4. Gsirea drumurilor ntr-un graf orientat

Dac privim graful ca imagine a unui sistem, nodurile reprezentnd componentele sistemului, atunci o interpretare imediat a unui arc (xi,xj) este c, componenta xi influeneaz direct componenta xj. Dac nodurile au semnificaia de stri posibile ale unui sistem atunci un arc (xi,xj) semnific faptul c sistemul poate trece direct din starea xi n starea xj. n ambele cazuri se vede c avem de-a face doar cu informaii despre legturi directe; totui, chiar dac o component xi nu influeneaz direct componenta xj ea o poate influena prin intermediul altor componente, existnd un ir de componente intermediare: x1 x2 ,..., xk, fiecare influennd-o direct pe urmtoarea i xi direct pe x1 iar xk direct pe xj. Astfel, dac dintr-o stare xi nu se poate trece direct ntr-o stare xj s-ar putea totui n mai multe etape, prin alte stri intermediare. Deoarece gsirea acestor influene sau treceri posibile este de obicei foarte important iar pentru un sistem cu mii sau zeci de mii de componente acest lucru nu mai poate fi fcut "din ochi", este necesar formalizarea noiunii de "influene" i "treceri" posibile, nu neaprat directe. Acest lucru a i fost fcut mai sus, deoarece este evident c "xi influeneaz xj" sau "din starea xi se poate trece n starea xj" este echivalent cu existena n graf a unui drum de la nodul xi la nodul xj. n continuare vom da un algoritm prin care putem gsi toate drumurile dintr-un graf orientat cu un numr finit de noduri.Pasul 1. Se construiete matricea boolean a adiacenelor directe corespunztoare grafului, notat cu A. n aceasta se afl, evident, toate drumurile de lungime 1.

Este interesant de vzut ce legtur exist ntre aceast matrice i drumurile de lungime 2. Fie dou noduri xi i xj oarecare din graf. Existena unui drum de lungime 2 ntre ele presupune existena unui nod xk, din graf, cu proprietatea c exist att arcul (xi,xk) ct i arcul (xi,xk). Pentru a vedea dac acesta exist, lum pe rnd fiecare nod al grafului i verificm dac exist sau nu ambele arce ((xi,xk) i (xi,xk)). Aceasta este echivalent cu a verifica dac, n matricea boolean a adiacenelor directe, exist vreun indice k astfel nct elementul k al liniei i i elementul k al coloanei j s fie ambele egale cu 1. Dac folosim operaiile algebrei booleene de adunare i nmulire: & & 0 1 0 1 + 0 0 1 0 0 0 1 1 1 1 0 14

atunci verificrile de mai sus sunt echivalente cu a verifica dac elementul de pe poziia (i,j) din A2 este egal cu 1. Valoarea 1 spune doar c exist cel puin un drum de lungime 2 de la xi la xj. Dac dorim s vedem i cte sunt, vom folosi regulile de nmulire i adunare obinuit. De asemenea, se poate observa c existena unui drum de lungime 3 de la xi la xj presupune existena unui nod xk astfel nct s existe un drum de lungime 2 de la xi la xk i un arc de la xk la xj, care este echivalent cu a verifica dac exist vreun indice k astfel nct elementul k al liniei i din matricea A2 i elementul k al coloanei j din A sunt ambele egale cu 1 sau, mai simplu, dac elementul (i,j) din A3 este 1. Din cele de mai sus se observ c existena drumurilor de lungime k este dat de valorile matricei Ak, dac s-au folosit regulile algebrei booleene i numrul lor este dat de Ak, dac s-au folosit regulile obinuite.Pasul 2. Vom calcula succesiv puterile lui A pn la puterea An-1

Dac ntre nodurile xi i xj exist un drum de lungime n atunci el va conine un numr de noduri mai mare sau egal nu n+1 i, cum n graf sunt doar n vrfuri, este clar c cel puin unul, s zicem xk, va aprea de dou ori. Vom avea n acest caz un drum de la xi pn la prima apariie a lui xk, i un drum de la ultima apariie a lui xk la xj. Eliminnd toate nodurile dintre prima apariie a lui xk i ultima apariie a sa vom obine un drum de la xi la xj, n care xk apare o singur dat. Aplicnd acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obine un drum de la xi la xj, n care fiecare nod apare o singur dat (deci un drum elementar), care are evident cel mult n-1 arce. n concluzie, dac exist vreun drum de la xi la xj atunci exist i un drum elementar i, deci, va exista o putere a lui A, ntre A1 i An-1, n care poziia (i,j) este diferit de 0. Pentru deciderea existenei unui drum ntre oricare dou noduri este suficient, deci, calcularea doar a primelor n-1 puteri ale lui A.Pasul 3. Se calculeaz matricea D = A + A2 + ... + An-1

Dac ne intereseaz doar existena drumurilor dintre noduri, nu i numrul lor, vom folosi nmulirea i adunarea boolean i conform observaiei de mai sus:( ( 1 daca exista cel putin un drum de x i la x j dij = ( ( 0 daca nu exista nici un drum de x i la x j

n acest caz, observnd c: A(A + I)n2 = C 0 2 A + C 1 2 A2 + C 2 2 A3 + ... + C n 2 An1 = A + A2 + A3 + ... + An-1 = D n n n n 2 rezult c e suficient s calculm doar puterea n-2 a matricei A + I i apoi s-o nmulim cu A. Avantajul acestei metode, n ceea ce privete economia de timp, este susinut i de urmtoarea observaie: dac D conine toate perechile de arce ntre care exist drum atunci: D = (A + A2 + ... + An-1) + An + An+1 + ... + An+k = D oricare ar fi k 0 A(A + I)n2+k = (A + A2 + ... + An-1) + An + An+1 + ... + An+k-1 = D = A(A + I)n2 A(A + I)n2+k = A(A + I)n2 oricare ar fi k 0 deci de la puterea k = n-2 toate matricile Ak sunt egale. Putem, deci, calcula direct orice putere a lui A+I mai mare sau egal cu n-1 (de exemplu calculnd (A+I)2, (A+I)4, (A+I)8, ..., (A + I) 2 , r fiind prima putere a lui 2 pentru care 2r n-2). 5r

Procedeul de mai sus nu asigur dect aflarea faptului dac exist sau nu drum ntre dou noduri, eventual ce lungime are i cte sunt de aceast lungime. Totui, n problemele practice cel mai important este s tim care sunt efectiv aceste drumuri. Deoarece toate drumurile pot fi descompuse n drumuri elementare i n problemele practice n general acestea sunt cele care intereseaz, paii urmtori ai algoritmului vor fi dedicai gsirii lor. Pentru gsirea acestora se folosete reprezentarea grafului prin matricea latin de la cazul F.Pasul 4. Construim matricea latin L asociat grafului, unde:

( ( ~ x j daca exista arcul (x i , x j ) lij = ( ( 0 daca nu exista arcul (x i , x j ) numit matricea latin redus. Gsirea unui drum de lungime 2 de la xi la xj presupune gsirea unui nod cu proprietatea c exist arcele (xi,xk) i (xk,xj) i memorarea vectorului (xi, xk, xj). Aceasta este echivalent cu a gsi un indice k astfel nct elementul de pe poziia k a liniei i, din matricea L, s fie xi,xk i elementul ~ ~ de pe poziia k al coloanei j, din matricea L , s fie xj. Vom nmuli deci matricea L cu matricea L , folosind ns nite reguli de calcul speciale, numite nmulire i adunare latin.Definiia 1: Se numete alfabet o mulime de semne numite simboluri sau litere {si/iI} unde I este o mulime oarecare de indici, finit sau nu. Definiia 2: Se numete cuvnt un ir finit de simboluri notat s i1 s i 2 ...s i n . Definiia 3: Se numete nmulire latin o operaie definit pe mulimea cuvintelor unui alfabet, notat " L ", astfel: s i1 s i 2 ...s i n L s j1 s j2 ...s jm = s i1 s i 2 ...s i n s j1 s j2 ...s jm

~ i matricea L , definit prin:

x x lij = i j 0

( ( daca exista arcul (x i , x j ) ( ( daca nu exista arcul (x i , x j )

(produsul a dou cuvinte se obine prin concatenarea lor) nmulirea latin este asociativ, are ca element neutru cuvntul vid, nu e comutativ i un element este inversabil doar dac este cuvntul vid. Definiia 3: Se numete adunare latin o funcie definit pe mulimea cuvintelor unui alfabet cu valori n mulimea parilor mulimi cuvintelor, notat " + L " astfel: s s ...s s i1 s i 2 ...s i n + L s j1 s j2 ...s jm = i1 i 2 i n s j1 s j2 ...s jm (suma a dou cuvinte este mulimea format din cele dou cuvinte)Pasul 5. Se calculeaz succesiv matricile:

~ ~ L2 = L L L , L3 = L2 L L , ...

~ ,Lk+1 = Lk L L

folosind operaiile de nmulire i adunare latin, alfabetul fiind mulimea nodurilor grafului, unde operaia de nmulire este uor modificat, produsul dintre dou elemente ale matricilor fiind 0, dac unul dintre ele este 0 sau au un nod comun i este produsul latin al lor, n caz contrar. Din felul cum a fost construit, matricea Lk va conine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (cte are graful cu totul) rezult c: primele n-1 puteri ale lui L conin toate drumurile elementare din graf; puterile lui L mai mari sau egale cu n au toate elementele egale cu 0; 6

matricea Ln-1 conine toate drumurile hamiltoniene din graf (dac exist).Observaie: Deoarece obinerea matricii D prin metoda de mai sus presupune un volum foarte mare de calcule (de exemplu, dac graful are 100 de noduri, ridicarea unei matrici de 100100 la puterea 100) pentru obinerea acesteia se poate aplica i urmtorul algoritm: Pas 1. Se construiete matricea de adiacen A; Pas 2. Pentru fiecare linie i se adun boolean la aceasta toate liniile j pentru care aij = 1. Pas 3. Se reia pasul 2 pn cnd, dup o aplicare a acestuia, matricea rmne aceeai (nu mai apare nici un 1) Ultima matrice obinut este matricea drumurilor D numit i matricea conexiunilor totale. Aceast metod, dei mai simpl nu spune ns i care sunt aceste drumuri, pentru gsirea lor aplicndu-se, de exemplu, nmulirea latin 5. ARBORI. Problema arborelui de valoare optim

n acest subcapitol grafurile vor fi considerate neorientate.5.1. Noiunea de arbore

Un arbore este un graf neorientat, finit, conex i fr cicluri. Grafurile din fig. 4.1. sunt arbori. x1 x1 x1 a) x1 b) Figura 4.1 Studiul arborilor este justificat de existena n practic a unui numr mare de probleme care pot fi modelate prin arbori. Dintre acestea amintim: 1. construirea unor reele de aprovizionare cu ap potabil (sau cu energie electric sau termic etc) a unor puncte de consum, de la un punct central; 2. construirea unor ci de acces ntre mai multe puncte izolate; 3. desfurarea unui joc strategic; 4. luarea deciziilor n mai multe etape (arbori decizionali); 5. evoluii posibile ale unui sistem pornind de la o stare iniial; 6. construirea unei reele telefonice radiale, a unei reele de relee electrice; 7. legarea ntr-o reea a unui numr mare de calculatoare; 8. organigramele ntreprinderilor; 9. studiul circuitelor electrice n electrotehnic (grafe de fluen etc); 10. schemele bloc ale programelor pentru calculatoare etc. 7 x1 x1 c) x1 x1 x1 x1 x1

n toate problemele de mai sus se dorete ca, dintre muchiile unui graf neorientat, s se extrag arborele optim din mulimea tuturor arborilor care pot fi extrai din graful dat. Deoarece definiia arborelui este dificil de aplicat pentru deciderea faptului c un graf este arbore sau nu (i n special sunt greu de verificat conexitatea i mai ales existena ciclurilor) exist mai multe caracterizri posibile ale unui arbore, acestea fiind date de teorema de mai jos:Teorem. Dac H este un graf neorientat finit, atunci urmtoarele afirmaii sunt echivalente:

1) H este arbore; 2) H nu conine cicluri i, dac se unesc printr-o muchie dou noduri neadiacente, se formeaz un ciclu (i numai unul). Arborele este, deci, pentru o mulime de noduri dat, graful cu numrul maxim de arce astfel nct s se pstreze proprietatea c nu are cicluri); 3) H este conex i dac i se suprim o muchie se creeaz dou componente conexe (arborele este graful conex cu numrul minim de arce); 4) H este conex i are n-1 muchii; 5) H este fr cicluri i are n-1 muchii; 6) Orice pereche de noduri este legat printr-un lan i numai unul.

5.2. Algoritmi pentru gsirea arborelui de valoare optim

Vom da mai jos trei algoritmi pentru determinarea unui graf parial al grafului, care s fie arbore i pentru care suma valorilor arcelor sale s fie minim (sau maxim). Toi algoritmii descrii n continuare extrag arborele prin colectarea una cte una a muchiilor acestuia.A. Algoritmul lui Kruskal Pasul 1. Dintre toate muchiile grafului se alege muchia de valoare minim (maxim). Dac minimul este multiplu se alege la ntmplare una din muchiile respective. Deoarece acest "la ntmplare" trebuie cumva tradus n limbajul calculatorului, n cazul implementrii unui program bazat pe acest algoritm, vom perturba din start valorile muchiilor, la k muchii cu aceiai valoare V adunnd respectiv valorile , 2, ... , k, unde este foarte mic (n orice caz, k mai mic dect diferena dintre valoarea acestor arce si valoarea imediat superioar a unui arc), pozitiv. Pasul 2. Dintre toate muchiile rmase, se alege cea de valoare minim (maxim); Pasul 3. Dintre toate muchiile rmase, se alege cea de valoare minim (maxim), astfel nct s nu se formeze cicluri cu cele deja alese; Pasul 4. Se reia algoritmul de la pasul 3 pn se colecteaz n-1 muchii.

Dei s-a demonstrat c algoritmul gsete ntotdeauna arborele optim, el are dezavantajul c este foarte laborios (de fiecare dat trebuie calculat minimul unei mulimi mari sau foarte mari exist situaii n practic n care graful are sute de mii de arce) i, n plus, trebuie aplicat un algoritm special ca s respectm condiia de a nu se forma cicluri, la alegerea unui nou arc. O metod posibil este ca, dup adugarea fiecrui arc, s se mpart graful n componente conexe i s alegem apoi un arc care nu are ambele extremitile n aceeai component conex. De asemenea este clar c, n cazul existenei arcelor de valori egale, deoarece se alege la ntmplare, exist mai multe variante de evoluie a alegerii arcelor. Totui, cu toate c pot fi mai multe grafuri la care se poate ajunge prin acest algoritm, ele vor avea toate aceeai valoare (minima (sau maxima) posibil). 8

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 pn n acest moment, se alege cea de valoare minim (maxim); Pasul 3. Se reia pasul 2 pn se colecioneaz n-1 muchii.

Algoritmul are toate avantajele algoritmului lui Sollin i, n plus, lucreaz cu o singur component conex, fiind mult mai uor de implementat pe calculator i mult mai rapid n execuie. Exemplu: Administraia unei localiti montane a hotrt construirea unor linii de teleferic care s lege oraul de cele 8 puncte turistice importante din jurul acestuia. n urma unui studiu au fost puse n evidena toate posibilitile i costurile de conectare a obiectivele turistice ntre ele i cu oraul, acestea fiind prezentate n figura 4.2. Se cere gsirea variantei de construcie de cost minim, care s asigure accesul din ora la oricare din obiectivele turistice. P2 4 P1 3 P6 5 8 5 3 O 2 P7 Figura 4.2Rezolvare

7 8 2

9 P3 7 9 3 P5 6 8 7 P8 8 4 8 P4

Condiia de cost minim implic dou obiective: 1. S se construiasc minimul de arce necesare; 2. S se construiasc cele mai ieftine legturi. Referitor la numrul de arce necesar, facem observaia c, dac din ora se va putea ajunge la orice obiectiv turistic, atunci se va putea ajunge i de la orice staiune la oricare alta (trecnd prin ora), deci trebuie ca arcele alese pentru construcie s formeze la un loc un graf conex. n concluzie, cutm un graf parial conex cu un numr minim de arce, adic un arbore. n plus, suma costurilor arcelor sale trebuie s fie minim. Vom aplica pe rnd cei trei algoritmi pentru gsirea acestuia:A. Kruskal

La primul pas poate fi ales unul din arcele OP3 sau OP7, ele avnd valoarea minim 2. Putem alege oricum primul arc dintre cele dou pentru c la al doilea pas va fi ales cellalt. 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 fr a se forma nici un ciclu. 9

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, fr a se forma nici un ciclu. Urmtoarea valoare disponibil a unui arc este 5, dar arcul opt nu poate fi ales dintre arcele OP1, P6P7, dei au valoarea minim 5. Arcul OP1 nu poate fi ales deoarece s-ar forma ciclul OP1P6, iar P6P7 ar duce la ciclul OP6P7. Urmtoarea valoare minim este 6, pentru arcul P5P7 dar nu poate fi ales deoarece se formeaz ciclul OP5P7. Valoarea urmtoare, 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 obinut graful cutat. Acest arbore este reprezentat n figura 4.3. P2 4 P1 2 3 3 P6 O 2 P7 Figura 4.3B. Sollin

P3 P4 4 3 P5 7 P8

Vom alege:

pentru nodul O pentru nodul P1 pentru nodul P2 pentru nodul P3 pentru nodul P4 pentru nodul P5 pentru nodul P6 pentru nodul P7 pentru nodul P8

arcul OP3 arcul P1P6 arcul P1P2 arcul OP3 arcul P4P5 arcul OP5 arcul P1P6 arcul OP7 arcul P5P8

Rezult graful parial: P2 4 P1 2 3 P6 O 2 P7 Figura 4.4 10 4 3 P5 7 P8 P3 P4

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 obinem o singur component conex, care este arborele cutat.

C. Varianta algoritmului lui Kruskal

Succesiunea alegerii arcelor va fi: 1 2 3 4 5 6 7 8

OP3 OP7 OP6 OP5 P1P6 P1P2 P4P5 P5P8

6. Drumuri i circuite hamiltonieneUna dintre cele mai cunoscute probleme economice este problema comis voiajorului. Comis voiajorul este un individ care trebuie s prezinte sau s distribuie marfa comandat la o serie de centre distribuite n general neliniar pe o anumit zon teritorial (localitile dintr-un jude, magazinele dintr-un cartier, persoanele dintr-un sat etc). Dac numrul de obiective care trebuie vizitate este mare sau foarte mare iar timpul disponibil foarte limitat atunci devine vital o asemenea organizare a trecerii pe la fiecare obiectiv nct s se efectueze n timpul minim posibil. Acest timp minim se traduce prin drumul cel mai scurt, iar cel mai scurt drum este evident cel n care se trece pe la fiecare obiectiv o singur dat. n plus, la sfrit trebuie s se afle n punctul iniial, adic sediul firmei la care lucreaz. O reprezentare a regiunii aprovizionate, n care centrele pe la care se trece sunt vizualizate prin puncte iar cile de acces la acestea prin segmente de curbe, va fi evident un graf, problema reducndu-se la a gsi circuitul hamiltonian de lungime minim. n timp, s-au evideniat o multitudine de probleme reductibile la gsirea unui drum (sau circuit) hamiltonian ntr-un graf, cum ar fi: 1. Problema potaului (gsirea traseului cel mai scurt care trece pe la toate locuinele ce aparin de oficiul potal la care lucreaz acesta); 2. Problema adunrii deeurilor (cel mai scurt drum care trece pe la toate punctele de depozitate a deeurilor);

11

3. Problema succesiunii operaiilor (executarea mai multor operaii pe o main n acea ordine n care suma timpilor consumai cu pregtirea mainii pentru trecerea de la o operaie la urmtoarea s fie minim) 4. Ordinea lipirii unor componente electronice pe o plac, etc;

Determinarea drumurilor hamiltonieneProblema determinrii drumului (circuitului) hamiltonian de valoare optim s-a dovedit deosebit de dificil, neexistnd nici acum un algoritm care s rezolve problema n timp polinomial i nici mcar o metod simpl prin care s se decid dac ntr-un graf dat exist sau nu drumuri hamiltoniene. Exist ns mai muli algoritmi, unii exaci alii heuristici, care reuesc, ntr-un caz sau altul, s rezolve problema satisfctor i n timp util.

A. Algoritmul lui FoulkesPasul 1. Se scrie matricea boolean A asociat grafului G. Pasul 2. Se determin matricea D a drumurilor grafului G prin procedeul expus la nceputul capitolului i apoi matricea M = I + D. Pasul 3. Se mparte mulimea nodurilor grafului n submulimi disjuncte astfel:

1. Se consider n matricea M liniile pline (cu toate elementele 1). Nodurile ce corespund liniilor pline cu 1 formeaz submulimea C1. 2. Se elimin liniile i coloanele care corespund nodurilor din submulimea stabilit. 3. Se reia raionamentul de la punctul 1 pe matricea redus obinut la punctul 2 obinndu-se urmtoarea submulime i n continuare toate celelalte pn se epuizeaz toate liniile matricei.Pasul 4. Se construiete graful G' n care:

1. Nodurile care formeaz o submulime sunt reprezentate prin puncte n interiorul unui dreptunghi i ntre acestea se traseaz arcele existente n graful iniial G. 2. Se traseaz legturile dintre submulimi. Ele sunt reprezentate prin arcele existente n graful iniial G ntre nodurile submulimii C1 i cele ale submulimii C2, ntre nodurile submulimii C2 i cele ale submulimii C3 etc.Pasul 5. Se gsesc drumurile hamiltoniene

Un drum hamiltonian se gsete plecnd de la un vrf din submulimea C1, trecnd prin toate vrfurile acesteia cu un drum hamiltonian, din ultimul vrf la care se ajunge n C1 trecnd la un vrf din C2, parcurgnd n continuare un drum hamiltonian n a doua submulime i tot aa, trecnd prin toate submulimile i parcurgnd, deci, toate nodurile grafului iniial, o singur dat. Aplicnd acest procedeu n toate modurile posibile se obin toate drumurile hamiltoniene din graful iniial G. (Observaie: poate s nu existe nici un drum hamiltonian n graful G, caz n care algoritmul se oprete deoarece la un anumit pas nu mai exista nici o linie plina cu 1).Observaie. Algoritmul lui Foulkes reduce gsirea drumurilor hamiltoniene n graful iniial G (care n problemele practice este foarte mare) la gsirea mai multor drumuri hamiltoniene mai mici n componente tare conexe ale grafului. Dac un graf are o singur component tare conex,

12

algoritmul lui Foulkes nu este eficient, n acest caz trebuind aplicai ali algoritmi cum ar fi cel bazat pe nmulirea latin.

B. Algoritmul lui Chen pentru determinarea drumurilor hamiltoniene n grafuri fr circuiteFie G = (X,U) un graf orientat fr circuite, cu n noduri: X = {x1, x2, , xn}. Vom considera c am calculat matricea drumurilor D i puterile de atingere ale tuturor nodurilor. Dac n graful G exist un drum de la nodul xi la nodul xj atunci evident p(xi) > p(xj), deoarece n orice vrf n care se poate ajunge din xj se poate ajunge i din xi dar din xj nu se poate ajunge n xj pentru c nu exist circuite.Teorema 2.3 (Chen) Un graf cu n noduri, fr circuite conine un drum hamiltonian dac i numai dac exist relaia:

p(x i ) =i =1

n

n (n 1) 2

Teorema 2.4 Dac ntr-un graf orientat fr circuite exist un drum hamiltonian atunci acesta este unic.

Pe aceste teoreme se bazeaz algoritmul lui Chen de determinare a drumului hamiltonian ntr-un graf orientat fr circuite:Pasul1. Se scrie matricea de adiacen A Pasul2. Se calculeaz matricea drumurilor D Pasul3. Dac exist un indice i cu dii = 1 atunci graful are circuite, nu se poate aplica algoritmul lui Chen i algoritmul se oprete. Dac nu, se trece la pasul 4. Pasul4. Se calculeaz puterile de atingere pentru fiecare nod. Pasul5. Dac nu se verific relaia

p(x i ) =i =1

n

n (n 1) atunci graful nu are drumuri hamiltoniene 2

i algoritmul se oprete, altfel se trece la pasul 6. Pasul6. Se ordoneaz nodurile n ordinea descresctoare a puterilor lor de atingere i obinem drumul hamiltonian cutat.

C. Algoritmul lui KaufmannPasul 1. Construim matricea latin L asociat grafului, unde:

( ( x i x j daca exista arcul (x i , x j ) lij = ( ( daca nu exista arcul (x i , x j ) 0 ~ Pasul 2. Construim matricea L , definit prin: ( ( ~ x j daca exista arcul (x i , x j ) lij = ( ( 0 daca nu exista arcul (x i , x j )numit matricea latin redus.

13

Pasul 3. Se calculeaz succesiv matricile:~ ~ ~ L2 = L L L , L3 = L2 L L , ..., Lk+1 = Lk L L , ... folosind operaiile de nmulire i adunare latin, alfabetul fiind mulimea nodurilor grafului, unde operaia de nmulire este uor modificat, produsul dintre dou elemente ale matricilor fiind 0, dac unul dintre ele este 0 sau au un nod comun, i este produsul latin al lor, n caz contrar. Din felul cum a fost construit, matricea Lk va conine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (cte are graful cu totul) rezult c: primele n-1 puteri ale L conin toate drumurile elementare din graf; puterile lui L mai mari sau egale cu n au toate elementele egale cu 0; matricea Ln-1 conine toate drumurile hamiltoniene din graf.

Pasul 4. Dac se doresc i circuitele atunci se verific pentru fiecare drum hamiltonian dac poate fi completat pn la un circuit (adic dac exist n graf arcul care unete nodul final cu cel iniial); Pasul 5. Dac se dorete i drumul (sau circuitul) de valoare optim (maxim sau minim) se calculeaz suma valorilor pentru fiecare drum i/sau circuit i se alege cel cu valoarea optim.n concluzie, metoda nmulirii latine (A. Kaufmann J. Melgrange) determin toate drumurile elementare din graf, prin calcularea matricelor M(1), M(2), M(3), , M(n-1). n matricea M(n-1) se citesc drumurile hamiltoniene. Aceast metod a nmulirii latine (algoritmul lui Kaufmann) este util, mai ales, n cazul grafurilor tare conexe, unde algoritmul lui Foulkes nu este eficient. Totui, metoda este greu de aplicat n grafuri cu un numr mare de noduri. n acest caz este preferabil s se construiasc graful condensat, s se determine drumurile hamiltoniene n fiecare n parte cu algoritmul lui Kaufmann i apoi, ca la algoritmul lui Foulkes, s se caute drumurile hamiltoniene n graful iniial.

7. Drumuri optime ntr-un grafn marea majoritate a problemelor care pot fi modelate prin grafuri nu ne intereseaz numai dac exist sau nu legturi ntre componentele reprezentate prin nodurile grafului ci i intensitatea acestora. Aceast intensitate are semnificaia unei valori numerice (pozitive sau negative) asociate arcului corespunztor legturii a crei intensitate o msoar. n aplicaiile economice aceast valoare poate fi: lungimea drumului dintre dou localiti; costul parcurgerii rutei reprezentate prin arcul corespunztor; durata parcurgerii rutei respective; cantitatea transportat pe ruta respectiv; capacitatea maxim a rutei respective; ctigul realizat prin trecerea de la o stare la alta a sistemului; consum de energie pentru efectuarea trecerii respective; punctaj realizat etc.

14

Una din problemele care poate aprea n aceste situaii este gsirea, pentru o anumit pereche de noduri (sau mai multe perechi), a drumului optim ntre acestea. Pentru formalizarea problemei vom introduce noiunea de valoare a unui drum, care este egal cu suma valorilor arcelor care l compun. Vom nota n continuare valoarea unui arc (xi,xj) cu v(xi,xj) sau cu vij. n aceste condiii putem enuna problema drumului optim astfel: "Dat fiind un graf G = (X,U) i o funcie care asociaz fiecrui arc o valoare real, s se gseasc, pentru o pereche dat de noduri, drumul (drumurile) de valoare optim (minim sau/i maxim) ntre cele dou noduri i valoarea acestuia (acestora)" Deoarece este vorba de gsirea minimului unei mulimi de numere reale, prima ntrebare care se pune este dac aceasta admite minim. Dac mulimea nodurilor grafului este infinit atunci pot exista o infinitate de drumuri elementare distincte ntre cele dou noduri i mulimea valorilor acestora poate avea orice form (nchis sau nu, mrginit sau nu) devenind foarte greu de caracterizat cazurile cnd minimul dorit exist. Deoarece totui majoritatea covritoare a problemelor economice se modeleaz prin grafuri cu numr finit de noduri, ne vom limita n continuare doar la acestea. Un numr finit de noduri n atrage dup sine existena unui numr finit de arce (cel mult n2) i a unui numr finit de drumuri elementare ( cel mult nn!

k! ). Deoarece oricrui drum d i1k =1

n -1

corespunde un drum elementar de (obinut prin eliminarea tuturor subcircuitelor lui d) putem calcula valoarea oricrui drum ca sum ntre valoarea drumului elementar corespunztor i valorile unor subcircuite ale sale, fiecare nmulit cu numrul de parcurgeri ale circuitului respectiv. n concluzie, dac exist un circuit de valoare negativ nseamn c exist drumuri de valoare orict de mic (cele care conin acest circuit), obinut prin parcurgerea acestuia de oricte ori dorim) i, deci, mulimea valorilor drumurilor este nemrginit inferior, neexistnd drum de valoare minim. Dac exist un circuit de valoare pozitiv atunci exist drumuri de valoare orict de mare i mulimea valorilor drumurilor este nemrginit superior, neexistnd drum de valoare maxim. Dac nu exist circuite de valoare negativ atunci valoarea oricrui drum este mai mare sau egal cu a drumului elementar corespunztor, deci drumul de valoare minim (dac exist) va fi un drum elementar. Cum mulimea drumurilor elementare este finit (i deci i mulimea valorilor lor) va avea minorant i am lmurit problema compatibilitii problemei. Analog, dac nu exist circuite de valoare pozitiv atunci valoarea oricrui drum este mai mic sau egal cu a drumului elementar corespunztor, deci drumul de valoare maxim (dac exist) va fi un drum elementar. Cum mulimea drumurilor elementare este finit (i deci i mulimea valorilor lor), va avea majorant. Obs. 1. Dac n graf nu exist dect arce de valoare pozitiv atunci exist drum de valoare minim. Obs. 1. Dac n graf nu exist dect arce de valoare negativ atunci exist drum de valoare maxim. Obs. 1. Dac n graf nu exist circuite atunci exist i drum de valoare minim i drum de valoare maxim. Deoarece din cele de mai sus se sesizeaz importana existenei circuitelor ntr-un graf vom da n continuare un algoritm de depistare a existenei circuitelor ntr-un graf:

Pasul 1. Se construiete mulimea A format din nodurile pentru care toate arcele incidente sunt incidente spre interior ( noduri n care toate arcele "intr" sau, altfel spus, noduri din care nu "pleac" nici un arc). Pasul 2. Se gsesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealalt extremitate n A (noduri din care se poate "ajunge" doar in A). Dac nu exist nici un astfel de arc se trece la pasul 4.15

Pasul 3. Se adaug arcele gsite la pasul 2 la mulimea A apoi se reia algoritmul de la pasul 2, pentru noua mulime A. Pasul 4. Dac A conine mulimea tuturor nodurilor atunci graful nu conine circuite. Dac au rmas noduri n afara lui A atunci graful conine circuite.

Algoritmi de gsire a drumului optimDin cauza varietii nelimitate a grafurilor posibile, nu exist un algoritm care s rezolve orice problem n timp util, dar s-au elaborat o mulime de algoritmi, fiecare fiind cel mai eficace n anumite cazuri. Aceti algoritmi pot fi grupai n cinci categorii: 1. 2. 3. 4. 5. Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell); Algoritmi prin ajustri succesive: (Ford); Algoritmi prin inducie (Dantzig); Algoritmi prin ordonare prealabil a vrfurilor grafului; Algoritmi prin extindere selectiv (Dijkstra).

n continuare vom prezenta trei dintre aceti algoritmi.

A. Algoritmul lui Bellman - KalabaAlgoritmul 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 gsete drumurile de valoare minim (maxim) de la toate nodurile grafului la un nod oarecare, fixat. Dac dorim s cunoatem drumurile de valoare minim (maxim) ntre oricare dou noduri vom aplica algoritmul, pe rnd, pentru fiecare nod al grafului. Fie G = {x1, x2, ... ,xn} un graf orientat finit. Presupunem (fr a restrnge generalitatea, c am numerotat nodurile astfel nct nodul spre care cutm drumurile de valoare minim (maxim) de la celelalte noduri s fie xn.

Pasul 1. Se construiete matricea ptratic M cu dimensiunea egal cu numrul de noduri ale grafului ale crei elemente sunt: daca exista arcul (x i , x j ) si i j valoarea arcului (x i , x j ) mij = 0 daca i = j + (ntr - o problema de minim) daca nu exista arcul (x , x ) i j (ntr - o problema de maxim) Pasul 2. Se adaug succesiv liniile Li la matricea M, elementele acestora calculndu-se prin relaiile de recuren: 1. L1j = mjn j = 1,...,n (prima linie este ultima coloan, transpus, a matricii M) 2. Lij = min (Li-1,j , min (mjk + Li-1,k)) ntr-o problem de minimk =1, n

sau Lij = max (Li-1,j , max (mjk + Li-1,k)) ntr-o problem de maximk =1, n

Pasul 3. Dup calcularea fiecrei linii noi se compar elementele ei cu cele ale precedentei: Dac Lij = Li-1,j pentru orice j = 1,...,n atunci se oprete recurena i ultima linie calculat conine valorile minime ale drumurilor de la celelalte noduri la nodul xn. 16

Dac exist cel puin un indice j cu Lij Li-1,j se trece la calcularea noii linii Li+1

Pasul 4. Pentru gsirea drumului care d valoarea minim de la un nod xj la nodul xn se gsesc, ncepnd napoi de la ultima linie, pe care s-au obinut valorile finale, notat Lf, nodurile x k1 , x k 2 , ..., x k r care formeaz drumul cutat, unde x k1 = xj, x k r = xn i fiecare alt indice

ki+1 este cel pentru care s-a obinut minimul(maximul) de pe poziia ki al liniei Li.Observaie: Pentru grafuri foarte mari, algoritmul necesit un volum mare de memorie, prin necesitatea memorrii matricei M, care este greu de manipulat. Chiar dac din cele n2 arce posibile graful ar avea doar un procent foarte mic matricea grafului va avea tot n2 poziii de memorat i analizat. Exemplu: Presupunem dat graful orientat de mai jos, n care se dorete gsirea drumului de valoare minim de la nodul x1 la nodul x9.

x2 4 x1 3 x6 5 0 Matricea M va fi 4 0 8 8 7 0 2 9 3 0 7 4 5 0 3 0 2 5 0 8 5 3 x5 2 x7 9 3 9 6 8 0 7 0 6 8 8 2 9 x8 7 x9 7 9 x3 7 9 3 4 3 x4

iar dup calcularea liniilor Li obinem: x1 x2 x3 x4 x5 x6 x7 x8 x9 x1 0 x2 4 0 8 8 x3 7 0 2 x4 9 3 0 7 4 x5 5 0 x6 3 0 x7 2 5 0 x8 9 6 0 x9 9 3 8 7 0

17

L1 L2 12 L3 15 12 L4 13 12 L5 13 12

9 6 6 6 6

3 3 3 3 3

10 13 8 13 8 13 8 13

8 8 8 8 8

7 7 7 7 7

0 0 0 0 0

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 poziie a liniei 5, fiind egal cu 13. Pentru a gsi acest drum, plecm napoi de la linia 4 i avem:x1 x5 13 = 8 + 5 x3 8 = 6 + 2 x4 6 = 3 + 3 3 x9

B. Algoritmul lui Ford simplificatAlgoritmul lui Ford simplificat se aplic doar n grafuri care nu admit circuite. Cu ajutorul lui se gsete drumul de valoare optim ntre dou noduri fixate xi i xj. Printr-o eventual renumerotare a nodurilor putem presupune c nodul de la care pornete drumul este x1, care va fi numit nod iniial, iar nodul la care se termin este xn, numit nod final. Algoritmul este:

Pasul 1. I se d vrfului iniial valoarea 0 (zero): w(x0) = 0 Pasul 2. Se construiete mulimea A format din nodul iniial: A = {x1} Pasul 3. Se analizeaz nodurile din afara mulimii A. Dac exist noduri n care se poate ajunge prin arce directe doar de la nodurile mulimii A, acestea se adaug la mulimea A, cu valoarea: w(xi) = min (w (x j ) + v (x j , x i )) , n problemele de minim sau w(xi) = max (w (x j ) + v (x j , x i )) , n problemele de maximxj x j ,x i

xj x j ,x i

(

)

(

)

apoi se trece la pasul 4 Dac nu exist nici un nod de acest tip atunci nu exist nici un drum de la x1 la xn. STOP

Pasul 4. Se analizeaz mulimea A: Dac xn A atunci valoarea sa reprezint valoarea drumului de valoare optim de la x1 la xn. Pentru gsirea acestui drum se pornete napoi de la nodul final xn i se gsesc nodurile x k1 , x k 2 , ..., x k r care formeaz drumul cutat, unde x k1 = xn, x k r =x1 i fiecare alt indice ki+1 este cel pentru care: w( x k i +1 ) + v( x k i +1 , x k i ) = w( x k i ) STOP 18

Dac xn A se reia algoritmul de la pasul 3.

Exemplu: Pentru acelai graf i aceeai pereche de noduri din exemplul rezolvat cu algoritmul lui Bellman-Kalaba vom avea succesiv:pas1: w(x1) = 0 pas2: A = {x1} pas3: Nodurile n care se poate ajunge doar din x1: {x5} w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5 pas4: x9 A pas3: A = {x1,x5} i nodurile n care se poate ajunge prin arce directe doar din x1 i x5 sunt: {x6} w{x6) = min( w(x1) + v(x1,x6), w(x5) + v(x5,x6)) = min(0 + 3 , 5 + 3) = 3 pas4: x9 A pas3: A = {x1,x5,x6} i nodurile n care se poate ajunge prin arce directe doar din x1, x5 i x6 sunt: {x2,x7} w{x2) = min( w(x1) + v(x1,x2), w(x5) + v(x5,x2), w(x6) + v(x6,x2)) = min(0 + 4,5 + 8,3 + 8) = 4 w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7 pas4: x9 A pas3: A = {x1,x2,x5,x6,x7} i nodurile n care se poate ajunge prin arce directe doar din x1, x2, x5, x6 i x7 sunt: {x3,x8} w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7 w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13 pas4: x9 A pas3: A = {x1,x2,x3,x5,x6,x7,x8} i nodurile n care se poate ajunge prin arce directe doar din x1, x2,x3,x5, x6, x7 i x8 sunt: {x4} w{x4) = min( w(x2) + v(x2,x4), w(x3) + v(x3,x4),w(x5) + v(x5,x4), w(x8) + v(x8,x4)) = min(4 + 9,7 + 3,5 + 7,13 + 4) = 10 pas4: x9 A pas3: A = {x1,x2,x3,x4,x5,x6,x7,x8} i nodurile n care se poate ajunge prin arce directe doar din x1, x2, x3, x4, x5, x6, x7 i x8 sunt: {x9} w{x9) = min( w(x3) + v(x3,x9), w(x4) + v(x4,x9), w(x7) + v(x7,x9), w(x8) + v(x8,x9)) = min(7 + 9, 10 + 3, 7 + 8, 13 + 7) = 13 pas4: x9 A i urmeaz s gsim drumul care are lungimea 13. Avem succesiv: w(x9) = w(x4) + v(x4,x9) w(x4) = w(x3) + v(x3,x4) w(x3) = w(x5) + v(x5,x3) w(x5) = w(x1) + v(x1,x5) deci drumul cutat este: x1 x5 x3 x4 x9Observaia 1. Dac graful are un circuit atunci se poate demonstra uor c nu vom putea da valoare nici unui nod al acestuia i dac exist vreun drum de la x1 la xn care trece prin unul din nodurile circuitului nu vom putea da valoare nici lui xn, cu toate c exist drum de la x1 la xn. Observaia 2: Algoritmul necesit pentru memorare i manipulare doar cunoaterea, pentru fiecare nod, a nodurilor spre care "pleac" arce din acesta i valorile acestor arce, fiind mult mai uor de aplicat sau implementat pe calculator. El are ns dezavantajul c se poate aplica doar n grafuri fr circuite.

C. Algoritmul Ford generalizat19

Algoritmul lui Ford generalizat a fost creat cu scopul de a putea gsi drumul optim i n grafurile care au circuite. Cu ajutorul lui se gsete drumul de valoare optim ntre dou noduri fixate xi i xj. Printr-o eventual renumerotare a nodurilor putem presupune c nodul de la care pornete drumul este x1, care va fi numit nod iniial, iar nodul la care se termin este xn, numit nod final. Algoritmul este:

Pasul 1. I se d vrfului iniial valoarea 0 (zero): w(x0) = 0 i tuturor celelalte valoarea + (ntr-o problem de minim) sau - (ntr-o problem de maxim). Pasul 2. n ordinea cresctoare a indicilor nodurilor se calculeaz pentru fiecare nod, pe baz fostelor valori, noile valori cu formula: * w (xi) = min w (x i ), min (w (x j ) + v (x j , x i )) n problemele de minim xj (x j , x i ) * sau w (xi) = max w (x i ), max (w (x j ) + v (x j , x i )) n problemele de maxim xj (x j , x i ) * Pasul 3. Se compar noile valori w (xi) cu fostele valori w(xi): Dac w*(xi) = w(xi) pentru orice nod xi atunci: dac w(xn) < (la problema de minim) sau w(xn) > - (la problema de maxim), valoarea nodului xn reprezint valoarea drumului de valoare minim(maxim) de la x1 la xn. Pentru gsirea acestui drum se pornete napoi de la nodul final xn i se gsesc nodurile x k1 , x k 2 , ..., x k r care formeaz drumul cutat, unde x k1 = xn,x k r = x1 i fiecare alt indice ki+1 este cel pentru care: w( x k i +1 ) + v( x k i +1 , x k i ) = w( x k i ) STOP dac w(xn) = + (-) atunci nu exist nici un drum de la x1 la xn. STOP Dac exist cel puin un nod pentru care w*(xi) < w(xi) se reia algoritmul de la pasul 2 pentru noile valori ale vrfurilor.Observaie: Algoritmul poate gsi drumul i n grafuri cu circuite dar este evident mult mai lent dect cel simplificat. Pentru scurtarea duratei de execuie se poate modifica algoritmul n sensul c o valoare nou calculat a unui vrf va fi folosit imediat ca atare la calculul noilor valori ale celorlalte, nu doar dup ce se calculeaz noile valori ale tuturor vrfurilor.

D. Algoritmul lui Dijkstran algoritmul Ford simplificat, pentru a gsi valoarea nodului final, deci a drumului minim, plecm de la nodul iniial n toate direciile posibile, pstrnd de fiecare dat toate nodurile analizate. Acest fapt duce la un consum inutil de timp, deoarece foarte multe din aceste noduri nu vor face parte din drumul optim. Pentru a elimina acest neajuns, algoritmul lui Dijkstra ncearc s pstreze, la fiecare iteraie, mulimea minim de noduri care s le conin pe toate cele care vor forma efectiv drumul optim. n plus, algoritmul se poate aplica i n drumuri cu circuite. Ca un minus este faptul c se aplic doar la probleme de minim. Algoritmul are urmtorii pai:

Pasul 1. I se d vrfului iniial valoarea 0 (zero): w(x0) = 0 Pasul 2. Se construiete mulimea A format din nodul iniial: A = {x1} Pasul 3. Se analizeaz nodurile din afara mulimii A. 20

Dac exist noduri n care se poate ajunge prin arce directe de la noduri din A (nu doar de la nodurile mulimii A, ca la algoritmul lui Ford simplificat) se calculeaz pentru toate acestea: w(xi) = min (w (x j ) + v (x j , x i )) n problemele de minimx jA x j ,x i

(

)

dar, spre deosebire de algoritmul lui Ford simplificat, se adaug la mulimea A doar cel pentru care se obine valoarea minim, apoi se trece la pasul 4. Dac nu exist nici un nod de acest tip atunci nu exist nici un drum de la x1 la xn. STOP

Pasul 4. Se analizeaz mulimea A: Dac xn A atunci valoarea sa reprezint valoarea drumului de valoare optim de la x1 la xn. Pentru gsirea acestui drum se pornete napoi de la nodul final xn i se gsesc nodurile x k1 , x k 2 , ..., x k r care formeaz drumul cutat, unde x k1 = xn, x k r =x1 i fiecare alt indice ki+1 este cel pentru care: w( x k i +1 ) + v( x k i +1 , x k i ) = w( x k i ) STOP Dac xn A se reia algoritmul de la pasul 3.

Exemplu Vom aplica algoritmul la acelai graf folosit la ceilali algoritmi, pentru a putea face comparaii:pas1: w(x1) = 0 pas2: A = {x1} pas3: Nodurile n care se poate ajunge i din x1: {x2, x5, x6} w{x2) = min( w(x1) + v(x1,x2)) = 0 + 4 = 4 w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5 w{x6) = min( w(x1) + v(x1,x6)) = 0 + 3 = 3 min(w{x2),w{x5),w{x6)) = w{x6) = 3 pas4: x9 A pas3: A = {x1,x6} i nodurile n care se poate ajunge prin arce directe din x1 sau x6 sunt: {x2,x5,x7} w{x2) = min( w(x1) + v(x1,x2), w(x6) + v(x6,x2)) = min(0 + 4 , 3 + 8) = 4 w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5 w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 8 min(w{x2),w{x5),w{x7)) = w{x2) = 4 pas4: x9 A pas3: A = {x1,x2,x6} i nodurile n care se poate ajunge prin arce directe din x1, x2 sau x6 sunt: {x3,x4,x5,x7} w{x3) = min( w(x2) + v(x2,x3)) = min(4 + 7) = 11 w{x4) = min( w(x2) + v(x2,x4)) = min(2 + 9) = 11 w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5 w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 0 min(w{x3),w{x4),w{x5),w{x7)) = w{x5) = 5 pas4: x9 A pas3: A = {x1,x2,x5,x6} i nodurile n care se poate ajunge prin arce directe din x1, x2, x5, x6 i x7 sunt: {x3,x4,x7,x8} w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7 w{x4) = min( w(x2) + v(x2,x4), w(x5) + v(x5,x4)) = min(4 + 9,5 + 7) = 12 21

w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7 w{x8) = min( w(x5) + v(x5,x8)) = min(5 + 9) = 14 min(w{x3),w{x4),w{x7),w{x8)) = w{x3) = w{x7) = 7 pas4: x9 A pas3: A = {x1,x2,x3,x5,x6,x7} i nodurile n care se poate ajunge prin arce directe din x1, x2, x3, x5, x6, i x7 sunt: {x4,x8,x9} w{x4) = min( w(x2) + v(x2,x4), w(x3) + v(x3,x4),w(x5) + v(x5,x4)) = min(4 + 9,7 + 3,5 + 7) =10 w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13 w{x9) = min( w(x3) + v(x3,x9), w(x7) + v(x7,x9)) = min(7 + 9,7 + 8) = 15 min(w{x4),w{x8),w{x9)) = w{x4) = 10 pas4: x9 A pas3: A = {x1,x2,x3,x4,x5,x6,x7} i nodurile n care se poate ajunge prin arce directe din x1, x2, x3, x4, x5, x6, i x7 sunt: {x8,x9} w{x9) = min( w(x3) + v(x3,x9), w(x4) + v(x4,x9), w(x7) + v(x7,x9)) = min(7 + 9,10 + 3,7+8)=13 w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13 min(w{x8),w{x9)) = w{x8) = w{x9) = 13 pas4: x9 A i urmeaz s gsim drumul care are lungimea 13. Avem succesiv: w(x9) = w(x4) + v(x4,x9) w(x4) = w(x3) + v(x3,x4) w(x3) = w(x5) + v(x5,x3) w(x5) = w(x1) + v(x1,x5) deci drumul cutat este: x1 x5 x3 x4 x9

8. Reele de transportntr-o mare varietate de situaii concrete din practica economic se pune problema deplasrii unei cantiti de materie, energie, informaie etc, din anumite locuri, numite surse, n alte locuri, numite destinaii. Pentru realizarea acestui transport se folosesc o serie de trasee, numite rute de legtur. Unitile indivizibile ale cantitii Q, care se deplaseaz de-a lungul rutelor ntre surse i destinaii, se numesc uniti de flux, iar ansamblul rutelor, surselor, destinaiilor i, eventual, a altor puncte intermediare se numete reea de transport. Situaia de mai sus poate fi reprezentat geometric printr-un graf finit, conex i fr bucle. Pentru ca o astfel de problem s fie suficient de complex pentru a necesita un studiu matematic riguros, trebuie ca fiecare surs s poat aproviziona mai multe destinaii i orice destinaie s poat fi aprovizionat de mai multe surse. Aprovizionarea destinaiilor se poate face direct de la surse sau prin intermediul altor puncte, numite puncte intermediare. n cazul cel mai general pot exista de asemenea legturi ntre surse i/sau legturi ntre destinaii. Aa cum s-a vzut i la problema de transport, situaia de mai sus este un cadru extrem de larg, care permite existena unui numr foarte mare de tipuri de probleme posibile, diferite ntre ele prin informaiile suplimentare pe care le avem despre reea i prin obiectivele urmrite. Una dintre acestea este problema determinrii cantitii maxime (minime) care poate fi transportat de la surse la destinaii, n situaia n care sursele dispun de cantiti limitate (inferior sau superior), destinaiile au un necesar sau o putere de absorbie limitat inferior sau superior iar pe fiecare rut se poate transporta doar o cantitate cuprins ntre anumite limite. Pentru studiul matematic al acestei situaii vom da definiiile matematice ale obiectelor implicate n problem i ipotezele modelului.

Definiia 1: Se numete reea de transport standard un graf finit, simplu, conex, fr bucle G = (X,U) care are urmtoarele proprieti:22

2. Exist i este unic t X a.. U t = , U t (n care doar "intr" arce) numit+

1. Exist i este unic s X a.. U s , U s = (din care doar "ies" arce), numit intrarea reelei de transport;

+

ieirea reelei de transport; 3. S-a definit o funcie c: U R+ care asociaz fiecrui arc u un numr strict pozitiv cu numit capacitatea arcului. Observaie: Este clar c exemplele obinuite au doar rareori o singur surs i o singur destinaie. Totui, printr-o tehnic foarte simpl, orice reea de transport se poate aduce la forma standard: 1. Dac sunt mai multe surse se introduce un nod suplimentar din care "pleac" cte un arc spre fiecare surs (i numai spre acestea), iar capacitile acestor arce vor fi egale cu disponibilurile surselor corespunztoare; 2. Dac sunt mai multe destinaii se introduce un nod suplimentar spre care "pleac" cte un arc din fiecare destinaie (i numai din acestea), iar capacitile acestor arce vor fi egale cu necesarurile destinaiilor corespunztoare; Definiia 2: Se numete flux ntr-o reea de transport R = (X,U) o funcie : U R+ care are urmtoarele proprietile: P1. 0 u cu oricare ar fi u din U; valoarea u se numete flux al arcului uP2.+ u U i

u

=

u U i

u

oricare ar fi i s,t (suma fluxurilor arcelor care "intr" ntr-

un nod i este egal cu suma fluxurilor arcelor care "ies" din acest nod, cu excepia nodului iniial i al celui final.

Definiia 3: Se numete valoare a fluxului suma fluxurilor arcelor care "pleac" din nodul iniial s i se noteaz cu . Observaie: Se poate demonstra uor c aceast valoare este egal i cu suma fluxurilor arcelor care "intr" n nodul final t. n concluzie avem:=

+ u U s

u

=

u U t

u

Valoarea fluxului reprezint cantitatea care se transport efectiv pe reea de la surse la destinaii.

Definiia 4: Se numete flux de valoare maxim ntr-o reea un flux n aceast reea, cu proprietatea c, pentru orice alt flux ' pe aceast reea, avem '.Valoarea fluxului de valoare maxim reprezint cea mai mare cantitate care se poate transporta efectiv pe reea, de la surse la destinaii. Economic vorbind, ne intereseaz, referitor la o reea, rspunsurile la urmtoarele ntrebri: 1. 2. 3. 4. Putem transporta ntreaga cantitate necesar la destinaii? Dac da, cum transportm efectiv aceast cantitate de la surse la destinaii? Dac nu, din ce motiv nu putem realiza acest transport? Cum putem nltura cu eforturi minime acest motiv? 23

Rspunsul la primele dou ntrebri se poate afla prin gsirea fluxului de valoare maxim i compararea valorii lui cu suma necesarurilor destinaiilor. n plus, valoarea acestuia pe un arc reprezint cantitatea care trebuie transportat pe ruta respectiv, pentru a obine aceast valoare a fluxului. Rspunsul la ultimele dou ntrebri pornete de la observaia c cea mai mare cantitate care poate traversa reeaua de la un cap la altul este egal cu dimensiunea celui mai ngust loc de trecere prin reea. Dac vrem, deci, s mrim fluxul va trebui s lrgim tocmai acest cel mai ngust loc de traversare al reelei. Pentru formalizarea consideraiilor de mai sus vom introduce noiunea de tietur ntr-o reea:

Definiia 5: Dat o reea de transport G(X,U) cu s = nodul iniial i t = nodul final, se numete tietur n reea o partiie a mulimii vrfurilor reelei de transport, format din dou submulimi V i W (VW = , VW = X) astfel nct s V i t W.O tietur poate fi privit, intuitiv, ca o seciune a reelei, care las nodul iniial cu o submulime din noduri ntr-o parte, nodul final cu restul nodurilor n cealalt parte i reteaz toate arcele care trec dintr-o parte n cealalt. A cunoate o tietur este echivalent cu a cunoate care sunt elementele celor dou mulimi, V i W, care formeaz partiia. Vom nota o tietur prin T = (V,W), convenind ca mulimea scris pe prima poziie s conin nodul iniial s al reelei iar cea scris pe a doua, nodul final t.

Definiia 6: Se numete capacitate a unei tieturi T = (V,W) ntr-o reea de transport G(X,U), notat C(T), suma capacitilor tuturor arcelor care au extremitatea iniial n V i cea final n W. C(T) = cuu = x i ,x j x i V x jW

) (

Pentru a nu exista nici o ambiguitate, insistm asupra faptului c se vor lua n considerare doar arcele care trec de la mulimea ce conine nodul iniial spre mulimea care conine nodul final, adic n sensul normal de transport (surse destinaie).

Definiia 7: Se numete tietur de valoare minim ntr-o reea o tietur T n aceast reea, cu proprietatea c, pentru orice alt tietur T' n aceast reea, avem C(T) C(T').Urmtoarele teoreme fac legtura matematic dintre fluxurile unei reele i tieturile sale:

Teorema 1. Dat o tietur T = (V,W) i un flux ntr-o reea de transport avem:=

u = x i ,x j x i V x jW

) (

u

u = x i ,x j x i W x jV

) (

u

sau, altfel spus, valoarea unui flux oarecare este egal cu suma fluxurilor arcelor care trec de la V la W din care se scade suma fluxurilor arcelor care trec invers, de la W la V, oricare ar fi tietura T = (V,W).

Demonstraie: Avem succesiv:24

=

u = x i ,x j x i V x jV

( ( )

= u = u + u u = u = (s, x j ) u = (s, x j ) x i V uU + uU i x xi x i s x jX x jX

u

u ) +

u = x i ,x j x i V x jW

) (

u

-

u = x i ,x j x i W x jV

) (

u

=

u = x i ,x j x i V x jW

) (

u

u = x i ,x j x i W x jV

) (

u

Corolar: ntr-o reea de transport valoarea oricrui flux este mai mic sau egal dect valoarea oricrei tieturi. Demonstraie: Fie T o tietur oarecare i un flux oarecare. Avem succesiv:

=

u = x i ,x j x i V x jW

) (

u

u = x i ,x j x i W x jV

) (

u

u = x i ,x j x i V x jW

) (

u

u = x i ,x j x i V x jW

c) (

u

= C(T)

Corolar: ntr-o reea de transport valoarea fluxului maxim este mai mic sau egal dect valoarea tieturii minime. Demonstraia e evident. n plus, din cele de mai sus se vede c egalitatea are loc numai dac, pentru tietura minim, exist un flux pentru care toate arcele de la V la W sunt folosite la maxim (fluxul e egal cu capacitatea arcelor) iar pe toate arcele de la W la V nu se transport nimic. Teorema lui Ford-Fulkerson Dac fluxul este maximal atunci exist o tietur de capacitate egal cu valoarea fluxului. Demonstraie: Fie un flux maximal. Introducem urmtorul procedeu de marcare a vrfurilor: Pasul 1. Se marcheaz nodul iniial s cu 0(zero); Pasul 2. Pentru fiecare vrf marcat xi se marcheaz cu: [+xi] toate vrfurile nemarcate xj pentru care exist arcul (xi,xj) i (xi,xj) < c(xi,xj) (adica nodurile spre care mai e loc pentru a se transporta ceva din xi); [xi] toate vrfurile nemarcate xj pentru care exist arcul (xj,xi) i (xj,xi) > 0 (adic toate nodurile spre care pleac deja ceva din xi); Pasul 3. Se repet pasul 2 pn nu mai poate fi marcat nici un vrf.

Dac vrful final t ar fi marcat, atunci ncepnd de la acesta, am putea construi lanul x k1 , x k 2 , ..., x k r unde x k1 = s, x k r = t i marcajul oricrui vrf x k i +1 este + x k i sau x k i . Adugnd la fluxul fiecrui arc al lanului de tipul ( x k i , x k i +1 ) valoarea: = min(

(x k i ,x k i +1 )

min

(c(x k , x k ) (x k , x k )) , (x min ,xi i +1 i i +1 k i +1

ki

)

(x k i , x k i +1 ) )

i scznd din fluxul fiecrui arc de tipul ( x k i +1 , x k i ) aceeai valoare , obinem un flux de valoare + , deci fluxul nu ar fi maximal. n concluzie vrful t nu va fi marcat. Fie tietura T = (V,W), unde V este format din mulimea nodurilor marcate iar W din cele nemarcate. n acest caz, pentru fiecare arc (xi,xj) care "traverseaz" tietura avem:25

dac xi V atunci (xi,xj) = c(xi,xj) deoarece nodul xj nu e marcat dac xi W atunci (xi,xj) = 0 deoarece nodul xi nu e marcat n acest caz avem: C(T) =

u = x i ,x j x i V x jW

c) (

u

=

u = x i ,x j x i V x jW

) (

u

u = x i ,x j x i W x jV

) (

u

=

i teorema e demonstrat. Teorema lui Ford-Fulkerson poate stabili doar valoarea fluxului maxim dar nu d o metod de gsire a acestuia. Pentru a rezolva problema gsirii fluxului de valoare maxim se poate folosi algoritmul lui Ford-Fulkerson. Pentru expunerea acestuia vom introduce i noiunile de:arc saturat = un arc pe care fluxul este egal cu capacitatea; drum complet = un drum de la nodul iniial s la nodul final t care conine cel puin un arc saturat; flux complet = un flux pentru care orice drum de la nodul iniial s la nodul final t este complet. Algoritmul lui Ford-Fulkerson ETAPA I Se determin un flux complet. Pasul 1. Se numeroteaz nodurile reelei de transport astfel nct x1 = s i xn = t; Pasul 2. Se asociaz grafului fluxul nul (u = 0 pentru orice arc u din graf); Pasul 3. n ordine lexicografic, se ia pe rnd fiecare drum D de la nodul iniial la cel final, se calculeaz valoarea D = min(c u u ) i se adaug la fluxul de pe fiecare arc aluD

drumului. Arcul(arcele) unui drum D pentru care s-a obinut valoarea minim D va fi dup aceast adugare, n mod evident, saturat i deci drumul D va fi complet. Dup epuizarea tuturor drumurilor se obine un flux complet, de valoare = D .D

Deoarece alegerea drumurilor n ordine lexicografic nu ine cont de structura reelei, aa cum se poate vedea pe un exemplu, acest procedeu nu asigur ntotdeauna gsirea fluxului maxim. Acest impediment poate fi depit fie prin gsirea unei ordini de parcurgere a tuturor drumurilor, care s dea pentru fiecare reea fluxul maxim, n urma procedeului de mai sus, fie prin redistribuirea judicioas a fluxului gsit la etapa I. A doua variant este cea care se aplic la etapa II.ETAPA II Se determin fluxul maxim Pasul 4. Se marcheaz nodul iniial s cu 0(zero); Pasul 5. Pentru fiecare vrf marcat xi se marcheaz cu: [+xi] toate vrfurile nemarcate xj pentru care exist arcul (xi,xj) i (xi,xj) < c(xi,xj) (adica nodurile spre care mai e loc pentru a se transporta ceva din xi); [xi] toate vrfurile nemarcate xj pentru care exist arcul (xj,xi) i (xj,xi) > 0 (adic toate nodurile spre care pleac deja ceva din xi); Pasul 6. Se repet pasul 5 pn este marcat nodul final sau pn cnd nu mai poate fi marcat nici un vrf; Pasul 7. Dac nodul final a fost marcat atunci fluxul este maxim i algoritmul se oprete, n caz contrar trecndu-se la pasul 8;

26

Pasul 8. Construim un lanul L = x k1 , x k 2 , ..., x k r unde x k1 = s, x k r = t i marcajul oricrui vrf

x k i +1 este + x k i sau x k i . Se calculeaz: L = min(

(x k i ,x k i +1 )

min

(c(x k , x k ) (x k , x k )) , (x min ,xi i +1 i i +1 k i +1

ki

)

(x k i , x k i +1 ) )

care se adaug la fluxul fiecrui arc al lanului de tipul ( x k i , x k i +1 ) i se scade din fluxul fiecrui arc de tipul ( x k i +1 , x k i ).Pasul 9. Se terge marcajul i se reia algoritmul de la pasul 4.

n final, tietura de valoare minim este cea n care V = mulimea nodurilor marcate iar W = mulimea nodurilor nemarcate.Observaia 1. Algoritmul nu asigur ntotdeauna gsirea fluxului maxim, deoarece se poate ca creterea fluxului la fiecare iteraie s se fac cu cantiti din ce n ce mai mici astfel nct suma lor s nu ating niciodat marginea superioar dat de valoarea tieturii minime, algoritmul avnd o infinitate de pai. Teorema de mai jos d o condiie suficient pentru ca algoritmul s se termine ntr-un numr finit de pai:

Teorem Dac toate capacitile rutelor reelei sunt numere raionale atunci algoritmul lui Ford-Fulkerson are un numr finit de pai. Demonstraie Prin nmulirea tuturor acestor capaciti cu cel mai mic multiplu comun al numitorilor se obine o reea cu toate capacitile numere naturale. innd cont de formula de calcul, la fiecare iteraie cantitatea adugat va fi numr natural i cum valoarea fluxului maxim este mrginit de capacitatea tieturii minime Cmin, care este de asemenea numr natural, algoritmul va avea nevoie de cel mult Cmin pai pentru a o atinge.Observaia 2. Teorema de mai sus asigur doar o limitare superioar a numrului de iteraii ale algoritmului, fa de capacitatea tieturii minime. Aceast valoare poate fi ns, n anumite cazuri, foarte mare i, dac nu se iau precauii suplimentare, algoritmul nu va da soluia n timp util. Depirea acestei situaii este asigurat de urmtoarea teorem:

Teorem Dac la fiecare iteraie se alege drumul (lanul) de lungime minim atunci 1 algoritmul va avea cel mult mn iteraii, unde n = numrul de noduri iar m = numrul de muchii. 2Observaia 3. Exist probleme n care se dorete gsirea fluxului minim ntr-o reea, valorile fluxului pe arce fiind limitate inferior de capacitile acestora. n acest caz se aplic de asemenea algoritmul lui Ford-Fulkerson astfel:

Pasul 1. Se calculeaz M = maximul capacitilor arcelor Pasul 2. Se construiete reeaua R', care este fosta reea, n care au fost modificate doar capacitile arcelor, acestea devenind c = M cu u Pasul 3. Se gsete cu algoritmul Ford-Fulkerson fluxul , de valoare maxim, n aceast reea Pasul 4. Fluxul de valoare minim n reeaua iniial va avea valorile ' = M Observaia 4. Exist i alte tipuri de probleme asemntoare celor de mai sus. Astfel, se poate pune problema:

27

gsirii capacitilor minime ale arcelor cu care se poate asigura transportarea ntregii cantiti de la surse la destinaii fluxului minim(maxim) ntr-o reea n care capacitile rutelor sunt limitate att superior ct i inferior; n cazul n care rutelor li se asociaz i costuri unitare de parcurgere, putem cuta fluxul maxim de cost minim;

28

CAPITOLUL 7 CMP DE EVENIMENTE. CMP DE PROBABILITATE

7.1.

Noiuni fundamentale: evenimente; probabilitatea de producere a evenimentelor.

DEFINIIE : Experiena reprezint orice act care poate fi repetat n condiii date. Aplicarea experienei asupra unei populaii date se numete prob. DEFINIIE : Evenimentul reprezint orice rezultat al unei experiene. Noiunea de eveniment n teoria probabilitilor este legat de producerea sau neproducerea unui fenomen (ntr-o experien dat) i nu de natura fenomenului. EXEMPLUL 1 : La controlul de recepie a mrfurilor : Experiena const n cercetarea unui lot de marf, dac corespunde sau nu din punct de vedere al calitii. Proba const n cercetarea calitii unei uniti (unui articol) din marfa respectiv. Evenimentele rezultate sunt : -articolul este corespunztor; -articolul nu este corespunztor. EXEMPLUL 2 : La aruncarea unui zar : Experiena const n crearea condiiilor de aruncare a zarului (mas, zar). Proba const n aruncarea zarului i citirea feei. Evenimentele sunt asociate feelor 1, 2, 3, 4, 5 sau 6. DEFINIIE : Se numete eveniment elementar evenimentul care se poate realiza printr-o singur prob. Dac o experien are n rezultate posibile, vom nota evenimentele elementare cu 1 , , n . DEFINIIE : Notm cu mulimea tuturor evenimentelor elementare, = {1 , , n } .

De exemplu, n cazul aruncrii zarului, = {1,2,3,4,5,6} . OBSERVAIE : Mulimea este evenimentul sigur (adic evenimentul care se poate realiza prin oricare din probe). DEFINIIE : Evenimentul care nu se produce la nici o efectuare a experienei se numete evenimentul imposibil, pe care l notm cu . DEFINIIE : Evenimentul care poate fie s se produc fie s nu se produc n efectuarea unei experiene se numete eveniment aleator (ntmpltor). Vom nota evenimentele aleatoare cu litere mari A, B, C, Dac evenimentele aleatoare pot fi observate de mai multe ori n condiii identice se constat c ele se supun unor legiti statistice. Teoria probabilitilor studiaz aceste legiti, care permit s se prevad desfurarea evenimentelor. Fiecrui eveniment A i corespunde un eveniment contrar (opus, complementar) care se realizeaz atunci i numai atunci cnd nu se realizeaz evenimentul A. Vom nota evenimentul contrar cu A sau C(A). OBSERVAIE : = ; = . DEFINIIE : Evenimentul A implic evenimentul B, dac realizarea evenimentului A atrage dup sine realizarea evenimentului B. Notm A B . OBSERVAIE : Dac A este un eveniment i este evenimentul sigur, evident A . DEFINIIE : Dac A B i B A , atunci evenimentele A i B sunt echivalente.

7.2. Operaii cu evenimente Fie evenimentele A i B. DEFINIIE : Evenimentul a crui producere const n producerea a cel puin unuia din evenimentele A i B se numete

reuniunea (suma) evenimentelor. Se noteaz cu A B i se citete A sau B. DEFINIIE : Evenimentul care const n producerea simultan a evenimentelor A i B se numete intersecia (produsul) evenimentelor. Se noteaz cu A B i se citete A i B. n general, S = Ai i I = Ai .i =1 i =1 n n

DEFINIIE : Dou evenimente sunt incompatibile dac nu se pot produce simultan. Deci A B = . OBSERVAIE : A A = . DEFINIIE : Diferena evenimentelor AB este evenimentul care se produce atunci i numai atunci cnd se produce A i nu se produce B. Avem : A B = A B . Proprieti ale operaiilor cu evenimente :A B = B A ( A B) C = A ( B C ) A A = A A = A A = A A = ( A) = A A B = B A ( A B) C = A ( B C ) A A = A A = A = A A A =

= n Ai i =1

=

n

Ai

i =1

DEFINIIE : O mulime nevid K de pri ale lui se numete corp de evenimente dac : a) oricare ar fi evenimentul A din mulimea K, atunci i evenimentul A aparine mulimii K. b) oricare ar fi evenimentele A i B din mulimea K, A B aparime mulimii K. CONSECINE :

a) K Demonstraie : dac A K , atunci i A K , iar A A = K , conform proprietilor operaiilor cu evenimente. b) K Demonstraie : deoarece K , i = K . c) Dac A, B K , atunci A B K Demonstraie : A B = A B = A B K . d) Dac A, B K , atunci A B K DEFINIIE : O mulime nevid K de pri ale lui se numete corp borelian de evenimente, dac : a) oricare ar fi evenimentul A din mulimea K, atunci i evenimentul A aparine mulimii K. b) oricare ar fi A j K , j = 1,2,... , atunci

Aj =1

j

K.

DEFINIIE : Se numete cmp finit de evenimente, o mulime finit de evenimente elementare pe care s-a definit un corp de evenimente K. Se noteaz (, K ) . DEFINIIE : Se numete cmp borelian de evenimente o mulime finit de evenimente elementare peste care s-a definit un corp borelian de evenimente. OBSERVAIE : Din definiia anterioar rezult c n mulimea evenimentelor cmpului (, K ) exist o submulime { i }, i = 1,..., n numit mulimea evenimentelor elementare. Aceast mulime are urmtoarele proprieti : 1) i , i = 1,..., n . 2) i j = , i j . 3) 4)

i =1

n

i

=.

exist cel puin un eveniment A (, K ) , A i , i = 1,..., n , astfel nct A = i1 ... i p , 1 p n .

DEFINIIE : E1, E2 ,...,En formeaz un sistem complet de evenimente, deoarece :

1) 2)

Ei =1

n

i

=

Ei E j = , i j .

7.3. Conceptul de probabilitate Pentru msurarea anselor de realizare a unui eveniment aleator s-a introdus noiunea de probabilitate. Sunt cunoscute trei definiii ale noiunii de probabilitate. 1. Definiia axiomatic introduce probabilitatea ca o funcie p definit pe un cmp de evenimente cu valori n mulimea numerelor reale. 2. Definiia clasic a probabilitii reduce conceptul de probabilitate la cazul evenimentelor egal posibile. 3. Definiia statistic exprim probabilitatea cu ajutorul frecvenei de realizare a unui eveniment ntr-un numr mare de experiene realizate n aceleai condiii. DEFINIIA AXIOMATIC A PROBABILITII: Fie (, K ) un cmp de evenimente. Funcia P : (, K ) R , care asociaz oricrui eveniment A (, K ) numrul real P(A), cu proprietile : 1) P( A) 0 , oricare ar fi A (, K ) , 2) P() = 1 , 3) P( A B) = P( A) P( B ) , oricare ar fi A, B (, K ) , A B = , se numete probabilitate. Aceast definiie a fost enunat de A.N.Kolmogorov (1929). DEFINIIE : Un cmp de evenimente (, K ) nzestrat cu o probabilitate P se numete cmp de probabilitate, i se noteaz cu (, K , P) .

DEFINIIE : Se numete probabilitate - aditiv (sau complet aditiv) pe cmpul borelian de evenimente (, K ) o funcie P : (, K ) R cu proprietile : 1) P( A) 0 , oricare ar fi A (, K ) , 2) P() = 1 , 3) P Ai = P ( Ai ) , oricare ar fi irul i =1 i =1 Ai A j = , oricare ar fi i j .

( Ai )iN

*

(, K ) i

DEFINIIE : Un cmp borelian de evenimente (, K ) nzestrat cu o probabilitate - aditiv se numete cmp borelian de probabilitate i se noteaz (, K , P) .

Consecine ale definiiei axiomatice a probabilitii: C1. P( A ) = 1 P( A) Demonstraie : Din proprietile operaiilor cu evenimente tim c Atunci deoarece A A = . P( A A ) = P( A) + P( A ) , A A = . Rezult c P( A ) = 1 P( A) . C2. Dac Ai (, K ) , i = 1,..., n cu proprietatea c Ai A j = , oricare ar fi i j , i, j = 1,..., n , atunci : P Ai = P ( Ai ) . i =1 i =1

Demonstraie : - folosim inducia matematic . Pentru n=2, relaia este adevrat, conform proprietii numarul 3 din definiia lui Kolmogorov. Presupunem c propoziia este adevrat pentru n-1, adic n 1 n 1 n 1 P Ai = P ( Ai ) . Notm A = Ai . Rezult astfel c putem i =1 i =1 i =1 scrie

Ai =1

n 1

i

= A An .

n 1 n Atunci P Ai = P( A) + P( An ) = P( Ai ) . i =1 i =1

C3.

P( ) = 1 , unde , i =1 i 1

n

2

,..., n sunt evenimentele elementare

ale mulimii . Demonstraie:

i =1 n i=1

n

i

=i

i

i j = ,

i j.

Atunci

n Pi = P() = 1, deci i=1

P( ) =1.

C4. Dac A, B (, K ) i A B , atunci P( A) P( B) . Demonstraie: Dac A B , atunci A = i i B =p

i j = , ij.Deci :P( A) = P( i )i =1 p

i =1

i =1 q

p+q

i

. tim c

i

P ( B ) = P( i ) +i =1

p

i = p +1

P( ) .i

Dar

P( i ) 0 , de unde rezult c P( A) P( B ) .

C5. Oricare ar fi evenimentul A (, K ) , este adevrat relaia 0 P( A) 1 . Demonstraie: Oricare ar fi A (, K ) , A , deci vom avea P( ) P( A) P() , adic 0 P( A) 1 .

C6. S considerm o experien n care mulimea evenimentelor elementare cuprinde evenimente egal posibile (exemplu: aruncarea unui zar). Din C3. rezult c P(i ) = 1 . Fie A (, K ) , unde n k A = i1 ... ik . Atunci P( A) = P(i1 ) + ... + P(ik ) , deci P( A) = . n

DEFINIIA CLASIC A PROBABILITII: Probabilitatea unui eveniment A (, K ) este egal cu raportul dintre numrul cazurilor favorabile producerii evenimentului A i numrul total de cazuri posibile.

7.4. Probabiliti condiionate DEFINIIE : Fie (, K , P ) un cmp borelian de probabilitate. Fie A, B (, K , P ) cu P( A) 0 . S presupunem c apariia evenimentului B este condiionat de apariia evenimentului A. Vom nota aceast probabilitate condiionat cu PA (B ) sau P( A B ) P( B / A) . Atunci PA ( B ) = = P ( B / A) . P ( A) Proprieti ale probabilitilor condiionate: Proprietatea 1 : {, K , PA ( B )} este probabilitate.

un

cmp

(chiar

borelian)

de

Demonstraie: Verificm ipotezele : 1. PA ( B ) 0 deoarece P( A B ) 0 i P( A) > 0 2. PA ( ) = 1 P ( A ) P( A) PA () = = =1 P ( A) P( A) 3. PA ( B1 B2 ) = PA ( B1 ) + PA ( B2 ) P[(B1 B2 ) A] P[(B1 A) (B2 A)] = = PA ( B1 B2 ) = P( A) P( A) P ( B1 A) P( B2 A) = + = PA ( B1 ) + PA ( B2 ) P( A) P ( A) n aceast demonstraie avem n vedere faptul B1 B2 = i ( B1 A) ( B2 A) = B1 B2 A . Proprietatea 2 : Dac P( A) 0 i P(B) 0 , relaia P( A) PA ( B) = P( B) PB ( A) .

c

atunci

este

adevrat

Demonstraie: P( A B ) , de unde P ( A B ) = P ( A) PA ( B ) PA ( B ) = P ( A) P( B A) , de unde P ( B A) = P ( B ) PA ( A) PB ( A) = P( B ) Cum P( A B ) = P( B A) , avem P( A) PA(B) = P(B) P ( A) B i proprietatea 2 este demonstrat. DEFINIIE : Evenimentele independente dac P( A B ) = P ( A) P( B ) .A, B (, K )

sunt

7.5. Formule de calcul ale probabilitilor n cazul operaiilor cu evenimente 1) Reuniunea evenimentelor incompatibile: n n P Ak = P ( Ak ) , dac Ai A j = , i j . k =1 k =1 Demonstraia este imediat, prin metoda induciei matematice, utiliznd axioma 3 din definiia axiomatic a probabilitii. 2) Reuniunea evenimentelor compatibile: P( A B ) = P ( A) + P( B ) P( A B ) (*) Demonstraie : Evenimentele A i B se mai pot scrie astfel: A = ( A B) ( A B ) B = ( B A) ( B A ) Deci A B = ( A B ) ( A B ) ( A B ) . Evenimentele din paranteze sunt independente dou cte dou. ( ) P( A B ) = P( A B ) + P( A B ) + P( A B )P ( A) = P ( A B ) + P ( A B ) P( B ) = P( A B ) + P( A B ) Din relaia ( ) scdem cele dou relaii de mai sus i obinem: P( A B ) P( A) P( B ) = P ( A B ) , de unde rezult P( A B ) = P ( A) + P( B ) P( A B ) .

n general, fie sistemul de evenimente compatibile { A1 ,..., An } K . Probabilitatea producerii a cel puin unuia dintre aceste evenimente este: n n P Ai = P( Ai ) P( Ai Aj ) + P( Ai Aj Ak ) + ... + i< j i< j 0 i p + q = 1 .

Evident: 1) f ( x ) 0 ; p 1 = = 1 , deoarece seria q x 1 1 q p x =1 x =1 x =1 este seria geometric de raie 0 < q < 1 , convergent, cu suma 1 . 1 q

2)

pq

x 1

= p q x 1 = p

8.1.1. Operaii cu variabile aleatoare discrete; variabile aleatoare independentex Fie X : 1 p 1 xi pi xn y ; Y : 1 q pn 1m j =1

yj qj q j = 1.

ym . qm

pi = f ( x i ) 0 ;

n i =1

pi = 1 ;

qj = f (yj ) 0 ;

Evenimentul care const n faptul c : X ia valoarea xi l notm ( X = xi ), i=1, , n , P( X = xi )=pi ;

Y ia valoarea P( Y = y j )=qj .

yj

l notm ( Y = y j ), j=1, , m,

Evenimentul care const n faptul c X = xi i Y = y j este ( X = xi ) (Y = y j ) , i=1, , n; j=1, , m .P[(X = xi );(Y = y j )] = P[(X = xi ) (Y = y j )] are o probabilitate

bine determinat, notat pij . DEFINIIE: Variabilele aleatoare X i Y se numesc independente dac evenimentele ( X = xi ) i ( Y = y j ), i=1, , n; j=1, , m sunt independente. n acest caz: P[( X = xi ); (Y = y j )] = P[( X = xi ) (Y = y j )] = pij = pi q j . OPERAII:x + yj , unde pij = pi q j , i=1, , n; j=1, , m . 1) X + Y : i p ij

x y 2) X Y : i j , i=1, , n; j=1, , m , unde, dac X i Y sunt p ij independente, pij = pi q j . a xi , i=1, , n . 3) a X = p i xk 4) X k : 1 p 1

xik pi

k xn . pn

EXEMPLU: Fie variabilele aleatoare discrete X i Y cu repartiiile: 1 2 1 1 0 i X : 0,3 0,5 0,2 Y : 0,5 0,5

1 0 2 1 3 1 X +Y : 0,3 0,5 0,3 0,5 0,5 0,5 0,5 0,5 0,2 0,5 0,2 0,5 1 0 1 2 3 X +Y : 0,15 0,25 0,25 0,25 0,10 . 0 1 1 2 2 0 X Y : 0,15 0,15 0,25 0,25 0,1 0,1 1 2 2 1 0 . X Y : 0,1 0,25 0,3 0,25 0,1

3 6 0 3 X : 0,3 0,5 0,2 . 1 8 0 X3 : 0,3 0,5 0,2 .

Reprezentarea grafic a funciilor de probabilitate:0 1 2 EXEMPLU: X : f (0) = 0,3 f (1) = 0,5 f (2) = 0,2 , pi = f ( xi ) .

Atunci graficul funciei de probabilitate a variabilei aleatoare X definit anterior este:

0,5 0,3 0,2 0

1

2

8.2. Variabile aleatoare continuex , unde x [a, b] , iar f (x ) Fie variabila aleatoare X : f ( x) este probabilitatea de apariie a lui x.

DEFINIIE: Funcia f (x ) se numete densitatea de probabilitate a variabilei aleatoare X. Proprietile densitii de probabilitate: 1) 2)f ( x) 0 ;

f ( x )dx = 1 .a

b

EXEMPLE: I. S se determine constanta c, astfel nct funcia f : [a, b] R , f ( x ) = c , s fie densitate de probabilitate a unei variabile aleatoare X. 1) f ( x ) 0 , oricare ar fi x [a, b] , deci c 0 ;b b

2)a

f ( x )dx = c dx = c x |b = c (b a ) = 1 aa

c=

1 . ba

x Deci: X : 1 , x [a, b] este o variabil aleatoare f ( x) = ba numit variabil aleatoare continu uniform pe intervalul [a , b] .

II. S se determine constanta k, astfel nct funcia f : [0, ) R , f ( x ) = k e x , s fie densitate de probabilitate a unei variabile aleatoare X. 1) f ( x ) 0 , oricare ar fi x 0 , deci k 0 , f fiind o funcie exponenial

2)

0

a 1 x f ( x )dx = k e x dx = k (1) = k = 1 , unde ( a ) = 0 x e dx0

este integrala a lui Euler.

x Deci X : , este o variabil aleatoare pe f (x) = ex x 0 intervalul [0, ) .

Reprezentarea grafic a densitii de probabilitate: Pentru funcia de la exemplul I, reprezentarea grafic este:

funcia este continu pe [a , b]1 ba

A =1

0

a

b

Pentru funcia de la exemplul II, reprezentarea grafic este:

1 -

A =1

ntr-adevr, derivata funciei f este oricare ar fi x > 0 ; i lim f ( x ) = 0 ; f (0) = 1 .x

f ' ( x ) = e x < 0 ,

X

f' f

0 - 1

- - - - - - - - - - 0

i deci graficul densitii de probabilitate f (x ) este cel de mai sus.

Funcia de repartiie a unei variabile aleatoare: Prezentarea unei variabile aleatoare prin funcia de probabilitate f ( xi ) sau prin densitatea de probabilitate prezint aspecte diferite. Considerm evenimentul ( X < x ) , x R . DEFINIIE: Se numete funcie de repartiie a variabilei aleatoare X, funcia F : R R dat de F ( x ) = P( X < x ) . OBSERVAIE: Variabila aleatoare X este discret (continu), dup cum funcia de repartiie F (x ) este o funcie discret (continu). Calculul funciei de repartiie: 1) Fie variabila aleatoare discret : x

x X : 1 p 1

xi pi

xi +1 pi +1 pi =

xn pnf ( xi )

F ( x ) = P( X < x ) =xi < x

xi < x

Reprezentarea grafic este urmtoarea:

1p +... p1+n 1

( (

p1 + p2 p1 0

( (

x1

x2

x3 .. x n 1

xn

0 1 2 EXEMPLU: X : 0,3 0,5 0,2

F (x ) 10,3+0,5-

( (

0,3 -(

x0 1 2

2) Fie variabila aleatoare continu: x , . X : f ( x ) x [ a , b] F (x ) f (x )

) a

( b

Putem lrgi domeniul de definiie al funciei f deoarece F se consider pe R .F ( x) =

f (t )dt

x

. Reprezentarea grafic a funciei de

repartiie continu F (x ) are urmtoarea form: F (x ) 1-

0

x

x EXEMPLU: X : f ( x ) = e x , x 0 . x

F ( x) =

x f (t )dt = et dt = et |0 = e x + 1 = 1 e x ;0

x

F ' ( x ) = e x > 0 ; F ' ' ( x ) = e x < 0 . Prin urmare, graficul funciei F este:

1

0F (0) = 0 ; lim F ( x ) = 1 .x

Proprieti ale funciei de repartiie: P1. 0 F ( x ) 1 , oricare ar fi x R . Demonstraie: F ( x ) = P( x < 1) , i deci fiind o probabilitate, rezult proprietatea P1. P2. F (x ) este nedescresctoare, adic, oricare ar fi x1 x 2 , rezult c F ( x1 ) F ( x 2 ) . Demonstraie: ( X < x1 ) = ( X < x1 ) ( x1 X < x 2 ) . P ( X < x 2 ) = P ( X < x1 ) + P ( x1 X < x 2 ) . 1 4 2 43 1 4 2 43 1 4 4 2 4 43F ( x2 ) F ( x1 ) 0

F ( x ) = 0, x a P3. Dac x [a, b] , atunci F ( x ) = 1, x > b Consecine: lim F ( x ) = 0 , lim F ( x ) = 1 .x x

CAPITOLUL 9 CARACTERISTICI NUMERICE ALE VARIABILELOR ALEATOARE 9.1. Media; definiie, proprieti Fie X variabil aleatoare pe cmpul de probabilitate (, K , P ) .xi , unde i = 1, , n . X : p = f (x ) i i Atunci valoarea medie variabilei aleatoare discrete X este

DEFINIIE : Fie

M (X ) =

n i =1

xi f ( xi ) .

x DEFINITIE : Fie X : , unde x [a, b] . Atunci f ( x) valoarea medie a variabilei aleatoare continue X este

M (X ) =

b a

x f ( x )dx .

OBSERVAIE

:

Pentru

n ,

trebuie

ca

seria

+ , trebuie ca integrala improprie s fie convergent.EXEMPLE:1 2 3 , M ( X ) = 1 0,2 + 2 0,5 + 3 0,3 = 2,1 . 1) X : 0,2 0,5 0,3 x x 2) X : f ( x ) = e x , x 0 , M ( X ) = 0 xe dx = ( 2) = 1 .

i =1

xi f ( xi ) s fie convergent. Pentru a sau b tinznd ctre sau

Proprieti ale mediei: x P1. Fie X : i , i = 1, , n . Dac xi , atunci : f (x ) i M(X ) .

Demonstraie: M ( X ) = xi f ( xi ) Adunnd aceste relaii pentru valorile indicelui i = 1, , n , obinem:i =1

n

f ( xi ) xi f ( xi ) f ( xi ) f ( xi ) M ( X ) f ( xi ) ,decii =1 i =1

n

n

M(X ) , deoarece

f (x ) = 1.i =1 i

n

P2. M ( k ) = k , adic media unei constante este o constant. k Demonstraie: X : , M (k ) = k 1 = k . 1 P3. Media unei constante nmulit cu o variabil aleatoare este egal cu constanta nmulit cu media variabilei aleatoare. Adic: M ( a X ) = a M ( X ) .x Demonstraie: Fie X : 1 p 1 a x1 Atunci a X : p 1

M(a X) = a x1 p1 + + a xn pn = a (x1 p1 + + xn pn ) = a M(X) .

xn , pn a xn . pn

pi =1

n

i

= 1 , M ( X ) = xi pi .i =1

n

P4. Dac X i Y sunt dou variabile aleatoare, atunci : M ( X + Y ) = M ( X ) + M (Y ) . Demonstraie:x Fie X : i , p i yj i fie Y : , q j

i = 1, , n , j = 1, , m ,

M ( X ) = xi pi ,i =1

n

pi =1

n

i

=1

M (Y ) = y j q j ,j =1

m

xi + y j q j = 1 . Atunci X + Y : pi q j , i = 1, , n , j = 1, , m . j =1 m

M(X +Y) = (xi + yj ) pi qj =xi pi qj +yj pi qj =xi pi qj +i=1 j=1 i=1 j=1 i=1 j=1 i=1 j=1

n m

n m

n m

n

m

+ pi y j q j = M ( X ) + M (Y ) .i =1 j =1

n

m

P5. Dac X i Y sunt independente, atunci: M(X Y) = M(X) M(Y) . x y Demonstraie: X Y : i j , i = 1, , n , j = 1, , m . p q i jM ( X Y ) = xi y j pi q j = xi pi y j q j = M ( X ) M (Y )i =1 j =1 i =1 j =1 n m n m

9.2. Dispersia; definiie, proprieti 2 1 1 2 , . Observm c Fie X : 0,1 0,4 0,4 0,1 M ( X ) = 0 valorile lui X nu difer mult de medie. 1000 5 5 1000 Fie Y : , M (Y ) = 0 . Observm c 0,1 0,4 0,4 0,1 valorile lui Y difer mult de medie. mprtierea valorilor lui Y este mai mare dect mprtierea valorilor lui X.x x2 xn i fie M(X) media sa. Construim Fie X : 1 p p p 2 n 1 variabila aleatoare = X M ( X ) , numit abaterea variabilei aleatoare X de la media sa. Fie m=M(X).

x m x2 m : 1 p p2 1

xn m pn

OBSERVAIE: M( ) = M[X m] = M(X ) M(m) = M(x) m = 0. Deci nu putem utiliza media variabilei aleatoare abatere pentru a determina mprtierea fa de media sa. Din acest motiv, ca o msur a mprtierii valorilor unei variabile aleatoare X fa de media sa, vom lua dispersia, notat cu D(X), unde: D( X ) = 2 = M ( 2 ) . Dispersia este media ptratului variabilei aleatoare de abatere .

( x m) 2 2 : 1 p1

( x2 m) 2 p2

( xn m)