33grafuri

8/3/2019 33Grafuri

1/38

Bazele cercetrii operaionale

ELEMENTE DE TEORIA GRAFURILOR

1. Noiuni generalen general, pentru situaiile care necesit la rezolvare un oarecare efort mintal (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 ctmai clar toate aspectele acesteia.

n acest scop se folosesc imagini grafice gen diagrame, schie, grafice etc. O reprezentaredintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate n special pentru vizualizareasistemelori situaiilor complexe. n general, vom reprezenta componentele acestora prin puncte n

plan iar relaiile (legturile, dependenele, influenele etc) dintre componente prin arce de curb cuextremitile 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 asociasau nu orientri (dup cum se influeneaz cele dou componente ntre ele), numere care s exprimeintensitatea relaiilor dintre componente etc.

Este evident, totui, c aceast metod are limite, att din punct de vedere uman (prea multepuncte i segmente vor face desenul att de complicat nct se va pierde chiar scopul pentru care afost creat claritatea i simplitatea reprezentrii, aceasta devenind neinteligibil) ct i din punct devedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

Din acest motiv, alturi de expunerea naiv-intuitiv a ceea ce este un graf, dat mai sus, seimpune att o definiie riguroas ct i alte modaliti de reprezentare a acestora, adecvate n generalrezolvrilor matematice.

Definiia 1 Se numete multigrafun triplet G = (X, A,f) n care X i A sunt dou mulimiiarfeste o funcie, definit pe produsul vectorial al lui X cu el nsui (X2 = XX), care ia valori nmulimea prilor mulimii A (notatP(A))

Mulimea X se numete mulimea nodurilor multigrafului i elementele sale se numescnoduri (sau vrfuri) ale multigrafului, iar A reprezint mulimea relaiilor (legturilor) posibile ntredou noduri ale multigrafului.

Definiia 2 Se numete graf orientat un multigraf n care mulimea A are un singurelement: A = {a}.

n acest caz mulimea prilor mulimii A are doar dou elemente: mulimea vid intreaga mulime A. Dac unei perechi orientate (xi, xj) din X

2 i se asociaz prin funciafmulimeaA 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 numetenod final sau extremitate final a arcului (xi,xj). Arcul (xi,xj) este incident spre interior vrfuluixj i incident spre exterior vrfului xi. Dac pentru un arc nodul iniial coincide cu nodul finalatunci acesta se numete bucl. Nodurile xii xj se vor numi adiacente dac exist cel puin unuldin 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 mul imeavrfurilor sale iar U mulimea arcelor sale.

De asemenea, putem cunoate un graf orientat cunoscnd mulimea nodurilor i, pentrufiecare nod, mulimea arcelor incidente spre exterior. Din acest motiv putem defini un graf orientatca o pereche (X,) unde X este perechea nodurilor iar este o funcie definit pe X cu valori n

111

8/3/2019 33Grafuri

2/38

Elemente de teoria grafurilor

mulimea prilor lui X, valoarea acesteia ntr-un nod xi, (xi) X fiind mulimea noduriloradiacente nodului xi, prin arce pentru care xi este extremitatea iniial.

Definiia 3 Se numete graf neorientat un multigraf n care mulimea A are un singurelement iar funciafare proprietatea:

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

n aceste condiii, dac f[(xi,xj)] = f[(xj,xi)] = A atunci perechea neorientat {xi,xj} este omuchie iar dacf[(xi,xj)] = f[(xj,xi)] = spunem c nu exist muchie ntre vrfurile xii 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 vomspecifica acest fapt la momentul respectiv.

2. Moduri de reprezentare ale unui grafA. O prim modalitate de reprezentare este listarea efectiv a tuturor nodurilori 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 extremitinodurile arcului i pe care este trecut o sgeat orientat de la nodul iniial spre celfinal.

D. Putem folosi o reprezentare geometric n care nodurile sunt reprezentate de dou ori, ndouiruri paralele, de la fiecare nod din unul din iruri plecnd sgei spre nodurile cucare formeaz arce n care el este pe prima poziie, de pe al doilea ir (reprezentarea princoresponden).

E. Un graf poate fi reprezentat printr-o matrice ptratic boolean, de dimensiune egal cunumrul 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 cunumrul de noduri, n care pe o poziie aij va fi xixj dac exist arcul (xi,xj) i 0 n cazcontrar.

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 {x

1, x

2, x

4, x

5} C

x3

x4x5

x6

x2x1x2 {x3, x4, x6}x3 {x1, x2}x4 {x5}x5 {x2}x6 {x4}

D (reprezentarea prin coresponden)x1 x2 x3 x4 x5 x6

x1 x2 x3 x4 x5 x6

112

8/3/2019 33Grafuri

3/38


E Fx1 x2 x3 x4 x5 x6

x1 1 1 0 1 1 0x2 0 0 1 1 0 1x3 1 1 0 0 0 0x4 0 0 0 0 1 0

x5 0 1 0 0 0 0x6 0 0 0 1 0 0

x1 x2 x3 x4 x5 x6x1 x1x1x1x2 0 x1x4x1x5 0x2 0 0 x2x3x2x4 0 x2x6x3 x3x1x3x2 0 0 0 0x4 0 0 0 0 x4x5 0

x5 0 x5x2 0 0 0 0x6 0 0 0 x6x4 0 0

3. Concepte de baz n teoria grafurilor1. semigraf interior al unui nod xk: este mulimea arcelor = {(xkxU j,xk)/ (xj,xk) U} care

sunt incidente spre interior nodului xk;

2. semigraf exterior al unui nod xk: este mulimea arcelor = {(x+kxU k,xi)/ (xk,xi) U} caresunt incidente spre exterior nodului xk;

3. semigradul interior al unui nod xk: este numrul arcelor care sunt incidente spre interiornodului xk= cardinalul lui i se noteaz cu ;kxU kx

4. semigradul exterior al unui nod xk: este numrul arcelor care sunt incidente spreexterior nodului xk= cardinalul lui i se noteaz cu ;

+kx

U +kx

5. gradul unui nod xk: este suma semigradelor nodului xk: = + ;kx

+kx

kx

6. nod izolat: este un nod cu gradul 0;7. nod suspendat: este un nod cu gradul 1;8. arce adiacente: arce care au o extremitate comun;9. 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) .+ix14.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;

Observaie: ntr-un graf neorientat noiunile de drum i lan sunt echivalente i deasemenea cele de circuit i ciclu.

24.graf parial al unui graf G = (X,U): este un graf G'(X,U') cu U' U;25.subgrafal unui graf G = (X,): este un graf G'(X',') unde X' X i '(xi) = (xi) X'

pentru orice xi X';

113

8/3/2019 33Grafuri

4/38


26.graf redus al unui graf G = (X,U): este un graf G*(X*,U*) unde X* este format dinmulimile unei partiii de mulimi nevide ale lui X, iar ( ) exist doar dac i j i

exist cel puin un arc n U, de la un nod din la un nod din

*iX ,

*jX

*iX

*jX .

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 suntechivalente, 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, ntreoricare dou noduri din component exist cel puin un drum i nu mai exist nici un nodn afara componentei legat printr-un drum de un nod al componentei).

4. Gsirea drumurilor ntr-un graf orientatDac privim graful ca imagine a unui sistem, nodurile reprezentnd componentele sistemu-

lui, 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 x i n starea xj. n ambele cazuri se vede cavem de-a face doar cu informaii despre legturi directe; totui, chiar dac o component xi nuinflueneaz direct componenta xj ea o poate influena prin intermediul altor componente, existndun ir de componente intermediare: x1 x2 ,..., xk, fiecare influennd-o direct pe urmtoarea i xidirect 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 sautreceri posibile este de obicei foarte important iar pentru un sistem cu mii sau zeci de mii decomponente 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, deoareceeste evident c "xi influeneaz xj" sau "din starea xi se poate trece n starea xj" este echivalent cuexistena 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 orientatcu un numr finit de noduri.

Pasul 1. Se construiete matricea boolean a adiacenelor directe corespunztoare grafului, notatcu 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 presupuneexistena 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 ambelearce ((xi,xk) i (xi,xk)). Aceasta este echivalent cu a verifica dac, n matricea boolean a adiacene-lor directe, exist vreun indice k astfel nct elementul k al liniei i i elementul k al coloanei j s fieambele egale cu 1. Dac folosim operaiile algebrei booleene de adunare i nmulire:

+& 0 1 & 0 10 0 1 0 0 01 1 1 1 0 1

atunci verificrile de mai sus sunt echivalente cu a verifica dac elementul de pe poziia (i,j) din A2este egal cu 1. Valoarea 1 spune doar c exist cel puin un drum de lungime 2 de la x i la xj. Dacdorim 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 presupuneexistena unui nod xkastfel nct s existe un drum de lungime 2 de la xi la xki 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

114

8/3/2019 33Grafuri

5/38

8/3/2019 33Grafuri

6/38


lij =( )

( )

ji

jiji

x,xarculaexistnuadac0x,xarculaexistadacxx

((

((

i matricea L~

, definit prin:

ijl~

=)

( )

ji

jij

x,xarculaexistnuadac0

x,xarculaexistadacx((

((

numitmatricea 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 gsiun indice k astfel nct elementul de pe poziia k a liniei i, din matricea L, s fie xi,xki elementulde 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 .n21 iii s...sDefiniia 3: Se numete nmulire latin o operaie definit pe mulimea cuvintelor unui

alfabet, notat " ", astfel:L

n21 iiis...ss L m21 jjj s...ss = m21n21 jjjiii s...sss...ss

(produsul a dou cuvinte se obine prin concatenarea lor)nmulirea latin este asociativ, are ca element neutru cuvntul vid, nu ecomutativi un element este inversabil doar dac este cuvntul vid.

Definiia 3: Se numete adunare latin o funcie definit pe mulimea cuvintelor unuialfabet cu valori n mulimea parilor mulimi cuvintelor, notat " " astfel:L+

n21 iii s...ss L+ m21 jjj s...ss =

m21

n21

jjj

iii

s...ss

s...ss

(suma a dou cuvinte este mulimea format din cele dou cuvinte)

Pasul 5. Se calculeaz succesiv matricile:L2 = LL L

~, L3 = L2 L L

~, ... ,Lk+1 = Lk L L

~

folosind operaiile de nmulire i adunare latin, alfabetul fiind mulimea nodurilor grafului, undeoperaia de nmulire este uor modificat, produsul dintre dou elemente ale matricilor fiind 0, dacunul 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 delungime 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; 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 de100100 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.

116

8/3/2019 33Grafuri

7/38


Pas 3. Se reia pasul 2 pn cnd, dup o aplicare a acestuia, matricea rmne aceeai (numai apare nici un 1)

Ultima matrice obinut este matricea drumurilor D numiti matricea conexiunilor totale.Aceast metod, dei mai simpl nu spune nsi care sunt aceste drumuri, pentru gsirea

lor aplicndu-se, de exemplu, nmulirea latin

117

8/3/2019 33Grafuri

8/38


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. suntarbori.

x1

x1

x1x1

x1

x1

x1

x1

x1

x1

x1

a) c)b)

Figura 4.1

Studiul arborilor este justificat de existena n practic a unui numr mare de probleme carepot fi modelate prin arbori. Dintre acestea amintim:

1. construirea unor reele de aprovizionare cu ap potabil (sau cu energie electric sautermic 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.

n toate problemele de mai sus se dorete ca, dintre muchiile unui graf neorientat, s seextrag 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) existmai 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)2)

3)

H este arbore;H nu conine cicluri i, dac se unesc printr-o muchie dou noduri neadiacente, seformeaz 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);H este conex i dac i se suprim o muchie se creeaz dou componente conexe (arboreleeste graful conex cu numrul minim de arce);

118

8/3/2019 33Grafuri

9/38


4)5)6)

H este conex i are n-1 muchii;H este fr cicluri i are n-1 muchii;Orice pereche de noduri este legat printr-un lani numai unul.

Demonstraie :

1) 2). ntre cele dou noduri adiacente noii muchii introduse exista deja un drum n fostul graf.Acest drum, mpreun cu noul arc va forma evident un ciclu i afirmaia 2) a fostdemonstrat.

2)3). Pentru oricare dou vrfuri neunite printr-o muchie, adugnd muchia dintre cele douvrfuri s-ar crea, conform ipotezei, un ciclu care conine aceast muchie, deci doudrumuri ntre cele dou noduri, din care unul nu conine noua muchie, adic n grafuliniial exista un drum ntre cele dou noduri. Dac nu exist cicluri nseamn c ntreoricare dou noduri exist un singur drum. Pentru dou noduri unite printr-o muchie,aceasta este chiar drumul corespunztor celor dou noduri. Dac suprimm aceast muchientre cele dou noduri nu va mai exista nici un drum, formndu-se dou componenteconexe.

3)4). Demonstraia se face prin inducie dup n = numrul de noduri ale grafului. Pentru n=2 esteevident. Presupunem afirmaia adevrat pentru toate grafurile cu cel mult n noduri. Dacgraful are n+1 noduri, prin suprimarea unei muchii se formeaz dou componente conexefiecare avnd cel mult n noduri (n1 n, n2 n i n1 + n2 = n+1) i deci au n1 1 respectivn2 1 muchii. n concluzie graful iniial a avut (n1 1) + (n2 1) +1 = n1 + n2 1= (n+1)-1muchii, ceea ce era de demonstrat.

4)5). Dac ar avea un ciclu atunci prin suprimarea unui arc al acestuia ar rmne de asemeneaconex. Eliminm acest arc apoi repetm procedeul pentru graful parial rmas i tot aapn cnd nu mai rmne nici un ciclu. n acest moment graful rmas este conex i nu arecicluri deci este arbore i deci are n-1 arce, n contradicie cu faptul c el avea n-1 arce

nainte de a ncepe suprimarea arcelor;5)6). Dac ntre dou noduri ar exista dou drumuri atunci acestea ar forma la un loc un ciclu.Deci ntre 2 noduri este cel mult un drum. Dac ntre dou noduri nu ar exista nici un drumar fi cel puin dou componente conexe n graf, fiecare fiind arbore (pentru c nu existcicluri) i deci fiecare ar avea un numr de arce cu 1 mai mic dect numrul de noduri.Fcnd adunarea, ar rezulta c n graf sunt strict mai puin de n-1 arce.

6)1). Dac H ar avea un ciclu, ntre dou noduri ale acestuia ar exista dou lanuri, ncontradicie cu ipoteza.

Presupunem c avem un graf pentru care am verificat deja dac este conex. Dac nu esteatunci acesta, evident, nu are nici un graf parial care s fie arbore.

Presupunem de asemenea c fiecrei muchii i este asociat o valoare real.

5.2. Algoritmi pentru gsirea arborelui de valoare optim

Vom da mai jos trei algoritmi pentru determinarea unui graf parial al grafului, care s fiearbore 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 muchiiloracestuia.

A. Algoritmul lui Kruskal

Pasul 1. Dintre toate muchiile grafului se alege muchia de valoare minim (maxim). Dacminimul este multiplu se alege la ntmplare una din muchiile respective. Deoarece acest"la ntmplare" trebuie cumva tradus n limbajul calculatorului, n cazul implementrii unui

119

8/3/2019 33Grafuri

10/38


program bazat pe acest algoritm, vom perturba din start valorile muchiilor, la k muchii cuaceiai valoare V adunnd respectiv valorile , 2, ... , k, unde este foarte mic (n oricecaz, k mai mic dect diferena dintre valoarea acestor arce si valoarea imediat superioar aunui 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 ceste 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 algoritmspecial 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 componenteconexe 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 lantmplare, 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).

B. Algoritmul lui Sollin

Pasul 1. Pentru fiecare nod se alege muchia adiacent de valoare minim (maxim).Pasul 2. Se evideniaz componentele conexe, existente n graful parial format din arcele alese

pn n acest moment.Pasul 3. Pentru fiecare component conex se alege muchia adiacent de valoare minim

(maxim). Prin muchie adiacent unei componente conexe nelegem o muchie care are osingur extremitate printre nodurile componentei respective.

Pasul 4. Se reia algoritmul de la pasul 2 pn rmne o singur component conex. Aceasta estearborele optim cutat.

Acest algoritm asigur de asemenea gsirea arborelui optim, necesit mult mai puinecalcule (la fiecare alegere se calculeaz minimul doar pentru muchiile adiacente unui singur nod),evit automat formarea ciclurilor, dar, pentru grafuri foarte mari, la un moment dat pot exista att demulte componente conexe care trebuie memorate succesiv, nct calculul devine greoi sau, pecalculator, depete posibilitile de memorare ale calculatorului.

C. O variant a algoritmului lui Kruskal

Pasul 1. Dintre toate muchiile grafului se alege cea de valoare minim (maxim);Pasul 2. Dintre toate muchiile adiacente componentei conexe format din arcele alese 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 singurcomponent conex, fiind mult mai uor de implementat pe calculatori mult mai rapid n execuie.

Exemplu: Administraia unei localiti montane a hotrt construirea unor linii de telefericcare s lege oraul de cele 8 puncte turistice importante din jurul acestuia. n urma unui studiu au

120

8/3/2019 33Grafuri

11/38


fost puse n evidena toate posibilitile i costurile de conectare a obiectivele turistice ntre ele i cuoraul, acestea fiind prezentate n figura 4.2.

Se cere gsirea variantei de construcie de cost minim, care s asigure accesul din ora laoricare din obiectivele turistice.

9

Figura 4.2

8

86 7

84

3

7

52

2

33

5

4

88

7 9

P8

P5

P4

P7

P3

P6

P1

P2

O

Rezolvare

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 ajungela orice obiectiv turistic, atunci se va putea ajunge i de la orice staiune la oricare alta (trecnd prinora), 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. nplus, suma costurilor arcelor sale trebuie s fie minim. Vom aplica pe rnd cei trei algoritmi pentrugsirea acestuia:

A. Kruskal

La primul pas poate fi ales unul din arcele OP3 sau OP7, ele avnd valoarea minim 2. Putemalege 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. Nicin acest caz nu are vre-o importan ordinea alegerii, deoarece pot fi alese succesiv toate trei fr a

se forma nici un ciclu.Al aselea arc poate fi ales dintre arcele P4P5i P1P2, care au valoarea minim 4. Nici nacest caz nu are vre-o importan ordinea alegerii, deoarece pot fi alese succesiv ambele, fr a seforma nici un ciclu.

Urmtoarea valoare disponibil a unui arc este 5, dar arcul opt nu poate fi ales dintre arceleOP1, 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 fiales deoarece se formeaz ciclul OP5P7.

Valoarea urmtoare, 7, o au arcele OP4, P2P3 i P5P8. OP4 nu poate fi ales deoarece s-arforma ciclul OP5P4. Arcul P2P3 nu poate fi ales deoarece s-ar forma ciclul OP6P1P2P3. Arcul P5P8 nuformeaz 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.

121

8/3/2019 33Grafuri

12/38


7

Figura 4.3

43

2

2

33

4

P8

P5

P4

P7

P3

P6

P1

P2

O

B. Sollin

Vom alege: pentru nodul O arcul OP3pentru nodul P1 arcul P1P6pentru nodul P2 arcul P1P2pentru nodul P3 arcul OP3pentru nodul P4 arcul P4P5pentru nodul P5 arcul OP5pentru nodul P6 arcul P1P6pentru nodul P7 arcul OP7pentru nodul P8 arcul P5P8

Rezult graful parial:

Figura 4.4

7

4

3

2

23

4

P8P5

P4

P7

P3

P6

P1

P2

O

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 OP6pentru C2 arcul OP6

i obinem o singur component conex, care este arborele cutat.

122

8/3/2019 33Grafuri

13/38


C. Varianta algoritmului lui Kruskal

Succesiunea alegerii arcelor va fi:

1 OP32 OP7

3 OP64 OP55 P1P66 P1P27 P4P58 P5P8

123

8/3/2019 33Grafuri

14/38


6. Cuplajul a dou mulimi disjuncte.Probleme de afectare (de repartiie)

n practica economic sunt foarte des ntlnite probleme n care se dorete asocierea optima elementelor unei mulimi X = {x1, x2, ... , xn} cu elementele unei alte mulimi Y = {y1, y2, ... , ym}n condiiile unor limitri existente (i cunoscute) ale posibilitilor de asociere.

n general, fiecare asociere posibil xi yj aduce un anumit efect aij (profit, cost etc) carepoate fi calculat i vom presupune c este cunoscut.

Limitrile asupra asocierilor se traduc de obicei prin faptul c:

1. Un element xi poate fi asociat doar cu anumite elemente din Y i reciproc;2. La sfrit, fiecrui element din X i s-a asociat cel mult un element din Y i reciproc.

Asocierea optim presupune, de obicei, dou obiective:

1. S se fac maximul de asocieri;2. Suma efectelor asocierilor s fie maxim (sau minim, n funcie de semnificaia

acestora).

Reprezentarea geometric a situaiei de mai sus este un graf de forma:

x1

x2

xnym

y2

y1

numit graf bipartit.

Definiia 1: Se numete graf bipartit un graf G = (X, U) n care mulimea nodurilor poate fimprit n dou mulimi disjuncte A i B astfel nct orice arc are extremitatea iniial n A i ceafinal n B.

Definiia 2: Se numete cuplaj al unui graf bipartit o submulime de arce W U cuproprietatea c nu exist dou arce adiacente (sau altfel spus, pentru orice nod existcel mult un arcincident acestuia).

Definiia 3: Se numete cuplaj maxim un cuplaj cu proprietatea c orice arc care nu faceparte din cuplaj este adiacent cu un arc din cuplaj ( orice arc am aduga, nu mai rmne cuplaj nu exist nici un cuplaj n care s se includ strict conine numrul maxim de arceneadiacente)

Este evident c numrul de arce ale unui cuplaj este mai mic sau egal cu numrul deelemente din fiecare din mulimile A i B ( min (A,B). Este interesant de vzut ns ct demare este el efectiv i n ce condiii este egal chiar cu min (A,B).

Referitor la prima ntrebare, n 1931 Knig a demonstrat o teorem care permite stabilireanumrului de arce ale unui cuplaj maxim:

124

8/3/2019 33Grafuri

15/38


Teorem: Numrul maxim de arce ale unui cuplaj ntr-un graf bipartit G = (AB, ) esteegal cu ( )( )CCAmin

AC+

n ceea ce privete a doua problem, observm mai nti c putem presupune c ntotdeaunaAB, n caz contrar inversnd sensul tuturor arcelor grafului, problema rmnnd aceeai.

n acest caz:

( )( )CCAminAC

+

= A ( )( )CCAminAC

+

A = 0 ( )( )CCminAC

+

= 0

( )( )CCmaxAC

= 0 ( ) CC oricare ar fi C A

sau altfel spus, pentru orice submulime C a lui A, mulimea nodurilor atinse de arce care pleac dinnodurile sale, adic(C), are cel puin attea elemente ct C.

De exemplu, la repartizarea angajailor pe posturi, fiecare angajat poate obine un post doritdaci numai dac oricare ar fi mulimea de r angajai exist cel puin r posturi diferite din care potalege.

Presupunem, n continuare, c s-a asociat fiecrui arc (xi,x

j) o valoare v

ij.

Definiia 4: Se numete valoare a unui cuplaj suma valorilor arcelor care l formeaz.

n acest moment putem spune c determinarea unei asocieri optime a mulimilor X i Y de lanceput este echivalent matematic cu determinarea unui cuplaj maxim de valoare optim (minimsau maxim) n graful bipartit asociat.

Dintre problemele ntlnite n practica economic, ce se reduc matematic la gsirea unuicuplaj maxim de valoare optim, amintim:

1. Problema repartizrii muncitorilor unei secii la utilajele acesteia n funcie de pregtireai preferinele muncitorilor, complexitatea mainilor etc;2. transferarea unor informaii ntr-un grup;

3. Repartizarea angajailor pe posturi;4. Formarea grupelor de lucru dup afinitile dintre membrii colectivului.n 1955, bazndu-se pe teorema lui Knig, H.W. Kuhn a elaborat un algoritm, cunoscut n

literatura de specialitate sub denumirea de algoritmul ungar, cu ajutorul cruia se poate determinaun cuplaj maxim de valoare minim ntr-un graf bipartit pentru care A=B= n.

El se bazeaz pe observaia c, dac se adun (sau scade) aceeai numr la toate valorilearcelor, nu se modific ierarhia cuplajelor maxime, n ceea ce privete valoarea lor.

Vom prezenta algoritmul concomitent cu rezolvarea unui caz particular, pentru o mai bun

receptare a acestuia:"ntr-o secie produsele finite se obin n urma efecturii succesive a 6 operaii pe 6 maini.

n aceast secie sunt angajai 6 muncitori, fiecare fiind calificat pentru efectuarea oricrei din cele 6operaii. Pentru a optimiza activitatea n secie cei 6 muncitori au fost supui la un test n carefiecare a prelucrat un numr de piese, pe toate cele ase maini. n final, calculndu-se timpul mediun care muncitorul Mi efectueaz operaia Oj s-au obinut valorile (n ore) date n tabelul de mai jos:

M1 M2 M3 M4 M5 M6O1 4 3 6 2 6 8O2 5 4 8 3 8 9O3 5 6 8 2 8 7O

44 5 7 2 7 8

O5 4 6 6 3 6 7O6 6 6 8 3 8 9

125

8/3/2019 33Grafuri

16/38


S se gseasc acea repartiie a muncitorilor la maini astfel nct timpul n care o pies seprelucreaz succesiv pe cele 6 maini s fie minim."

Pasul 1. Se construiete matricea ptratic M care are elementele:

mij =

( ) ( )

( )

jijiji

x,xarculexistanudaca

x,xarculexistadacax,xarculuivaloarea

Pentru exemplul ales vom avea: M =

983866763664872754782865983845862634

Pasul 2. Se scade din fiecare linie minimul acesteia apoi, n matricea ob inut, din fiecare coloan

minimul acesteia (se poate face i invers, rezultatul final va fi acelai). Pentru exemplul

dat vom obine succesiv matricile:

M1 =

i apoi M

650533430331650532560643650512640412

2 =

220222000020220221130332220201210101

Ultima matrice este cea asupra creia se aplic urmtoarele calcule. n acest moment pefiecare linie i pe fiecare coloan se afl cel puin un 0, care corespunde celui mai mic timp. Sencearc n continuare folosirea doar a acestor repartizri:

Pasul 3.n ordinea cresctoare a numrului de zerouri i de sus n jos (n cazul existenei maimultor linii cu acelai numr de zerouri ) se ncadreaz pentru fiecare linie zeroul a cruicoloan conine cele mai puine zerouri (primul de la stnga dintre acestea, n caz deegaliate) i se bareaz celelalte zerouri de pe linia i coloana acestuia. Pe parcursulalgoritmului sunt luate n considerare la numrare doar zerourile nencadrate i nebaratenc. n final, pe fiecare linie i pe fiecare coloan va fi cel mult un zero ncadrat. Dac nfinal sunt n (= dimensiunea matricei) zerouri, atunci arcele corespunztoare formeazcuplajul cutat. Dac sunt mai puine se trece la pasul 4.

n exemplul nostru avem trei linii cu cte un zero (a 3-a, a 4-a i a 5-a) .l ncadrm pe cel depe linia 3 (prima dintre ele) i barm restul zerourilor de pe linia 3 i coloana 3, obinnd:

220222000020220221130332220201 210101

n acest moment pe liniile 1 i 2 se afl un zero. Se ncadreaz cel de pe linia 1 i sebareaz celelalte de pe linia 1 i coloana 2, obinnd:

126

8/3/2019 33Grafuri

17/38


222000221132221211

022002022033020010

Ultima linie cu zerouri este linia 5 din care l ncadrm pe primul i le barm pe celelalte:

220222000020220221130332220201210101

n total nu sunt 6 zerouri ncadrate (sunt doar trei) i deci trecem la pasul 4.

Pasul 4. La acest pas se va stabili numrul minim posibil de linii i coloane care s conin toatezerourile matricii. n acest sens vom proceda astfel:a) se marcheaz liniile care nu au nici un zero ncadrat;b) se marcheaz coloanele care au un zero barat pe o linie marcat;c) se marcheaz liniile care au un zero ncadrat pe o linie marcat (dac exist);Se repet operaiile b) i c) pn nu mai poate fi marcat nici o linie i nici o coloan.

n cazul nostru vom avea: a) se marcheaz liniile 2, 4 i 6;b) se marcheaz coloanele 2 i 4;c) se marcheaz liniile 1 i 3;b) nu mai marcm nici o coloan deoarece nu mai existnici un zero barat pe liniile 1 i 3, care s corespund uneicoloane nemarcate;c) nu mai marcm nici o linie, deoarece nu a mai aprutnici o coloan marcat.

Rezult:

220222

000020220221130332220201210101

Pasul 5. Se taie liniile nemarcate i coloanele marcate:

220222000020220221130332220201210101

Pasul 6.Se mpart elementele matricei n trei grupe:

G1 = elemente aflate la intersecii de linii netiate cu coloane netiate;

127

8/3/2019 33Grafuri

18/38


G2 = elemente situate la intersecii de linii tiate cu coloane netiate sau de linii netiatecu coloane tiate;

G3 = elemente situate la intersecii de coloane tiate cu linii tiate

Pasul 7. Se gsete minimul grupei G1, care se scade din fiecare element al lui G1i se adun lafiecare element al grupei G3. Elementele grupei G2 rmn neschimbate.

Pentru exemplul dat, minimul lui G1 este 1 i obinem noua matrice:

110121001030110120020231110100100000

Pasul 8. Se reia algoritmul de la pasul 3.Vom avea dup marcare:

110121001030110120020231110100100000

Deoarece avem 6 zerouri ncadrate, am obinut cuplajul maxim de valoare minim cutat, cruia iva corespunde repartizarea muncitorilor pe operaii de mai jos:

M1

M2

M3

M4

M5

36

7

4

4

6

O6

O5

O4

O3

O2

O1

M6

care duce la o durat total a prelucrrii unei piese de 6 + 4 + 7 + 6 + 3 = 26 oreObservaie: Deoarece regula de a alege de sus n jos la linii cu acelai numr de zerouri este

arbitrari de asemenea alegerea primului zero de la stnga, putem ajunge i la altecuplaje maxime, dar toate vor avea aceeai valoare, cea minim. De exemplu, un altcuplaj optim este:

M1

M2

M3

M4

M5 3

6

7

4

4 6

O6

O5

O4

O3

O2

O1

M6

adic

110121001030110120020231110100100000

128

8/3/2019 33Grafuri

19/38


care are de asemenea valoarea 26.

Observaia 1. Dac dorim un cuplaj de valoare maxim atunci vom calcula la pasul 1matricea M astfel:

1.Construind matricea A de elemente:aij =

( ) ( )( )

jijiji

x,xarculexistanudacax,xarculexistadacax,xarculuivaloarea

2.Matricea M va avea componentele: mij = ) ijijnji,1

aamax

apoi aplicm n continuare algoritmul.

Observaia 2. DacAB atunci aplicm acelai algoritm cu singura diferen c ne

vom opri cnd vom obine un numr de zerouri egal cu min (A,B).

129

8/3/2019 33Grafuri

20/38


7. Drumuri i circuite hamiltoniene

Una dintre cele mai cunoscute probleme economice este problema comis voiajorului. Comisvoiajorul este un individ care trebuie s prezinte s-au s distribuie marfa comandat la o serie decentre 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 trebuievizitate este mare sau foarte mare iar timpul disponibil foarte limitat atunci devine vital oasemenea 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 ncare se trece pe la fiecare obiectiv o singur dat. n plus, la sfrit trebuie s se afle n punctuliniial, adic sediul firmei la care lucreaz.

O reprezentare a regiunii aprovizionate, n care centrele pe la care se trece sunt vizualizateprin puncte iar cile de acces la acestea prin segmente de curbe, va fi evident un graf, problemareducndu-se la a gsi circuitul hamiltonian de lungime minim.

n timp, s-au evideniat o multitudine de probleme reductibile la gsirea unui drum (saucircuit) hamiltonian ntr-un graf, cum ar fi:

1. Problema potaului (gsirea traseului cel mai scurt care trece pe la toate locuinele ceaparin de oficiul potal la care lucreaz acesta);

2. Problema adunrii deeurilor (cel mai scurt drum care trece pe la toate punctele dedepozitate a deeurilor);

3. Problema succesiunii operaiilor (executarea mai multor operaii pe o main n aceaordine n care suma timpilor consumai cu pregtirea mainii pentru trecerea de la ooperaie la urmtoarea s fie minim)

4. Ordinea lipirii unor componente electronice pe o plac, etc;

Determinarea drumurilor hamiltoniene

Problema determinrii drumului (circuitului) hamiltonian de valoare optim s-a doveditdeosebit de dificil, neexistnd nici acum un algoritm care s rezolve problema n timp polinomiali nici mcar o metod simpl prin care s se decid dac ntr-un graf dat exist sau nu drumurihamiltoniene.

Exist ns mai muli algoritmi, unii exaci alii heuristici, care reuesc, ntr-un caz sau altul,s rezolve problema satisfctori 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.

130

8/3/2019 33Grafuri

21/38


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 C1i cele ale submulimii C2, ntre nodurile

submulimii C2i cele ale submulimii C3 etc.

Pasul 5. Se gsesc drumurile hamiltonieneUn 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 C 1 trecnd la un vrfdin C2, parcurgnd n continuare un drum hamiltonian n a doua submulime i tot aa, trecnd printoate 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 seoprete deoarece la un anumit pas nu mai exista nici o linie plina cu 1).

Observaie. Algoritmul lui Foulkes reduce gsirea drumurilor hamiltoniene n graful iniialG (care n problemele practice este foarte mare) la gsirea mai multor drumuri hamiltoniene maimici n componente tare conexe ale grafului. Dac un graf are o singur component tare conex,algoritmul lui Foulkes nu este eficient, n acest caz trebuind aplicai ali algoritmi cum ar fi cel bazatpe nmulirea latin.

B. Algoritmul lui Chen pentru determinarea drumurilor hamiltonienen grafuri fr circuite

Fie G = (X,U) un graf orientat fr circuite, cu n noduri: X = {x1, x2, , xn}. Vomconsidera 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 poateajunge n xj pentru c nu exist circuite.

Teorema 2.3 (Chen) Un graf cu n noduri, frcircuite conine un drum hamiltonian dacinumai dacexistrelaia:

( )

( )

2

1

1

==nn

xp

n

ii

Demonstraie Fie H un drum hamiltonian i presupunem c nodurile grafului au fost notate n

ordinea n care apar n acest drum. Atunci din orice nod xi se poate ajunge n toate nodurile cuindice mai mare i numai n acestea (altfel ar exista circuite) i deci puterea unui nod xi este n i, deunde:

(=

n

i

ixp

1

) = (n 1) + (n 2) + + 1 + 0 =( )

2

1nn

Ordonnd vrfurile n ordinea descresctoare a puterii lor de atingere (i > j p(xi) j ar nsemna c

131

8/3/2019 33Grafuri

22/38


din xi se poate ajunge n xj, deci n toate nodurile n care se poate ajunge din xj, iar din xj nu se poateajunge n xi, deci p(x ) > p(xi

( )j) n contradicie cu ipoteza de ordonare a nodurilor). Cum deasupra

diagonalei suntn

nn 1poziii iar suma puterilor vrfurilor este chiar

( )n

nn 1rezult c toate

poziiile de deasupra diagonalei sunt 1. Aceasta nseamn c exist toate arcele de forma (xi,xi+1)(altfel n-ar exista drum de la xi la xi+1, deoarece toate drumurile au indicii nodurilor n ordine

descresctoare) i deci drumul hamiltonian (x1, x2, , xn) q.e.d.

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

Demonstraie Deoarece un drum hamiltonian se identific cu o permutare a nodurilorgrafului, existena a dou drumuri hamiltoniene implic existena a dou permutri distincte anodurilor grafului i cum dou permutri distincte difer prin cel puin o inversiune vor exista dounoduri xii xj n ordinea xi xj pe un drum i invers pe cellalt, existnd deci un drum att de la xila xj ct i de la xj la xi, cele dou formnd mpreun un circuit, n contradicie cu ipoteza.

Pe aceste teoreme se bazeazalgoritmul lui Chen de determinare a drumului hamiltonianntr-un graf orientat fr circuite:

Pasul1. Se scrie matricea de adiacen APasul2. Se calculeaz matricea drumurilor DPasul3. 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 ( ) ( )

2

1

1

=

=

nnxp

n

i

i atunci graful nu are drumuri hamiltoniene

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 Kaufmann

Pasul 1. Construim matricea latin L asociat grafului, unde:lij = ( )( ) ji

jijix,xarculaexistnuadac0 x,xarculaexistadacxx

((

((

Pasul 2. Construim matricea L~ , definit prin:ijl

~=

( )( )

ji

jij

x,xarculaexistnuadac0x,xarculaexistadacx

((

((

numitmatricea latin redus.

Pasul 3. Se calculeaz succesiv matricile:L2 = L L L

~, L3 = L2 L L

~, ..., Lk+1 = Lk L L

~, ...

132

8/3/2019 33Grafuri

23/38


folosind operaiile de nmulire i adunare latin, alfabetul fiind mulimea nodurilor grafului, undeoperaia de nmulire este uor modificat, produsul dintre dou elemente ale matricilor fiind 0, dacunul 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 delungime 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 poatefi completat pn la un circuit (adic dac exist n graf arcul care unete nodul final cu celiniial);

Pasul 5. Dac se dorete i drumul (sau circuitul) de valoare optim (maxim sau minim) secalculeaz suma valorilor pentru fiecare drum i/sau circuit i se alege cel cu valoareaoptim.

n concluzie, metoda nmulirii latine (A. Kaufmann J. Melgrange) determin toatedrumurile 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 deaplicat n grafuri cu un numr mare de noduri. n acest caz este preferabil s se construiasc grafulcondensat, s se determine drumurile hamiltoniene n fiecare n parte cu algoritmul lui Kaufmann iapoi, ca la algoritmul lui Foulkes, s se caute drumurile hamiltoniene n graful iniial.

D. Un algoritm bazat pe algoritmul ungar

Fie G = (X,U) un graf orientat cu n noduri X = {x1, x2, , xn}.

Pasul 1. Se construiete graful bipartit H = (AB,V) n care A = B = X i V = U (adic am folositpentru G reprezentarea prin coresponden).

Pasul 2. Se gsete pentru graful H cuplajul maxim de valoare minim.Pasul 3. Se construiete graful parial al lui G format doar cu arcele cuplajului gsit. Este uor de

demonstrat c, componentele tare conexe ale acestuia sunt toate nite circuite. Dac s-aformat un singur circuit acesta este circuitul hamiltonian de valoare minim. Dac s-auformat mai multe se trece la pasul 4.

Pasul 4. Pentru fiecare arc aflat pe circuitul de lungime minim (dac sunt mai multe se iau nconsiderare arcele tuturor) se reia algoritmul de la pasul 1 pentru graful parial rezultat dinG prin eliminarea acestui arc.

Pasul 5. Pentru fiecare graf parial se continu procedeul pn se ajunge la unul din cazurile:Cazul1.Cuplajului maxim gsit i corespunde un singur circuit. Dac acest circuit

este primul obinut atunci valoarea sa i se atribuie unei variabile Z icircuitul este pstrat. Dac nu este primul atunci valoarea sa se compar cuZ i, dac este mai mic, ea devine noua valoare a lui Z i circuitul se

pstreaz, eliminndu-l pe cel corespunztor fostei valori a lui Z. n cazcontrar se trece la alt graf parial neanalizat nc.

Cazul2.Cuplajul maxim are o valoare mai mare dect Z. Pentru acest graf parial seabandoneaz ramificarea.

133

8/3/2019 33Grafuri

24/38


Pasul 6. Se continu analiza grafurilor pariale pn sunt analizate toate ramificaiile. Valoarea Zfinal este valoarea circuitului de valoare minim iar circuitul corespunztor este celoptim.

Analiza de mai sus poate fi schematizat printr-un arbore de tipul:

n care fiecare nod este un graf parial de analizat, iar pentru fiecare arc, nodul inferior este un grafparial care provine din graful corespunztor nodului superior, prin suprimarea unui arc de pecircuitele de lungime minim corespunztoare cuplajului maxim de valoare minim al acestuia.

Observaie: Algoritmul asigur gsirea circuitului de valoare minim iar n cazul n carealgoritmul lui Foulkes nu funcioneaz este o alternativ mai bun dect algoritmul lui Kaufmann.Totui el nu lucreaz n timp polinomial i n unele cazuri (de exemplu cazuri n care se formeazfoarte multe cicluri cu lungime minim) necesit un numr imens de calcule.

n aceste cazuri se pot folosi metode euristice prin care se elimin din start o serie de arce,considerate a avea valori prea mari pentru a se putea afla pe circuitul hamiltonian de valoareminim, apoi se aplic n graful parial rmas unul din algoritmii de mai sus.

134

8/3/2019 33Grafuri

25/38


8. Drumuri optime ntr-un graf

n marea majoritate a problemelor care pot fi modelate prin grafuri nu ne intereseaz numaidac exist sau nu legturi ntre componentele reprezentate prin nodurile grafului ci i intensitateaacestora. 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.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 (x i,xj) cuv(xi,xj) sau cu vij. n aceste condiii putem enuna problema drumului optim astfel:

" Dat un graf G = (X,U) i o funcie care asociaz fiecrui arc o valoare real, s segseasc, pentru o pereche dat de noduri, drumul (drumurile) de valoare optim (minim sau/imaxim) ntre cele dou nodurii valoarea acestuia (acestora)"

Deoarece este vorba de gsirea minimului unei mulimi de numere reale, prima ntrebarecare se pune este dac aceasta admite minim. Dac mulimea nodurilor grafului este infinit atuncipot exista o infinitate de drumuri elementare distincte ntre cele dou noduri i mulimea valoriloracestora poate avea orice form (nchis sau nu, mrginit sau nu) devenind foarte greu decaracterizat cazurile cnd minimul dorit exist. Deoarece totui majoritatea covritoare a

problemelor economice se modeleaz prin grafuri cu numr finit de noduri, ne vom limita ncontinuare doar la acestea.

Un numrfinit 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!=

1-n

1kk!

1). Deoarece oricrui drum d i

corespunde un drum elementarde(obinut prin eliminarea tuturor subcircuitelor lui d) putem calculavaloarea oricrui drum ca sum ntre valoarea drumului elementar corespunztor i valorile unorsubcircuite ale sale, fiecare nmulit cu numrul de parcurgeri ale circuitului respectiv.

n concluzie, dac exist un circuit de valoare negativ nseamn c exist drumuri devaloare orict de mic (cele care conin acest circuit), obinut prin parcurgerea acestuia de oricteori dorim) i, deci, mulimea valorilor drumurilor este nemrginit inferior, neexistnd drum devaloare minim. Dac exist un circuit de valoare pozitiv atunci exist drumuri de valoare orict demare i mulimea valorilor drumurilor este nemrginit superior, neexistnd drum de valoaremaxim.

Dac nu exist circuite de valoare negativ atunci valoarea oricrui drum este mai mare sauegal 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 circuitede valoare pozitiv atunci valoarea oricrui drum este mai mic sau egal cu a drumului elementar

135

8/3/2019 33Grafuri

26/38


corespunztor, deci drumul de valoare maxim (dac exist) va fi un drum elementar. Cummulimea 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 valoareminim.

Obs. 1. Dac n graf nu exist dect arce de valoare negativ atunci exist drum de valoaremaxim.

Obs. 1. Dac n graf nu exist circuite atunci existi drum de valoare minimi drum devaloare 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 suntincidente spre interior ( noduri n care toate arcele "intr" sau, altfel spus, noduri din carenu "pleac" nici un arc).

Pasul 2. Se gsesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealaltextremitate n A (noduri din care se poate "ajunge" doar in A). Dac nu exist nici unastfel de arc se trece la pasul 4.

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 aurmas noduri n afara lui A atunci graful conine circuite.

Algoritmi de gsire a drumului optim

Din cauza varietii nelimitate a grafurilor posibile, nu exist un algoritm care s rezolveorice 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. Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);2. Algoritmi prin ajustri succesive: (Ford);3. Algoritmi prin inducie (Dantzig);4. Algoritmi prin ordonare prealabil a vrfurilor grafului;5. Algoritmi prin extindere selectiv (Dijkstra).n continuare vom prezenta trei dintre aceti algoritmi.

A. Algoritmul lui Bellman - Kalaba

Algoritmul se aplic n grafuri finite care nu au circuite de valoare negativ (pentru oproblem de minim) sau care nu au circuite de valoare pozitiv (ntr-o problem de maxim) igsete 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 nodurivom aplica algoritmul, pe rnd, pentru fiecare nod al grafului.

Fie G = {x1, x2, ... ,xn} un graf orientat finit. Presupunem (fr a restrnge generalitatea, cam 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 alegrafului ale crei elemente sunt:

136

8/3/2019 33Grafuri

27/38


mij =

+

=

)x,(xarculexistanudacamaxim)deproblemao-(ntrminim)deproblemao-(ntr

jidaca0

jisi)x,(xarculexistadaca)x,(xarculuivaloarea

ji

jiji

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 , (m

n1,kmin

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

sau Lij = max (Li-1,j , (mn1,k

max=

jk+ Li-1,k)) ntr-o problem de maxim

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. 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

, ..., care formeaz drumul cutat, unde = x1k

x ,2k

xrk

x1k

x j, = xrkx ni 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, prinnecesitatea 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 ianalizat.Exemplu: Presupunem dat graful orientat de mai jos, n care se dorete gsirea drumului de valoareminim de la nodul x1 la nodul x9.

x5 9

8

86 7

34

9

7

52

2

33

5

4

83

79

x9

x8

x4

x7

x3

x6

x1

x2

Matricea M va fi

0704860

5089230728

30930

970540

137

8/3/2019 33Grafuri

28/38


iar dup calcularea liniilor Li obinem:

x1 x2 x3 x4 x5 x6 x7 x8 x9x1 0 4 5 x2 0 7 9

x3 0 3 9x4 0 3x5 8 2 7 0 3 2 9 x6 8 0 5 x7 0 6 8x8 4 0 7x9 0L1 9 3 8 7 0L212 6 3 10 13 8 7 0L3 15 12 6 3 8 13 8 7 0

L4 13 12 6 3 8 13 8 7 0L5 13 12 6 3 8 13 8 7 0

Deoarece L4 = L5 oprim calcularea liniilor dup calcularea liniei 5. n aceast linie se aflvalorile celor mai scurte de la toate nodurile la nodul x9. Drumul dorit de noi (x1 x9) are valoareadat 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 simplificat

Algoritmul lui Ford simplificatse aplic doar n grafuri care nu admit circuite. Cu ajutorullui se gsete drumul de valoare optim ntre dou noduri fixate xi i xj. Printr-o eventualrenumerotare a nodurilor putem presupune c nodul de la care pornete drumul este x1, care va finumit 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) = 0Pasul 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 nodurilemulimii A, acestea se adaug la m limea A, cu valoarea:u

w(xi) =

( )

) ))ijjx,x

xx,xvxwmin

ij

j+

, n problemele de minim

138

8/3/2019 33Grafuri

29/38


sau w(xi) =

( )

) ))ijjx,x

xx,xvxwmax

ij

j+

, n problemele de maxim

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 segsesc nodurile , ..., care formeaz drumul cutat, unde = x

1kx ,

2kx

rkx

1kx n,

xrk

x =

1i fiecare alt indice ki+1 este cel pentru care:

w( ) + v( x , x ) = w( ) STOP1ik

x+ 1ik+ ik ik

x

Dac xn A se reia algoritmul de la pasul 3.Exemplu: Pentru acelai grafi aceeai pereche de noduri din exemplul rezolvat cu algoritmul luiBellman-Kalaba vom avea succesiv:

pas1: w(x1) = 0pas2: A = {x1}pas3: Nodurile n care se poate ajunge doar din x1: {x5}

w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5pas4: x9 Apas3: A = {x1,x5} i nodurile n care se poate ajunge prin arce directe doar din x1i x5 sunt: {x6}

w{x6) = min( w(x1) + v(x1,x6), w(x5) + v(x5,x6)) = min(0 + 3 , 5 + 3) = 3pas4: x9 A

pas3: A = {x1,x5,x6} i nodurile n care se poate ajunge prin arce directe doar din x1, x5i 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) = 4w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7

pas4: x9 Apas3: 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) = 7w{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, x7i 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 Apas3: 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, x7i 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) = 13pas4: 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)

139

8/3/2019 33Grafuri

30/38


w(x5) = w(x1) + v(x1,x5)deci drumul cutat este: x1 x5 x3 x4 x9

Observaia 1. Dac graful are un circuit atunci se poate demonstra uor c nu vom putea davaloare nici unui nod al acestuia i dac exist vreun drum de la x1 la xn care trece prin unul dinnodurile 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, pentrufiecare nod, a nodurilor spre care "pleac" arce din acesta i valorile acestor arce, fiind mult maiuor de aplicat sau implementat pe calculator. El are ns dezavantajul c se poate aplica doar ngrafuri fr circuite.

C. Algoritmul Ford generalizat

Algoritmul lui Ford generalizat a fost creat cu scopul de a putea gsi drumul optim i ngrafurile care au circuite. Cu ajutorul lui se gsete drumul de valoare optim ntre dou nodurifixate 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 nodfinal.Algoritmul este:

Pasul 1. I se d vrfului iniial valoarea 0 (zero): w(x0) = 0 i tuturor celelalte valoarea + (ntr-oproblem de minim) sau - (ntr-o problem de maxim).

Pasul 2. n ordinea cresctoare a indicilor nodurilor se calculeaz pentru fiecare nod, pe bazfostelor valori, noile valori cu formula:

w*(xi) = n problemele de minim( )

( )

( ) ( )(

+

ijj

x,x

xix,xvxwmin,xwmin

ij

j)

)sau w*(xi) = n problemele de maxim( )( )

( ) ( )(

+

ijj

x,xxi

x,xvxwmax,xwmax

ij

j

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) dela x1 la xn. Pentru gsirea acestui drum se pornete napoi de la nodul final xni

se gsesc nodurile , ..., x care formeaz drumul cutat, unde = x1kx , 2kx rk 1kx n,= x

rkx 1i fiecare alt indice ki+1 este cel pentru care:

w( ) + v( , ) = w( ) STOP1ik

x+ 1ik

x+ ik

xik

x

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 mailent dect cel simplificat. Pentru scurtarea duratei de execuie se poate modifica algoritmul n sensulc 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.

140

8/3/2019 33Grafuri

31/38


D. Algoritmul lui Dijkstra

n 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 nodurileanalizate. Acest fapt duce la un consum inutil de timp, deoarece foarte multe din aceste noduri nuvor 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 vorforma efectiv drumul optim. n plus, algoritmul se poate aplica i n drumuri cu circuite. Ca unminus 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) = 0Pasul 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 de la noduri din A(nu doar de la nodurile mulimii A, ca la algoritmul lui Ford simplificat) secalculeaz pentru toate acestea:

w(xi) =

( )

) ))ijjx,x Ax

x,xvxwmin

ijj

+

n problemele de minim

dar, spre deosebire de algoritmul lui Ford simplificat, se adaug la mulimea A doarcel 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 segsesc nodurile , ..., care formeaz drumul cutat, unde = x

1kx ,

2kx

rkx

1kx n,

xrk

x =

1i fiecare alt indice ki+1 este cel pentru care:

w( ) + v( x , x ) = w( ) STOP1ik

x+ 1ik + ik ik

x

Dac xn A se reia algoritmul de la pasul 3.

Exemplu Vom aplica algoritmul la acelai graf folosit la ceilali algoritmi, pentru a puteaface 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 = 4w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5w{x6) = min( w(x1) + v(x1,x6)) = 0 + 3 = 3min(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) = 4w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5

w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 8min(w{x2),w{x5),w{x7)) = w{x2) = 4

pas4: x9 A141

8/3/2019 33Grafuri

32/38


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) = 11w{x4) = min( w(x2) + v(x2,x4)) = min(2 + 9) = 11w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 0

min(w{x3),w{x4),w{x5),w{x7)) = w{x5) = 5pas4: x9 Apas3: A = {x1,x2,x5,x6} i nodurile n care se poate ajunge prin arce directe din x1, x2, x5, x6i x7

sunt: {x3,x4,x7,x8} w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7w{x4) = min( w(x2) + v(x2,x4), w(x5) + v(x5,x4)) = min(4 + 9,5 + 7) = 12w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7w{x8) = min( w(x5) + v(x5,x8)) = min(5 + 9) = 14min(w{x3),w{x4),w{x7),w{x8)) = w{x3) = w{x7) = 7

pas4: x9 Apas3: 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) =10w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13w{x9) = min( w(x3) + v(x3,x9), w(x7) + v(x7,x9)) = min(7 + 9,7 + 8) = 15min(w{x4),w{x8),w{x9)) = w{x4) = 10

pas4: x9 Apas3: 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)=13w{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) = 13pas4: 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

142

8/3/2019 33Grafuri

33/38


9. Reele de transport

ntr-o mare varietate de situaii concrete din practica economic se pune problema deplasriiunei 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 delegtur. 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, aaltorpuncte 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 oricedestinaie s poat fi aprovizionat de mai multe surse.

Aprovizionarea destinaiilor se poate face direct de la surse sau prin intermediul altorpuncte, numite puncte intermediare. n cazul cel mai general pot exista de asemenea legturi ntresurse i/sau legturi ntre destinaii.

Aa cum s-a vzut i la problema de transport, situaia de mai sus este un cadru extrem delarg, 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 (inferiorsau superior), destinaiile au un necesar sau o putere de absorbie limitat inferior sau superior iar pefiecare rut se poate transporta doar o cantitate cuprins ntre anumite limite.

Pentru studiul matematic al acestei situaii vom da definiiile matematice ale obiectelorimplicate n problemi ipotezele modelului.

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

1. Existi este unic s X a.. , (din care doar "ies" arce), numitintrarea reelei de transport;

+

sU =sU

2. Existi este unic t X a.. = ,+tU tU (n care doar "intr" arce) numitieirea reelei de transport;

3. S-a definit o funcie c: U R+ care asociaz fiecrui arc u un numr strictpozitiv cu numit capacitatea arcului.

Observaie: Este clar c exemplele obinuite au doar rareori o singur sursi 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" cteun arc spre fiecare surs (i numai spre acestea), iar capacitile acestor arce vor fiegale 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 arcevor fi egale cu necesarurile destinaiilor corespunztoare;

Definiia 2: Se numete flux ntr-o reea de transport R = (X,U) o funcie : U R+ careare urmtoarele proprietile:

P1.0 u cu oricare ar fi u din U; valoarea u se numete flux al arcului uP2. 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 excepianodului iniial i al celui final.

+

=

ii Uu

u

Uu

u

143

8/3/2019 33Grafuri

34/38


Definiia 3: Se numete valoare a fluxului suma fluxurilor arcelor care "pleac" din noduliniial s i se noteaz cu .

Observaie: Se poate demonstra uor c aceast valoare este egal i cu suma fluxurilorarcelor care "intr" n nodul final t. n concluzie avem:

= + = ts Uuu

Uu

u

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

Definiia 4: Se numete flux de valoare maxim ntr-o reea un flux n aceast reea, cuproprietatea 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. Putem transporta ntreaga cantitate necesar la destinaii?2. Dac da, cum transportm efectiv aceast cantitate de la surse la destinaii?3. Dac nu, din ce motiv nu putem realiza acest transport?4. Cum putem nltura cu eforturi minime acest motiv?

Rspunsul la primele dou ntrebri se poate afla prin gsirea fluxului de valoare maximicompararea 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 afluxului.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 trecereprin reea. Dac vrem, deci, s mrim fluxul va trebui s lrgim tocmai acest cel mai ngust loc detraversare al reelei.

Pentru formalizarea consideraiilor de mai sus vom introduce noiunea de tietur ntr-oreea:

Definiia 5: Dat o reea de transport G(X,U) cu s = nodul iniial i t = nodul final, senumete 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 osubmulime din noduri ntr-o parte, nodul final cu restul nodurilor n cealalt parte i reteaz toatearcele 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 sconin 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 transportG(X,U), notat C(T), suma capacitilor tuturor arcelor care au extremitatea iniial n V i ceafinal n W.

144

8/3/2019 33Grafuri

35/38


C(T) =( )

=

WxVxx,xu

u

ji

ji

c

Pentru a nu exista nici o ambiguitate, insistm asupra faptului c se vor lua n consideraredoar 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 aceastreea, 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:

=( )

=

WxVxx,xu

u

ji

ji

( )

=

VxWxx,xu

u

ji

ji

sau, altfel spus, valoarea unui flux oarecare este egal cu suma fluxurilor arcelor care trec de la V laW 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:

= =

( )

= Xx xs,u

u

jj

( )

= Xx xs,u

u

jj

+ =

+sx Vx Uu

u

Uu

u

ii ixix

= ( )( )

=

VxVxx,xu

uu

ji

ji

+( )

=

WxVxx,xu

u

ji

ji

-( )

=

VxWxx,xu

u

ji

ji

=( )

=

WxVxx,xu

u

ji

ji

( )

=

VxWxx,xu

u

ji

ji

Corolar: ntr-o reea de transport valoarea oricrui flux este mai mic sau egal dect valoa-

rea oricrei tieturi.

Demonstraie: Fie T o tietur oarecare i un flux oarecare. Avem succesiv:

= ( )

=

WxVxx,xu

u

ji

ji

( )

=

VxWxx,xu

u

ji

ji

( )

=

WxVxx,xu

u

ji

ji

( )

=

WxVxx,xu

u

ji

ji

c = C(T)

Corolar: ntr-o reea de transport valoarea fluxului maxim este mai mic sau egal dectvaloarea tieturii minime.

Demonstraia e evident. n plus, din cele de mai sus se vede c egalitatea are loc numaidac, pentru tietura minim, exist un flux pentru care toate arcele de la V la W sunt folosite lamaxim (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 decapacitate egal cu valoarea fluxului.

145

8/3/2019 33Grafuri

36/38


Demonstraie: Fie un flux maximal. Introducem urmtorul procedeu de marcare avrfurilor:

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

, ..., unde = s, = t i marcajul oricrui vrf este + sau

Adugnd la fluxul fiecrui arc al lanului de tipul (x ,x ) valoarea:1k

x ,2k

xrk

x1k

xrk

x1ik

x+ ik

xik

x .

ik 1ik+

= min(( ) 1ii1ii1ikik

kkkkx,x

x,xx,xcmin++

+

,( ) 1iiik1ik

kkx,x

x,xmin+

+

)

i scznd din fluxul fiecrui arc de tipul ( x , ) aceeai valoare , obinem un flux de valoare

+ , deci fluxul nu ar fi maximal.1ik + ik

x

n concluzie vrful t nu va fi marcat. Fie tietura T = (V,W), unde V este format dinmulimea nodurilor marcate iar W din cele nemarcate. n acest caz, pentru fiecare arc (xi,xj) care"traverseaz" tietura avem:

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 marcatn acest caz avem: C(T) =

( )

=

WxVxx,xu

u

ji

ji

c =( )

=

WxVxx,xu

u

ji

ji

( )

=

VxWxx,xu

u

ji

ji

=

i teorema e demonstrat.

Teorema lui Ford-Fulkerson poate stabili doar valoarea fluxului maxim dar nu d o metodde gsire a acestuia. Pentru a rezolva problema gsirii fluxului de valoare maxim se poate folosialgoritmul 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 = ( )uuDu

cmin

i se adaug la fluxul de pe fiecare arc al

146

8/3/2019 33Grafuri

37/38


drumului. Arcul(arcele) unui drum D pentru care s-a obinut valoarea minimD va fidup 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 sepoate 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 sdea pentru fiecare reea fluxul maxim, n urma procedeului de mai sus, fie prin redistribuireajudicioas 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 (adictoate 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 niciun vrf;

Pasul 7. Dac nodul final a fost marcat atunci fluxul este maxim i algoritmul se oprete, n cazcontrar trecndu-se la pasul 8;

Pasul 8. Construim un lanul L = , , ..., unde = s, = t i marcajul oricrui vrfeste +x sau . Se calculeaz:

1kx

2kx

rkx

1kx

rkx

1ikx

+ ik ikx

L = min(( ) 1ii1ii1ikik

kkkkx,x

x,xx,xcmin++

+

,( ) 1iiik1ik

kkx,x

x,xmin+

+

)

care se adaug la fluxul fiecrui arc al lanului de tipul ( ) i se scade din

fluxul fiecrui arc de tipul ( , . ikx ,

1ikx

+1ik

x+ ik

x )

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 poateca creterea fluxului la fiecare iteraie s se fac cu cantiti din ce n ce mai mici astfel nct sumalor s nu ating niciodat marginea superioar dat de valoarea tieturii minime, algoritmul avnd oinfinitate 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 luiFord-Fulkerson are un numr finit de pai.

Demonstraie Prin nmulirea tuturor acestor capaciti cu cel mai mic multiplu comun alnumitorilor se obine o reea cu toate capacitile numere naturale. innd cont de formula decalcul, la fiecare iteraie cantitatea adugat va fi numr natural i cum valoarea fluxului maximeste mrginit de capacitatea tieturii minime Cmin, care este de asemenea numr natural, algoritmulva 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 iteraiiale algoritmului, fa de capacitatea tieturii minime. Aceast valoare poate fi ns, n anumite

147

8/3/2019 33Grafuri

38/38


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

algoritmul va avea cel mult2

1mn iteraii, unde n = numrul de noduri iar m = numrul de muchii.

Observaia 3. Exist probleme n care se dorete gsireafluxuluiminim ntr-o reea, valorilefluxului pe arce fiind limitate inferior de capacitile acestora. n acest caz se aplic de asemeneaalgoritmul lui Ford-Fulkerson astfel:

Pasul 1. Se calculeaz M = maximul capacitilor arcelorPasul 2. Se construiete reeaua R', care este fosta reea, n care au fost modificate doar

capacitile arcelor, acestea devenind uc = M cuPasul 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: 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 asociazi costuri unitare de parcurgere, putem cuta fluxu

33grafuri

Documents