algoritmica grafurilor sinteza

8/8/2019 algoritmica grafurilor sinteza

1/31

1

ALGORITMICA GRAFURILOR Conf. Univ. Dr.Silviu Brz

I. INTRODUCERE N TEORIA GRAFURILOR 1.1.Grafuri neorientate

Definiie. Fie X o mulime finit i nevid i { }{ }, ,U x y x y X . Numim graf ( sau graf neorientat ) perechea ( ),G X U = . Eelemente din mulimea X se numescnoduri sau vrfuri , iar elementele din mulimeaU poart numelede muchii ale grafului.

Un graf se reprezint grafic printr-o mulime de puncte corespunztoarevrfurilor grafului i o mulime de segmente corespunztoare muchiilor. Dac pentru un graf exist o reprezentare n care s nu existe dou segmente care s seintersecteze, atunci spunem c graful reprezentat este un graf planar .

Pornind de la definiie observm c dac X are n elemente, atunciU are

cel mult 2nC elemente.Dac A este o mulime, vom nota prin A numrul de elemente ale

mulimii.Definiie. Fie ( ),G X U = un graf i x X un nod fixat. Prin gradul

nodului nelegem numrul muchiilor incidente lui x i notm acest numr cu( )d x . Dac ( ) 1d x = spunem c estenod terminal . Dac ( ) 0d x = spunem

c x estenod izolat .Propoziia 1. Fie ( ),G X U = un graf n care U m= . Atunci

( ) 2 x X

d x m

=

.

Propoziia 2. Pentru orice graf ( ),G X U = , numrul vrfurilor de grad impar este par.

Definiie. Fie ( ),G X U = un graf.. Numim graf parial al lui G, graful ( ),G X V = , undeV U .

Definiie. Fie ( ),G X U = un graf. Numimsubgraf n G, graful

( ),G Y V = , n careY X , iar { }{ }, ,V x y U x y Y = .


2/31


3/31

3

1.2.Grafuri orientate

Definiie. Fie X o mulime finit i nevid. Numim graf orientat (digraf ) orice pereche ( ),G X U = n care U X X este o mulime finit de perechiordonate cu componente din X (U este o relaie binar pe X ).

Elementele mulimii X vor fi numitevrfuri sau noduri . ElementelemulimiiU se numescarce .

Orice arc are forma( ),a b , n carea se numeteextremitate iniial , iar b se numeteextremitate final a arcului( ),a b .

Un graf orientat se reprezint grafic printr-o mulime de punctecorespunztoare vrfurilor i printr-o mulime de segmente orientate (sgei)

corespunztoare arcelor..O sgeat este orientat de la extremitatea iniial spreextremitatea final a arcului pe care l reprezint.

Dac ( ),u x y U = spunem c x i sunt adiacente n G i cnodurile x i y suntincidente arculuiu sau c arculu este incident nodurilor i . Mai exact, spunem cu esteincident exterior nodului (u pleac sau iese

din ) i cu este incident interior nodului y (u ajunge sau intr n y). Arcul( ), x y U se mai noteaz i prin xy.Definiie. Fie ( ),G X U = un graf orientat i X un nod fixat.

a) Numim grad interior al lui , numrul arcelor incidente interior lui ,adic mrimea ( ) ( ){ },d x y x U y X = .

b) Numim grad exterior al lui , numrul arcelor incidente exterior lui ,adic mrimea ( ) ( ){ },d x x y U y X + = .

c) Prin gradul nodului nelegem numrul total al arcelor incidente lui ,

adic mrimea ( ) ( ) ( )d x d x d x += + .d) Dac ( ) 0d x = spunem c x X estevrf izolat . e) Dac ( ) 1d x = i ( ) 0d x+ = spunem c X estevrf terminal ; dac

( ) 0d x = i ( ) 1d x+ = spunem c x X estevrf iniial .Definiie. Fie ( ),G X U = un graf orientat i A X o mulime de

vrfuri.a) Gradul interior lui A este numrul arcelor ce intr n A i care au nodul

iniial n afara lui A , adic mrimea( ) ( ){ }, ,d A y x U y A x A = .


4/31

4

b) Gradul exterior lui A este numrul arcelor ce ies din A i au nodul terminal n afara lui A , adic mrimea

( ) ( ){ }, ,d A x y U x A y A+ = .c) Gradul total al lui Aeste ( ) ( ) ( )d A d A d A += + .

Observaii.1) Evident, pentru orive A X avem ( ) ( )

x A

d A d x

, deoarece s-ar putea ca anumite arce care ies din A s aib extremitatea final tot n A,arce care nu se numr la determinarea valorii( )d A+ .

2) Evident, pentru orive A X avem ( ) ( ) x A

d A d x+ +

, deoarece s-ar putea ca anumite arce care intr n A s aib extremitatea iniial tot n A,arce care nu se numr la determinarea valorii( )d A .Din 1) i 2) rezult c ( ) ( )

x Ad A d x

. Definiie. Fie ( ),G X U = un graf orientat. Numim graf orientat parial

al lui G graful orientat ( ),G X V = n care V U .Un graf orientat parial al luiG se obine prin suprimarea anumitor arce

ale luiG .Definiie. Fie ( ),G X U = un graf orientat. Numimsubgraf orientat al

lui G , graful orientat ( ), H Y V = n care Y X , iar ( ){ }, ,V x y U x y Y = (mulimea tuturor arcelor luiG cu ambele extremiti nY ).

Un subgraf orientat se obine suprimnd anumite vrfuri dinG ieliminnd toate arcele incidente vrfurilor suprimate.

Definiie. Fie ( ),G X U = un graf orientat. Dac pentru orice, y X avem( ), y U sau ( ), y x U spunem c G este graf orientat complet .

Un graf orientat complet cun vrfuri se notean cu n K .Observaie. n cazul grafurilor neorientate, pentru unn , 2n ,

exist un singur graf complet cun vrfuri, notat n K . n cazul grafurilor orientate pentru unn , 2n dat, exist mai multe grafuri orientate complete cun vrfuri, ele diferind fie prin orientarea arcelor, fie prin numrul de arce ce unescdou vrfuri, numr ce poate fi 1 sau 2.


5/31

5

Definiie. Fie ( ),G X U = un graf orientat. Numimdrum n G o succesiune de vrfuri ( )0 1, ,..., r d x x x= astfel nct pentru orice 0,1,..., 1i r = ,

1i i x x U + (sau o succesiune de arce care au acelai sens, ( )1 1, ,..., pd u u u= , cu proprietatea c pentru orice 1,2,..., 1i p= , iu i 1iu + au o extremitate comun,mai exact extremitatea final a luiiu coincide cu extremitatea iniial a lui1iu + .

Fie ( )0 1, ,..., r d x x x= un drum n graful ( ),G X U = . 0 x se numeteextremitatea iniial , iar r extremitatea final a drumuluid .

Definiie. Drumul ( )0 1, ,..., r d x x x= din graful ( ),G X U = se numeteelementar dac pentru orice , 0,1,...,i j r = , i j , avem i j x (drumul trece prin noduri distincte).

Definiie. Fie ( ),G X U = un graf orientat. Numimlan n G , o secven de noduri [ ]0 1, ,..., r L x x x= cu proprietatea c pentru orice 0,1,..., 1i r = avem( )1,i i x x U + sau ( )1,i i x U + ( sau o succesiune de arce

1 2, ,..., p L u u u = astfel nct pentru orice 1,2,..., 1i p= , arcele iu i 1iu + auo extremitate comun - nu se mai pune condiia ca arcele s aib acelai sens, cala drumuri).

Observaie.Din definiie rezult imediat c orice drum este ntr-un graf orientat este n acelai timp i lan n graful orientat respectiv.

Definiie. Fie ( ),G X U = un graf orientat. Pentru orice , y X spunem c y este accesibil din x sau y este atins din x dac i numai dac exist ( )0 1, ,..., r d x x x= un drum de capete i y ..

II.TIPURI PARTICULARE DE GRAFURI

Definiie.Se nume temultigraf un graf neorientat n care cel puin dou vrfuri sunt unite prin muchii multiple.

Definiie.Graful orientat ( ),G X U = se numetereflexiv (nereflexiv,simetric, antisimetric, total, tranzitiv ) dac i numai dac relaia binar U esterelaie binar reflexiv (nereflexiv, simetric,antisimetric, total, tranzitiv ).

Definiie. Fie ( ),G X U = un graf orientat. Dac pentru fiecare x X se asociaz o etichet pentru identificare spunem c G este un graf orientat etichetat .


6/31

6

Observc c la toate grafurile de mai sus un folosit o numerotare avrfurilor. Numerele folosite pot fi considerate etichete pentru vrfuri i astfelgrafurile pot fi considerate drept grafuri etichetate.

Definiie. Fie ( ),G X U = un graf orientat.G se numete graf orientat marcat sau reea dac fiecrui u U i se asociaz o marc um . n acest caz,U X M X , fiind mulimea mrcilor asociate arcelor. Dac

( ), , x m y X M X , atunci arcul y se marcheaz cu m i se reprezint

prin m x y . Definiie. Numimreea etichetat un graf orientat marcat i etichetat. De fapt, graful din exemplul anterior, avnd vrfurile numerotate i

muchiile marcate poate fi considerat i un exemplu de reea etichetat.

2.1.Grafuri conexe

Definiie.Graful neorientat ( ),G X U = se numeteconex dac i numaidac oricare ar fi dou noduri , y X , x y , exist cel puin un lan nG ,

( )0 1, ,...,

r L x x x= de extremiti i y .

Definiie. Fie ( ),G X U = un graf neorientat. Numimcomponentaconex a lui G , un subgraf conex ( ),C Y V = al su, i pentru orice Y , subgraful obinut lund mulimea de vrfuri{ }\Y x nu este conex( subgraful C estemaximal n raport cu proprietatea de conexitate).

Fie ( ),G X U = un graf neorientat. Pentru, x y X spunem c x esteconectat cu y dac exist un lan ce le unete, adic exist un lan

( )0 1, ,..., r L x x x= de extremiti i y Pe mulimea X definim relaia binar~ X X , dat prin ~ y dac

i numai dac ( x y= sau este conectat cu ).Propoziia 1. Relaia " ~ " definitmai sus este o relaie de echivale Propoziia 2. Fie ( ),G X U = un graf n care X n= , U m= i 2n .

Dac G este conex, atunci 1m n . Noiunea de graf conex este valabil i pentru grafurile orientate.

Definiia este urmtoarea:Definiie.Graful orientat ( ),G X U = se numeteconex dac i numai

dac oricare ar fi dou noduri , y X , x y , exist cel puin un lan nG ,( )0 1, ,..., r L x x x= de extremiti i y .


7/31

7

Dac n definiia grafului conex pentru grafuri orientate nlocuimcondiia de existen a unui lan cu cea de existen a unui drum se onineurmtoarea noiune.

Definiie.Graful orientat ( ),G X U = se numetetare conex dac inumai dac oricare ar fi dou noduri, y X , y , exist cel puin un drum nG , ( )0 1, ,..., r d x x x x y= = = de extremiti i y .

O posibilitate de a determina dac un graf neorientat este conex, saudeterminarea efectiv a componentelor conexe (sau problemele similare pentru grafurile orientate) const n aplicarea unui algoritm de tip greede.

S considerm nti problema determinrii conexitii unui graf neorientat ( ),G X U = .

Algoritm 1. 1. Se consider Y X = , V U = i se alege orice x X pentru care

considerm { } B x= .2. Dac B= , atunci algoritmul se termin genernd un rspuns

astfel :a. Dac V = , atunci graful este conex b. Dac V , atunci graful nu este conex (n plus se poate

spune c mulimea \ X Y reprezint componenta conex dincare face parte i nodul x considerat la1).

Altfel se continu .3. Se alege orice B .4. Pentru fiecare \Y B astfel nct { }, z V considerm

{ } B B z = i { }{ }\ ,V V y z = 5. Considerm { }\ B B y= i relum de la2.

Aa cum se vede din pasul 2, algoritmul prezentat d rspunsul lantrebarea EsteG un graf conex?. De asemenea, se poate determinacomponenta conex a grafuluiG din care face parte un anumit nodspecificat. Acest lucru creaz premizele realizrii algoritmului dedeterminare a componentelor conexe, plecnd de la algoritmul 1.

Algoritm 2. 1. Se consider Y X = , V U = 0k = . 2. Dac V = , atunci algoritmul se termin i componentele conexe

ale grafului G sunt 1 A , 2 A , ..., k A .Vrfurile care nu sunt n1

k

k i

A=

sunt vrfuri izolate i formeaz fiecare n parte cte o componentconex a grafuluiG (n plus valoarea pentru k arat dac graful


8/31

8

G este sau nu conex. Astfel pentru 1k = i 1 A X = graful esteconex, altfel G nu este conex).

3. Alegem orice x Y . Fie 1k k = + , k A = , { } B x= .4. Dac B= se trece le8 , altfel se continu .5. Se alege orice B . 6. Pentru fiecare \Y B astfel nct { }, z V considerm

{ } B B z = i { }{ }\ ,V V y z = . 7. Considerm { }\ B B y= , { }k k A A y= . Se trece la4.8. Se elimin din V orice muchie{ },a b pentru care , k a b A . Se trece

la 2.

2.2.Grafuri complementare i izomorfe

Definiie. Fie ( ),G X U = un graf neorientat, numimcomplementarul luiG ( graf complementar lui G ), graful ( ),G X U C C = , n care{ }, y U C dac i numai dac { }, x y U .

Definiie. Fie ( ),G X U = i ( ),G X U = dou grafuri neorientate.Spunem c G i G sunt izomorfe , notmG G , dac exist o funcie bijectiv

: f X X astfel nct { }, y U dac i numai dac ( ) ( ){ }, f x f y U .Din definiie rezult c dou grafuri sunt izomorfe dac au acelai numr

de vrfuri i se poat obine unul din cellalt printr-o renumerotare a vrfurilor.Definiii similare celor de mai sus sunt valabile pentru grafurile orientate.

Ele se obin nlocuid muchiile cu arce.Propoziia 3. Fie ( ),G X U = i ( ),G X U = dou grafuri orientate.

AtunciG G dac i numai dac G GC C .

2.3.Grafuri ciclice

Definiie. Fie ( ),G X U = un graf neorientat. Numimciclu n G un lan [ ]0 1, ,..., r L x x x= n care 0 r x= (n care extremitile coincid ).

Definiie. Fie ( ),G X U = un graf neorientat i [ ]0 1, ,..., r L x x x= unciclu. Spunem c L esteciclu elementar dac pentru orice0 , 1i j r , i j ,avem i j x (toate vrfurile sale, exceptnd extremitile, sunt distincte dou cte dou ) .


9/31

9

Definiie. Fie ( ),G X U = un graf neorientat i [ ]0 1, ,..., r L x x x= unciclu. Spunem c L este ciclu simplu daca pentru orice0 , 1i j r , i j ,avem{ } { }1 1, ,i i j j x x x+ + (toate muchiile sale sunt distincte dou cte dou ).

Definiiile de mai sus continu s fie valabile i pentru grafurileorientate. Suplimentar intervin definiiile care urmeaz.

Definiie. Fie ( ),G X U = un graf orientat. Numimcircuit n G un drum( )0 1, ,..., r C x x x= n care 0 r x x= (n care extremitile coincid ).

Definiie. Fie ( ),G X U = un graf orientat i ( )0 1, ,..., r C x x x= uncircuit. Spunem c C este circuit elementar dac pentru orice0 , 1i j r ,i j , avem i j x x (toate vrfurile sale, exceptnd extremitile, sunt distinctedou cte dou ) .

Definiie. Fie ( ),G X U = un graf orientat i ( )0 1, ,..., r C x x x= unciclu. Spunem c C este circuit simplu daca pentru orice0 , 1i j r , i j ,avem( ) ( )1 1, ,i i j j x x x+ + (toate arcele sale sunt distincte dou cte dou ).

Definiie. Graful neorientat ( ),G X U = se numeteciclic dac G conine cel puin un ciclu i se numeteaciclic n caz contrar.

Definiie. Fie ( ),G X U = un graf orientat. Spunem c G este aciclic dac G nu conine nici un circuit iciclic n caz contrar.

Propoziia 4. Fie ( ),G X U = un graf neorientat. Dac U X ,atunci G este ciclic.

Definiie. Fie ( ),G X U = un graf neorientat avnd 1k componenteconexe. Se numete punte n G o muchie m U pentru care graful parial

{ }( ), \G X U m = are numrul de componente conexe mai mare dect k .

Propoziia 5. Fie ( ),G X U = un graful neorientat im U . m este punte, dac i numai dac oricare ar fi ciclul [ ]1 2, ,..., r C m m m= n G dat prinmuchiile sale, im m pentru orice1 i r .

Propoziia 6. Fie ( ),G X U = un graf orientat. G este tare conexdac i numai dac exist un circiut C care conine toare vrfurile grafului.

Definiie. Fie ( ),G X U = un graf orientat. Definim( ) ( ){ }, circuit in cu ,V x y U C G x y C = . Graful parial ( ), H X V =

se numete graful orientat ciclu al lui G .


10/31

10

Propoziia 7. Fie ( ),G X U = un garf orientat i ( ), H X V = graful ciclu al lui G . Fie Y X i ( ),G Y W = subgraf. Atunci G component tare conex n G dac i numai dac G component tare conex n H .

Definiie. Fie ( ),G X U = un graf orientat i 1C , 2C , ..., t C componentele tari conexe ale lui G . Fie { }1 2, ,..., t Y C C C = i

( ) ( ){ }, , cu ,i j i jV C C x C y C x y U Y Y = .Graful ( ), H Y V = se numete graful condensat al lui G .

Observaie. Graful condensat al oricrui graf orientat este aciclic.

4. ARBORI4.1.Definire i proprieti

Definiie. Numimarbore orice graf neorientat conex i fr cicluri. Teorema 1. Fie ( ),G X U = un graf neorientat. Urmtoarele afirmaii

sunt echivalente: 1. G este arbore.2. G este aciclic maximal .3. G este convex minimal .

Corolar. Dac ( ),G X U = este arbore, atunci 1U X = . Propoziie 1. Dac ( ),G X U = este un arbire, atunciG are cel puin

dou vrfuri terminale.

4.2.Arbori pariali

Definiie. Fie ( ),G X U = un graf neorientat i ( ), H X V = un graf parial al luiG . Dac H este arbore spunem c H este unarbore paial (deacoperire sau de traversare ) al lui G .

Observaie.Dac un graf neorientat ( ),G X U = are arbore parial, acestanu este unic.

Definiie. Fie ( ),G X U = un graf neorientat i ( ), A X V = un arbore parial al luiG . Numimcoarde ale lui H elementele mulimii\U V , iar numrul

\U V se numetenumrul ciclomatic al lui G . Teorema 2. Fie ( ),G X U = un graf neorientat.G este conex dac i

numai dac G are arbore parial.


11/31

11

Algoritm 1.1. FieV U = .2. Dac graful ( ), H X V = nu conine cicluri, atunci algoritmul se termin i

H este un arborele parial al luiG , altfel se coninu.3. Se consider un ciclu 1 2, ,..., pC e e e = n H 4. Se alege { }1 2, ,..., pe e e e . Considerm { }\V V e= i mergem la 2.

Propoziia 2. Fie ( ),G X U = un graf neorientat conex. Atunci numrul ciclomatic al luiG este 1U X + .

Propoziia 3. Fie ( ),G X U = un graf neorientat conex, ( ), A X V = unarbore parial al luiG i { },e x y= o coard a lui A. Atunci graful

{ }( ), H X V e= conine exact un ciclu.4.3.Algoritmul lui Kruskal

Problema arborelui parial de cost minim. Fie ( ),G X U = un graf neorientat conex, ( ): 0,c U o funcie, numit funcie cost a muchiilor luiG i ( ), H X V = un graf parial al luiG . Numimcostul lui H suma costurilor tuturor muchiilor dinV , adic valoarea ( ) ( )

u U c H c u

= . Se pune problemadeterminrii nG a unui graf parial conex de cost minim.

Definiie. Fie ( ),G X U = un graf neorientat conex, ( ): 0,c U funcia cost a muchiilor luiG i ( ),cm cmT X V = un arbore parial cu proprietateac pentru orice arbore parial ( ),T X V = avem ( ) ( )cmc T c T . Atunci spunemc cmT estearbore parial de cost minim al lui G .

Teorema 3. Fie ( ),G X U = un graf neorientat conex, ( ): 0,c U funcia cost a muchiilor luiG i ( ), H X V = un graf parial al luiG . Dac H este graf parial conex de cost minim, atunci H este arbore parial de cost minim.

Algoritmul 2. (Kruskal).1. Considerm c ( ) L i i= pentru fiecare 1,2,...,i X = , construim ( )M j ,

. 1,2,..., j U = reprezentnd muchiile luiG n ordinea cresctoare acosturilor, considerm 0k = (pentru numrarea muchiilor selectate) i

1 j = (pentru parcurgerea lui ). FieV =.


12/31

12

2. Dac 1k n , atunci algoritmul se oprete, muchiile din V determin arborele parial de cost minim, altfel se continu .

3. Considerm{ } ( ), p q M j= .4. Dac ( ) ( ) L p L q= , atunci punem 1 j j= + i mergem la 3, altfel se

continu .5. Punem 1k k = + i { }{ },V V p q= .6. Dac ( ) ( ) L p L q< , atunci nlocuim n L toate valorile ( ) L q prin

( ) L p , altfel nlocuim n L toate valorile ( ) L p prin ( ) L q .7. Punem 1 j j= + i mergem la 2.

4.4.Arborescene

Definiie. Fie ( ),G X U = un graf orientat conex i aciclic. Dac exist un unic vrf 0 x X cu ( )0 0d x = i pentru orice X , 0 x avem

( ) 0d x , spunem c G este o arborescen ( sau arbore orientat ). 0 poart numele derdcin a arboresceneiG . Vrfurile pentru care ( ) 0d y+ = senumescvrfuri terminale sau frunze .

Definiie. Fie ( ), A X U = o arborescen cu rdcina0 . Pentru un vrf x X definimnivelul nodului prin ( )0,...,l x x , unde( )0,..., x x este drumul (unic) de extremitate iniial 0 x i extremitate final x.

Definiia de mai sus plasific vrfurile arborescenelor n funcie dedistana lor fa de rdcin. Acest clasificare are ca efect o reprezentare n carenodurile sunt poziionate pe fiecare nivel, cu rdcina arborescenei n parteasuperioar a imaginii.

Pentru o arborescena ( ), A X U = , dac ( ), x y U , spunem c x este printele (tatl ) lui i este fiul (descendentul direct ) lui x. Dac , y X i exist drumul (unic)( )1, ,..., ,k z z y , spunem c y estedescendentul lui x.

Definiie. Fie ( ), A X U = o arborescen. Dac pentru orice x X avem ( ) { }0,1,2d x+ . Spunem c A este oarborescen binar (arbore binar ). Dac ( ) { }0,2d x+ , spunem c A este oarborescen binar complet (arborebinar complet ).

Teorema 4. Pentru orice *n exist ( ), A X U = o arborescen

binar astfel nct


13/31

13

( ){ }0 X d x n+ = = (numrul vrfurilor terminale s fie egal cun ).

Propoziia 4. Fie ( ), A X U = o arborescen binar complet n care

( ){ }0 x X d x n+ = = . Atunci ( )2 1U n= .Definiie. Fie ( ), A X U = o arborescen binar i

( ) ( ){ }0cu 0 si , ..., DT s x X d x l x x s+= = = (mulimea distanelor de la rdcin la fiecare vrf terminal ). Dac max min 1 DT DT , spunem c A este oarborescen binar echilibrat .

Teorema 5. Fie ( ), A X U = o arborescen binar. Urmtoareleafirmaii sunt echivalente:

1. A este o arborescen binar echilibrat ;2. pentru orice x X cu ( ) 0d x+ = , dac 2m X = , atunci

( )0,...,m l x x= i dac 12 2m m X +< < , atunci ( ) { }0,..., , 1l x x m m + .

5. GRAFURI HAMILTONIENE I EULERIENE5.1.Grafuri Hamiltoniene

Definiie. Fie ( ),G X U = un graf neorentat. Un lan (ciclu) elementar din G care conine toate vrfurile grafului se numetelan (ciclu ) hamiltonian .

Definiie. Un graf ( ),G X U = care con ine cel puin un ciclu hamiltonian se numete graf hamiltonian

Aceste noiuni se regsesc i pentru grafurile orientate sub urmtoareleforme.

Definiie. Fie ( ),G X U = un graf orentat. Un lan (rum, ciclu, circuit )elementar dinG care conine toate vrfurile grafului se numetelan (drum,ciclu, circuit ) hamiltonian .

Definiie. Un graf ( ),G X U = care con ine cel puin un circiut hamiltonian se numete graf hamiltonian orientat

Facem observaia c problematica grafurilor hamiltoniene este una decomplexinate nepolinomial din punctul de vedere al algoritmcii.

Teorema 1. Fie ( ),G X U = un graf neorientat n care 3 X n= i

pentru orice vrf x X avem ( ) 2nd x . AtunciG este graf hamiltonian.


14/31

14

5.2.Grafuri euleriene

Definiie. Fie ( ),G X U = un graf neorientat. Un ciclu simplu dinG senumeteciclu eulerian dac conine toate muchiile luiG .

Definiie.Graful neorientat ( ),G X U = se numete graf eulerian dac G conine cel puin un ciclu eulerian.

Dac trecem n cadrul grafurilor orientate avem definiia ce urmeazDefiniie. Fie ( ),G X U = cu U s= un graf orientat Fie

[ ]1 2, ,..., s L m m m= un lan ( ( )1 2, ,..., s D m m m= un drum) simplu, atunci spunem c lanul L (drumul D) este lan (drum ) eulerian ..

Lema 1. Fie ( ),G X U = un graf neorientat, nu neaprat conex. Dac pentru orice x X avem ( )d x numr par i pentru 0 X avem ( )0 0d x ,atunci exist un ciclu simplu nG care trece prin 0 x .

Teorema 2. Fie ( ),G X U = un graf neorientat fr vrfuri izolate. AtunciG este eulerian dac i numai dac G este conex i pentru orice x X ,

( )d x este numr par. Teorema 3. Fie ( ),G X U = un graf conex. Urmtoarele afirmaii sunt

echivalente:1. G conine un ciclu eulerian.2. Orice x X , ( )d x este numr par .3. Exist 1 2, ,...,i i i ii pC m m m = cicluri,

i jm U , 1,2,..., i j p= ,

1,2,...,i k = , astfel nct notnd { }1 2, ,...,i i i ii pU m m m= avemi jU U = pentru orice 1 ,i j k , i j i

1

k

ii

U U =

= (mulimeamuchiilor poate fi partiionat n cicluri).Corolar 1. Fie ( ),G X U = un graf conex.G conine un lan eulerian

dac i numai dac cel mult dou vrfuri ale luiG au gradul impar .Corolar 2. Fie ( ),G X U = un graf conex cu2k vrfuri de grad impar,

0k > . Atunci exist 1 2, ,...,i i i ii p L m m m = lan deschis,i jm U , 1,2,..., i j p= ,

1,2,...,i k = , astfel nct notnd { }1 2, ,...,i i i ii pU m m m= avem i jU U =


15/31

15

pentru orice1 ,i j k , i j i1

k

ii

U U =

= (mulimea muchiilor poate fi

partiionat n exact k lanuri deschise).

VI.ALGORITMI PENTRU DRUMURI N GRAFURI ORIENTATE6.1.Algoritmi de calcul direct

Pentru calculul direct a matricii drumurilor putem folosi n primul rndoperaiile+ i i definite n capitolul 3.

Algoritmul are la baz propoziia 5 din capitolul 3 i are forma urmtoare.Algoritmul 1.

1. Considerm 1i = , D A= i T A= .2. Dac i n> algoritmul se oprete, D conine matricea drumurilor dinG ,

altfel se continu .3. Considerm 1i i= + i calculmT T A= i folosind operaiile+ i i .4. Calculm D D T = + folosind operaia+ .

5. relum cu pasul 2.Teorema 1. Fie ( ),G X U = un grad orientat cu matricea de adiacea A i cu X n= . Algoritmul 1 produce matricea drumurilor dinG i arecomplexitatea ( )42O n .

Acest algoritm poate fi considerat i sub urmtoarea form.Algoritmul 1.

1. Considerm D A= .2. Pentru 1,2,...,i n= i pentru 1,2,..., j n= se execut pasul 4.3. Algoritmul se oprete; D conine matricea drumurilor luiG .

4. Dac 0ijd = , atunci pentru 1,2,...,k n= se execut pasul 5 altfel secontinu. 5. Se calculeaz ik ik jk d d d = + .

O alt modalitate de calcul direct folosete operaiile uzuale definite pemulimea numerelor naturale.

Algoritmul se bazeaz pe propoziia 6 din capitalul 3 i pe legtura careexist ntre matricile G D i G D . Algoritmul are forma urmtoare.

Algoritmul 2.1. Considerm 1i = , D A= i T A= .2. Dac i n> se trece la pasul 6, altfel se continu .3. Considerm 1i i= + i calculmT T A= i folosind operaiile uzuale de

adunare i nmulire a numerelor ntregi.


16/31

16

4. Calculm D D T = + folosind operaia de adunare a numerelor ntregi.5. Relum cu pasul 2.6. Pentru fiecare 1,2,...,i n= i fiecare 1,2,..., j n= se execut pasul 8. 7. Algoritmul se oprete, D conine matricea drumurilor dinG 8. Dac 0ijd , atunci face 1ijd = , altfel se continu.

Algoritmul 1 este cunoscut sub numele de Algoritmul lui Wharshal pentrudeterminarea matricii drumurilor .

6.2.Algoritmul Wharshal pentru drumuri minime n grafuri orientate

De o mare aplicabilitate practic este o problem de drumuri relatic lagrafurile ponderate. Fie ( ),G X U = un graf ponderat, deci un graf orientat n careU X M X , fiind mulimea ponderilor.

Pentru reprezentarea acestui graf se utilizeaz o matrice specific( )1 ,ij i j n P p = de elemente

( ) pentru , ,

altfel

ij i ij jij

m m x U p

=

+

.

Matricea poart numele dematricea ponderilor grafuluiG .n grafulG se poate defini astfel noinuea delungime a unui drum

( )( ) ( )( )2 3 11 1 2 2 2 3 1, , , , , ,..., , , k i i i i i i i i i i i ik k k d x m x x m x x m x++= ,notat prin ( ) L d =, i dat prin relaia

( ) 11

k

i i j j j

L d m+

== .

Pentru orice , y X , putem defini mulimea drumurilor de la x la ca

fiind mulimea( ) ( ){ }0 1, , ,..., drum ink D x y d x x x x y d G= = = = .O problem important este de a determina nG drumurile minime ntrevrfuri. Pentru acest lucru vom definimatricea drumurilor minime , notat

( )min 1 ,G ij i j n D d = , unde

( )( )

,minij

d D x xi jd L d

=

. Folosind aceste notaii, pentru determinarea matriciiinG D a drumurilor minine se poate face folosind Algoritmul Wharshal pentru drumuri minime ,adic:


17/31

17

Algoritmul 3.1. Considerm 1i = ( prelucrm liniai ) , D P = .2. Dac i n> , atunci algoritmul se termin i minG D D= , altfel se continu. 3. Pentru fiecare 1,2,..., j n= se aplic pasul 5. 4. Facem 1i i= + (trecem la urmtoarea linie) i trecem la pasul 2. 5. Dac ijd = + , atunci se continu, altfel se nlocuiete linieii cu

minimul dintre linieii i linia obinut din linia j prin adugarea valoriiijd la fiecare element.

Teorema 2. Dac ( ),G X U = este un graf orientat ponderat cu P matricea ponderilor dat pe mulimea de ponderi i X n= . Algoritmul 3 producea matricea drumurilor minime din graful G i are complexitatea ( )3O n exprimat ca numr de comparaii.

6.3.Algoritmul lui Dantzig pentru drumuri minimede extremitate iniial dat

Acest algoritm determin toate drumurile de lungime minim care pornescde la un vrf dat i ajung la toate celelalte vrfuri.

Se consider un graf orientat ( ),G X U = avnd X n= . Fie i X unvrf considerat iniial pentru toate drumurile pe dare dorim s le determinm. Fie

( )1 ,ij i j n P p = matricea ponderilor definit ca mai sus.Se consider urmtorul proces de calcul:Algoritmul 4.

1. Considerm 1m= , { }m i X x= i ( ) 0ic x = .2. Dac ( ) 0md X + = , atunci ne oprim; altfel se continu. 3. Pentru orice arc( ), j k x U pentru care j m X i k m X se

calculeaz valoarea ( ) jk jk jd p c x= + 4. Calculm min jk x X m j

x X mk

d d

= .

5. Pentru fiecarek astfel nct jk d d = considerm ( )k c x d = i{ }1m m k X X x+ = . Facem 1m m= + i trecem la pasul 2.

n urma execuiei acestui proces,m este numrul de vrfuri atinse dinvrful i , m X este mulmea acestor noduri i pentru fiecare m x X valoarea

( )c x indic lungimea unui drum minim de extremitate iniiali x i extremitate


18/31

18

final x. Procesul se termin n cel mult 1n repetri ale pailor 2, 3, 4 i 5deoarece la pasul 5 se adaug cel puin cte un vrf la mulimeam X .

6.4.Algoritmul lui Bellman-Kalaba pentru drumuri minimede extremitate final dat

Acest algoritm rezolv problema similar celei prezentate la algoritmulDantzig, adic determin drumurile de lungime minim care au extremitatea finalfixat.

Fie ( ),G X U = un graf orientat ponderat cu { }1 2, ,..., n X x x x= . Putem presupune c dorin s determinm drumurile de extremitate finaln . Acest lucrunu restrnge generalitatea deoarece putem gsi un izomorfism f de grafuriorientate astfel nct dac dorim s determinm drummurile cu extremitatea final

i x s avem ( )i n f x x= .Considerm c ( )1 ,ij i j n P p = este matricea ponderilor pentru grafulG .

Pentru realizarea algoritmului Bellman-Kalaba, construim o versiune modificat a

matrici ponderilor, matricea ( )1 ,ij i j nW w = , definit dup cum urmeaz( )

( )

pentru si , , pentru

0 pentru pentru0

pentru si , ,

ij i ij jij

ij

i ij j

m i j x m x U p i j

w i ji j

i j x m x U

= = = =

.

Algoritmul 5. Etapa 1

Se construiete matricea estins a valorilor arcelor ( ), 1,ij i j nW w == .Construim un tabel n care liniile sunt liniile matricii , notat ( )1i i n L L = , unde i L este linia i a tabelului La tabelul format se adaug linia 1n L + care este transpusacoloanein din matriceaW .

Etapa 2Se adaug tabelului L , liniile suplimentare i L , 2, 3,...i n n= + + , astfel:

a) presupunnd completat liniak L se completeaz linia 1k L + conform relaiei:

{ }( )1, , 1, ,1,...,min , mink j k j k t k t t n L L w L+ +== + . b) se continu aplicarea punctului(a) pn la obinerea a dou liniik L i 1k L +

identice.

Etapa 3


19/31

19

Se determin regresiv drumul minim de lai x la n x astfel:- se adun linia i din L cu linia 1k L + urmrindu-se rezultatul minim ce se

poate obine. S presupunem c 1, 1,k i ij k i L w L+ += + , atunci primul arc dindrumul minim de la i x la n x este arcul ) ji x x , ;

- se adaug linia j din L cu 1k L + reinnd valoare minim, aflat de

exemplu pe coloana k , atunci al doilea arc va fi )k j x x , .a.m.d. Ultimul succesor determinat va fin x .

Propoziia 1. Pentru orice *k avem { }1, ,1,mink i ij k j j n L v L+ == +

Propoziia 2.Dac exist *k pentru care , 1,k i k i L L+= , pentru orice1 i n , atunci , ,k i s i L L= , pentru orice1 i n i orice 1 s k + ,

Teorema 3. Fie ( ),G X U = un graf orientat ponderat cu X n= . Atuncialgoritmul 5 are ca rezultat determinarea tuturor drumurilor minime deextremitate final n x i complexitatea algoritmului este ( )22O n exprimat canumr maxim de comparaii.

6.4.Algoritmii lui Ford i Dijkstra pentru drumuri minimede extremiti date

Comparativ cu algoritmii prezentai mai sus urmtorul algoritm sefolosete pentru cazul n care ambele extremiti ale drumului cutat sunt fixate.

Fie ( ),G X U = un graf orientat i i x , j dou vrfuri. Dorim sdeterminm un drum optim de lai x la x . Datorit izomorfiesmelor de grafuri, putem considera c determinm un drum de la1 x la n x , fr a restrngegeneralitatea procesului de determinare.

Calculul se realizeaz n trei faze, una de iniializare, una de calcul efectivi una de obinere a drumul minim dintre1 x i n x , dac exist drumuri ntre celedou vrfuri.

Considerm c ( )1 ,ij i j n P p = este matricea ponderilor pentru grafulG .Pentru realizarea algoritmului Bellman-Kalaba, construim o versiune modificat amatrici ponderilor, matricea ( )1 ,ij i j nW w = , definit dup cum urmeaz


20/31

20

( )

( )

pentru si , , pentru

0 pentru pentru0

pentru si , ,

ij i ij jij

ij

i ij j

m i j x m x U p i j

w i ji j

i j x m x U

= = = =

.

Algoritmul 6. Etapa 1

Se construiete matricea estins a valorilor arcelor ( ), 1,ij i j nW w == .Construim un vector ( )1i i nv v = pentru care considerm 1 0v = i iv = + pentru 2 i n . Etapa 2a) Cu 1,2,...,i n= , n aceast ordine se construiete vectorul ( )* * 1i i nv v = pe

baza formului:

( ){ }*

,

min , mini

i i j ji j x x U j

v v v w

= +

.

b) Se continu aplicarea punctului(a) ct timp exist un indicek pentru care*k k v v< , nlocuinduse vectorul v prin vectorul *v .

Etapa 3- Dac nw = + , atunci nu exist drumuri ntre1 i n .- Se determin drumul de la1 la n x plecndu-se de la n , procednd dup

cum urmeaz: dac presupunem c s-a determinat ( )1 1, ,...,k k k nii x x x = , partea de la k i la n x a drumului minim. Lum 1k i+ vrful pentru care are locrelaia

1 1k k k k i ii iv w v

+ ++ =

Algoritmul prezentat este un algoritm care conine o serie de complicaiidatorate faptului c s-a dorit s funcioneze pentru toate grafurile orientate. Pentrucazul n care se cunoate faptul v grafulG nu conine circuite, acest algoritm poate fi simplificat pentru a se ajunge la urmtoarea form.

Algoritmul 7.1. Se construiete matricea estins a valorilor arcelor ( ), 1,ij i j nW w == .,

facem 1 0v = (. ( )1i i nv v = fiind un vector de dimensiunen ) iconsiderm mulimile { }1 A x= i { }1\ B X x= .

2. Dac nu exist j A i i x B astfel nct ( ), j i x U , atunci neoprin, nu exist drumuri de la1 x la n ; altfel se continu.


21/31

21

3. Considerm mulimea ( ){ }, ,C x B y A y x U = . Pentru oricei C , facem { }mini j ji j

x A j

v v w

= + .

4. Facem nlocuirile A A C = , \ B B C = . 5. Dac n x A atunci se trece la pasul 2, altfel se continu .6. Se determin drumul de la

1la

n x plecndu-se de la

n , procednd dup

cum urmeaz: dac presupunem c s-a determinat ( )1 1, ,...,k k k nii x x x = , partea de la k i x la n x a drumului minim. Lum 1k i x + vrful pentru careare loc relaia


+ ++ = .

Se poate observa c n algoritmul simplificat al lui Ford, n pasurile 3 i 4se determin un minim i apoi are loc o trecere a tuturor vrfurilor dinC n A. Pede al parte, o parte din arcele considerate la pasul 3 nu vor face parte din drumulminim de la 1 la n x . Acest lucru se va ntmpla doar pentru vrfurile n care seatinge minimul calculat la aplicarea relaiei { }mini j ji j

x A j

v v w

= + . Aceast

consideraie ne conduce la un algoritm nbuntit pentru determinarea drumurilor minime n grafuri fr circuite, cunoscut sub numele dealgoritmul lui Dijkstra .

Algoritmul 8.1. Se construiete matricea estins a valorilor arcelor ( ), 1,ij i j nW w == .,

facem 1 0v = (. ( )1i i nv v = fiind un vector de dimensiunen ) iconsiderm mulimile { }1 A x= i { }1\ B X x= .

2. Dac nu exist j A i i x B astfel nct ( ), j i x U , atunci ne

oprin, nu exist drumuri de la1 x la n ; altfel se continu. 3. Considerm mulimea ( ){ }, ,C x B y A y x U = . Pentru orice

i C , facem { }mini j ji j x A j

v v w

= + .

4. Pentru fiecare k C pentru care exist j A astfel nct

{ }mink jk j jk j x A j

v w v w

+ = + considerm { }k A A x= i { }\ k B B x= .

5. Dac n x A atunci se trece la pasul 2, altfel se continu .


22/31

22

6. Se determin drumul de la1 la n x plecndu-se de la n , procednd dup

cum urmeaz: dac presupunem c s-a determinat ( )1 1, ,...,k k k nii x x x = , partea de la k i x la n x a drumului minim. Lum 1k i x + vrful pentru careare loc relaia


+ ++ = .

VII.ALGORITMI PENTRU GRAFURIHAMILTONIENE I EULERIENE

7.1.Algoritmul lui Foulkes pentru drumuri hamiltoniene

Pentru a uura cutarea drumurilor hamiltoniene ntr-un graf orientat conex( ),G X U = , vom face o cutarea a drumurilor hamiltoniene n subcomponente

tari conexe ale grafuluiG i apoi vom asambla subdrumurile prin utilizarea punilor prin care sint conectate componentele tari conexe.

Considerm un graf orientat conex ( ),G X U = care are matricea de

asiacen A. Din matricea de adiacen putem determina matricea drumurilor D ,utiliznd modalitile prezentate n capitolele anterioare.Procesul se desfoar n 3 etape, una de formare a componentelor tari

conexe din grafulG , a doua n care se formeaz cte un drum hamiltonian nfiecare din componentele tari conexe i ultima etap de formare a unui drumhamiltonian nG pe baza subdrumurilor determinare n etapa a doua.

Algoritmul 1. Etapa 1 1.a) Facem I D= + i 1i = 1.b) n matricea se consider toate liniile formate dour cu

valoarea 1. Vrfurile corespunztoare acestor linii formez mulimea devrfuri

iC .

1.c) Se elimin din matricea liniile i coloanele considerate n formareamulimii iC .

1.d) Dac matricea nu s-a epuizat se trece la pasul (1.b), altfel se continu trecnd la etapa a doua.

Etapa 2Se construiete un grag ( ),G Y V = unde { }1 2, ,..., r Y C C C = i

( ),i jC C V dac i numai dac exist iC i exist jC astfel nct ( ), x y U .Se formeaz astfel un drum hamiltonian nG , i anume drumul

( )1 2, ,..., r d C C C = .


23/31

23

Etapa 33.a) Se consider 1 1 x C i 2 2C pentru care exist ( )1 2, x U . Gsim n

1C un drum hamiltonian 1d de extremitate iniial *1 x i extremitate final 1

i n 2C un drum hamiltonian 2d de extremitate iniial 2 x i extremitate

final *2 x . Se foremaz astfel drumul hamiltonian ( )( )

*1 1 1 2 2, , ,d d x x d = n

graful parial al luiG de vrfuri 1 2C C . Facem 3i = .3.b) Dac i r > ne oprin, s-a obinut drumul hamiltonian, altfel se continu .3.c) Dac exist i i x C astfel nct ( )* 1,i i x U atunci se trece la pasul (3.d),

altfel se trece la pasul (3.e).3.d) Se consider n iC un drum hamiltonian id de extremitate iniial i x i

notm extremitatea sa final prin*i x . Am format astfel drumul hamiltonian

( )( )* * *1 1, , ,i i i i id d x x d = n graful parial al lui G de vrfuri1 2 ... iC C C . Facem 1i i= + i mergem la pasul (3.b).3.e) Fie ie partea din drumul * 1id care formeaz acest drum mpreun cu 1id .

Fie 1 1i iC i i i x C pentru care ( )1,i i x x U . mprim drumul 1id n1id de extremitate final 1i x i drumul 1id de extremitate iniial 1i i

extremitate final * 1i . Considerm un drum 1id care pleac din 1i x , trece*

1i x i apoi prin toate celelante vrfuri care apar n drumul 1id astfel nct extremitatea final a lui 1id s fie 1i x . Se consider n iC un drumhamiltonian id de extremitate iniial i i notm extremitatea sa final prin

*i x . Considerm drumul ( )( )

*1 1 1, , , ,i i i i i id d d x x d = n graful parial al luiG de vrfuri 1 2 ... iC C C . Facem 1i i= + i mergem la pasul (3.b).

7.2.Teorema lui Chen

Fie ( ),G X U = un graf orientat i fr circuite cu { }1 2, ,..., n X x x x= .Considerm c A este matricea de adiacen a grafului i putem determinamatricea D a drumurilor dinG .


24/31


25/31

25

7.3.Algoritmul lui nmulirii latine

Algoritmul de determinare a matricii drumurilor are un caracter preasintetic, n sensul c prezena unei valori de 1 n matricea drumurilor nu dinformaii asupra vrfurilor din care se compun drumurile corespunztoare, bineneles c nici asupra numrului de drumuri ntre vrfurile care corespundacelor valori de 1.

Ca un exemplu de algoritm capabil s rspund acestor deziderate, prezentm algoritmul datorat lui Kaufmann, numitaloritmul nmulirii latine .Introducem ca punct de plecare, o matrice( )1 , care n locul valorilor de

1 utilizate n matricea obinuit a arcelor, utilizeaz nsui arcul respectiv,reprezentat prin vrfurile care l compun.( ) ( )( ) n jiijmM ,1,11 == , unde

dac exist arc de lai x la j x ( ) =0

1 jiij

x xm

n restPrin suprimarea primei litere n matricea( )1 se obine o matrice ( )1~

numit a destinaiilor posibile . Se compun matricele ( )1 i ( )1~ prin operaiade nmulire latin . ( ) ( )1 1M L M .

nmulirea latin a matricilor se face formal ca i nmulirea a dou matrici,fr nsumare i fr nmulire efectiv innd cont c:- produsul latin a dou componente participante la calcul este nul dac cel puin

una din ele este nul.- produsul latin a dou componente participante este nul dac au vrf comun.- rezultatul compunerii const n scrierea n continuare a vrfurilor componente

ale simbolurilor participante.Prin definiia produsului latin avem ( ) ( ) ( )2 1 1M L M = ,

( ) ( ) ( )3 2 1M L M = , Algoritmul continu pn la obinerea matricii( )1n ,

deoarece ntr-un graf cun vrfuri un drum hamiltonian are 1n arce.n matricea ( )1nM citim, conform modului de scriere de mai sus toatedrumurile hamiltoniene ale grafului.

Dac toate elementele lui ( )1n sunt zerouri ( ( ) 0=1nM ), graful nuadmite drum hamiltonian.

Observaie. Procedeul este aplicabil pentru orice tip de graf orientat (cusau fr circuit), dar pentru grafurile fr circuite se recomand algoritmul luiChen, ntruct pentru grafuri de dimensiuni mari, algoritmul nmulirii latine estegreoi (dar sigur).


26/31


27/31

27

Ideea de mai sus a fost utilizat de Hierholzer pentru realizareaargoritmului de mai jos, cunoscut dreptalgoritmul lui Hierholzer .

Fie graful ( ),G X U = .Algoritmul 3.

1. Se alege un vrf 0 X i plecnd de la 0 , prin traversarea fiecreimuchii neconsiderate formm un ciclu { }0 0 00 1 2 0, ,..., r C u u u= i 0i = .

2. Dac graful parial format cu muchiile cuprinse n ciclul iC coincide cuG atunci ne oprim, iC reprezint ciclul eulerian cutat, altfel secontinu .

3. Fie nodul i , extremitate a muchieiik u din ciclul iC i al unei muchii *iu

care nu este n iC . Pornind de la nodul i x , n graful parial al luiG cumulimea de muchii format de muchiile nefolosite la formarea luiiC , formm un ciclu ca la pasul (1) , notat *iC .

4. Formm ciclul { }1 1 11 1 2 1, ,...,i i ii r iC u u u+ + ++ += pornin din i x , parcurgnd integral iC pn ajungen din nou la i x i apoi parcurgnd integral *iC pn se ajunge la i

5. Facem 1i i= + i trecem la pasul (2).

VIII.FLUX MAXIM N REELE DE TRANSPORT8.1.Consideraii generale

Definiie. Un graf orientat ponderatt ( ), ,G X U p= fr circuite, senumetereea de transport dac ndeplinete urmtoarele condiii:

1. Dac { }n x x x X ,...,, 21= , atunci oricare ar fi1 i n avem ( ),i i x U .2. Exist un vrf unic X x 1 n care nu intr nici un arc, numit sursa reelei.3. Exist un unic vrf n x din care nu iese nici un arc, numit destinaia reelei.4. G este conex i exist drumuri de la 1 x la n x .5. S-a definit o funcie :c U astfel nct ( ) 0uc pentru orice arc u U ;

numrul ( )uc se numetecapacitatea reelei. Definiie. Fie ( ), ,G X U p= o reea de transport. Fiind dat o

submulime X Y , se numetetietur de suport Y mulimea de arce

( ) ( ){ }, ,i j i jY x x U x Y x Y U

=


28/31

28

( ) ( ){ }, ,i j i jY x x U x Y x Y U + = .Cantitatea ( )( )

( ) ( )

=Y j xi xij pY c

, estecapacitatea tieturii ( )Y .

Definiie. Fie ( ), ,G X U p= o reea de transport. O funcie :U + se numete flux pe reeaua de transport ( ), ,G X U p= dac ndeplinete

urmtoarele condiii:1. Condiia de mrginire a fluxului : pentru orice( ),i j x U , avem ) ij p x x ji ,0 .

2. Condiia de conservare

Pentru orice i X , avem ( )( )

( )

=

==

n

h x j xh

h j

n

j xk xk

jk x x x x,

1,

1,, .

Observaii.1. Condiia 2) afirm c pentru orice vrf x cu 1 x x i n x x , suma

fluxurilor de pe arcele care intr n este egal cu suma fluxurilor pe arcelecare ies din x.

2. Funcia nu este unic.Definiie. Fie ( ), ,G X U p= o reea de transport. Un arc( ),i j x U se

numetearc saturat , dac n raport cu are loc relaia ) ij ji p x x = , .Se pune problema determinrii funciei astfel nct suma fluxurilor pe

arcele ce intr n n x s fie maxim, aa-numita problem a fluxului maxim .Adic, dintre toate fluxurile:U + posibile n reeaua de transport

( ), ,G X U p= se urmrete s se determine fluxul pentru care

( )( )

( )( )

1 1

, ,

, ,n n

h n h nh h

x x U x x U n nh h

x x x = =

.

Propoziia 1. Fie ( ), ,G X U p= o reea de transport avnd sursa 1 x ,destinaia n x i :U + un flux oarecare n reeaua G , atunci:

( )( )

( )( )

11 1

, ,1

, ,n n

i j ni j

x x U x x U i j n

x x x = =

=

Definiie. Fie ( ), ,G X U p= o reea de transport avnd sursa 1 x ,destinaia n x i :U + un flux oarecare n reeaua G . Valoarea


29/31

29

( )( ) ( )

( )( ) ( )

1,, 1

, , j n i x x x x x xn n i j i

x x x x

+

= = se numetevaloarea total a fluxului : + .

Propoziia 2. Fie ( ), ,G X U p= o reea de transport i fie X Y o submulime cu proprietile: - pentru sursa 1 x a lui G avem 1 x Y ;- pentru destinaia n x a lui G avem Y xn .

Atunci pentru orice flux :U + avem( )

( ) ( )( )

( ) ( )( )( )Y c x x x x

Y j xi x ji

Y j xi x ji

=

+=

,,,, .

8.2.Algoritmul Ford-Fulkerson

n continuare vom considera c toate capacitile sunt numere raionale sauntruct numrul total de arce este finit, chiar numere naturale.

Pe baze consideraiilor precedente se deduce urmtorul algoritm cunoscut

sub numele dealgoritmul Ford-Fulkerson pentru determinarea fluxului maximntr-o reea de transport .Algoritm

Pasul I Se construiete un flux iniial 0 , care verific condiiile de conservare n

fiecare vrf i de mrginire pe fiecare arc, de exemplu chiar fluxul avnd componente nule pe fiecare arc al reelei, ( )0 , 0i j x x = , oricare ar fi ( ),i j x x U .

Pasul II Folosind operaiile de marcare ce vor fi prezentate mai jos, se cerceteaz

dac fluxul iniial 0 este maxim; operaiunile de marcare constau nurmtoarele:a) se marcheaz sursa reelei1 x cu semnul +; b) vrfurile ( )1 x x j + vor fi marcate cu 1 x+ dac arcul ) j x x ,1 este

nesaturat ;c) dac vrful j x este deja marcat i dac pentru un vrf ( ) jk x x + arcul

)k j x x , este nesaturat, atunci marcm vrful k x prin j x+ ;d) dac vrful j x este deja marcat i dac pentru un vrf ( ) jk x x arcul

) jk x x are fluxul nenul, marcm vrful k x prin j x .;


30/31

30

n urma terminrii operaiei de marcare, putem ntlni urmtoarele situaii:1. Dac destinaia n x a reelei nu s-a marcat, atunci fluxul este maxim i

algoritmul se termin , altfel se aplic procesul (2 ) i se reia pasul II. 2. Dac destinaia n x s-a putut marca, atunci fluxul nu este maxim i poate fi

msurat astfel :a) se alege un drum de la 1 x la n x ; b) pe arcele drumului marcat cu + fluxul se majoreaz cu o cantitate

de flux(de exemplu 1= );c) pe arcele drumului marcat cu - fluxul se micoreaz cu aceeai

cantitate ;d) fluxul arcelor nemarcate nu se schimb ;

Algoritmul are un numr finit de pai, iar fluxul maxim se atinge cnd nu mai poate fi marcat destinaian x a reelei.

Observaie. Mrimea fluxului se poate face cu mai mult dect o unitate,evitndu-se astfel prea multe operaii de marcare, astfel: se consider un drumV format din drumuri marcate cu + sau - ce unete1 x cu n x , uor de gsit

urmrind vrfurile marcate n sensul de lan x ctre 1 x . Notm +V mulimeaarcelor ( ) y x, unde y este marcat cu + i V mulimea arcelor ( ) y x, unde y este marcat cu -. Calculm

( ) ( ){ }uucV u

= +

min1

( )uV u=

min2

i { }21,min = . Observm c 0> i este numr ntreg.Mrim cu pe fiecare arc +V u i micorm cu pe fiecare arc V u ,

obinnd la ieire un flux mrit cu .Se repet etapa a doua cu fluxul obinut. Valoarea fluxului maxim se gsete

realiznd o tietur prin separarea cu o linie a vrfurilor marcate de cele nemarcatei capacitatea acestei tieturi reprezint fluxul maxim, sau adunnd fluxurilearcelor incidente interior luin x .

BIBLIOGRAFIE Obligatorie

1. I. Tomescu,Combinatoric i teoria grafurilor , Editura Universitii.Bucureti, 1990

2. I. Tomescu, Probleme de combinatoric i teoria grafurilor , EdituraDidactic i Pedagogic, Bucureti, 1981. Ediia englez: Problems inCombinatorics and Graph Theory, John Wiley, New York , 1985.


31/31

31

BIBLIOGRAFIE Opiomal

1. Bang-Jensen, G. Gutin, Digraphs Theory, Algorithms and Applications,Springer-Verlag, 2007

2. M. Behzad, G. Chartrand, L. Lesniak-Foster,Graphs & Digraphs, Prindle,Weber & Schmidt, Boston, Massachusetts, 1979.

3. B. Bollobas,Graph Theory. An Introductory Course, Springer-Verlag, New York, Heidelberg, Berlin, 1979.

4. C. Berge,Teoria grafurilor i aplicaii, Editura Tehnica, Bucuresi, 1971

algoritmica grafurilor sinteza

Documents

Transcript of algoritmica grafurilor sinteza