INTRODUCEREELEMENTARINTEORIAGRAFURILOR= 1: Reprezentri ale unui graf Un grafeste o pereche G = ( A , V ) format din : mulimea finit V , numit mulime de vrfuri : un element V v se numete vrf al grafului G ; mulimea V x V A numit mulime de arce : un element

A a se numete arc al grafului G.EXEMPLU : fie V = { a , b , c , d } i A = { ( a,b) , (d,c) , (b,c) , ( c,a) } .Graful G = ( A , V ) poate fi reprezentat schematic astfel :

Mai importante sunt reprezentrile matriceale ale grafurilor : vom prezenta n continuare unele reprezentri mai utilizate .Fie graful G = ( A , V ) , cu | V | = n .1Matricea latin L(G) = || sij || , i,j = 1,n este un tablou alfanumeric ,avnd elementelesij date de

'A ) v , v ( daca "*"A ) v , v ( daca ) v , v (sj ij i j iijPentru graful din exemplul precedent , avem L(G) =a b c da * (a,b) * (a,d)b * * (b,c) *c (c,a) * * *d * * (d,c) *Matricea binar sau boolean X(G) = || xij || , i,j = 1,nare elemente de 0 i 1 aparinnd lui Z2 , asociate astfel :'A ) v , v ( daca , 0A ) v , v ( daca , 1xj ij iijPentru graful G din exemplul precedent avem :X(G) =a b c da 0 1 0 1b 0 0 1 0c 1 0 0 0d 0 0 1 0Matricea X(G) se numete matricea arcelor grafului G.= 2 :Noiuni introductive :Fie graful G = ( A , V ) , cu | V | = n . pentru arcul A ) b , a ( , vrful a se numete sursa arcului , iar vrful2b se numete destinaia arcului ; vom spune c arcul este un arc de la alab un drum elementar de lungime k , *N k , n graful G = ( A , V ) este o succesiune de arce , cu proprietatea c destinaia fiecrui arc este aceeai cu sursa arcului urmtor EXEMPLU: n graful G deja prezentat , drumul d = {( a, b ) , ( b , c ) , ( c, a ) }

este un drum elementar de lungime 3Acest drum scris ca o list de arce , d = { (a,b) , (b,c) , (c,a) }se mai poate scrie ca o list de vrfurid = { a , b , c , a }.Observare : un drum elementar se zice c : are ca surs, sursa primului arc , a , i ca destinaie , destinaia ultimului arc , b , sau c este un drum de la a la b .

drumul f trece prin vrfurile arcelor care l compun .= 3 : Matricea drumurilor ntr-un graf Fie graful G = ( A , V ) , cuV = { v1 , v2 , , vn } .Urmrim s construim matricile urmtoare : pentru fiecare *N k , matricea n , 1 j , i) k (ij) k (|| d || D , numit matricea drumurilor de lungime k a grafului G , unde avem : 1 d) k (ij , dac n G exist un drum de lungime k de la vi la vj ;0 d) k (ij, dac n G nu exist nici un drum de lungime k de la vi la vj . matricea n , 1 j , iij|| d || D , numit matricea drumurilor sau matricea sintetic3a drumurilor , dat de :1 dij, dac n G exist cel puin un drum de la vi la vj ;0 dij, dac n G nu exist nici un drum de la vi la vj .Construcia matricilor) k (D are la baz cteva observri simple : 1 :) G ( X D) 1 (deoarece drumurile de lungime 1 sunt chiar arcele grafului dat ; 2 : principiul adugrii la nceput : ' +1 d) G ( X in 1 x: care . pt n , 1 h ) ( 1 d) k (j hih) 1 k (j i adic un drum de lungime k+1 de la vi la vj se compune dintr-unarc de la vi la un vrf intermediar vh , continuat cu un drum de lungime k de la vh la vj ; 3 : principiul adugrii la sfrit : ' +1 d) G ( X in 1 x: care . pt n , 1 h ) ( 1 d) k (h ihj) 1 k (j i adic un drum de lungime k+1 de la vi la vj se compune dintr-un drum de lungime k de la vi la vh continuat cu un arc de la vh la vrfulvj .-3.1 :ALGORITMUL M.R.C. de construire a matricilor D(K) :Varianta : cu folosirea adugrii la nceput etapa 1 : iniializarea algoritmului : avem) G ( X D) 1 (4 etapa 2 : trecerea de la matricea ) k (Dla matricea ) 1 k (D+ calculm matricea auxiliar|| h || H , D ) G ( X Hij) k ( avem :0 h 1 dij) 1 k (ij +Varianta : cu folosirea adugrii la sfrit etapa 1 : iniializarea algoritmului : avem ) G ( X D) 1 ( etapa 2 : trecerea de la matricea ) k (Dla matricea ) 1 k (D+ calculm matricea auxiliar|| h || H , ) G ( X D Hij) k ( avem :0 h 1 dij) 1 k (ij +==//==EXEMPLU: pentru un graf G avem urmtoarea matrice a arcelor :

,_

0 1 0 01 0 0 11 1 0 00 1 1 0) G ( XS calculm matricile ) 1 (D, ) 2 (D, ) 3 (D , ) 4 (D . avem ) 1 (D= X(G) calculul lui ) 2 (D :avem

,_

1 0 0 10 2 1 01 1 0 12 1 0 1) G ( X D H) 1 (5deci

,_

1 0 0 10 1 1 01 1 0 11 1 0 1D) 2 ( calculul lui ) 3 (D :avem

,_

0 2 1 02 1 0 11 2 1 11 2 1 1) G ( X D H) 2 (deci

,_

0 1 1 01 1 0 11 1 1 11 1 1 1D) 3 ( calculul lui ) 4 (D :avem

,_

1 2 0 11 2 1 12 3 1 12 3 1 1) G ( X D H) 3 (deci

,_

1 1 0 11 1 1 11 1 1 11 1 1 1D) 4 (Precizri:= elementele matricilor H au semnificaia urmtoare :dac|| h || H , ) G ( X D Hij) k ( dac hi j = m 6 atunci n graful dat exist m drumuri de lungime k+1 de la vi la vj = algoritmul M.R.C nu se termin neaprat dup un numr finit de pai : se poate spune c dac exist k pentru care ) k (Dmatricea nul, atunci avem . k m , 0 D) m ( O condiie suficient ca algoritmul s nu se termine dup un numr finit de pai este prezentat n continuare.DEFINIIE : un drum elementar f : { 1,2,, k } A se numete circuitdac

sursa primului arc coincide cu destinaia ultimului arcDac ntr-un graf exist cel puin un circuit , graful se va numi graf cu circuite .Dac graful G are circuite , atunci k , 1 n ) ( , N m ) (* pentru care1 d) m (n nadic n matricea drumurilor avem un 1 pe diagonal .Deci : = dac se obine o matrice ) m (D avnd un element de 1 pe diagonalse deduce c acel graf este un graf cu circuite ;= atunci 0 D) m ( pentru orice *N m, deci algoritmul nu se oprete dup un numr finit de pai .- 3.2 :ALGORITMUL M.R.C. de construire a matricii DAcest algoritm se aplic numai dac graful nu are circuite : el const din urmtoarele etape : se determin o valoare m pentru care ) m (D= O ; calculm matricea auxiliar H = D(1) + D(2) ++ D(m-1) , H = || hij || avem0 h 1 dj i j i .EXEMPLU: fie graful G de mai jos :7S determinm matricea sintetic a drumurilor :Avem X(G) = a b c d ea 0 1 1 0 0b 0 0 1 1 0c 0 0 0 1 1d 0 0 0 0 1e 0 0 0 0 0i deci D(1) = X(G) . Pentru calculul lui D( 2 ) :

,_

,_

0 0 0 0 00 0 0 0 01 0 0 0 01 1 0 0 01 1 1 0 0D0 0 0 0 00 0 0 0 01 0 0 0 02 1 0 0 01 2 1 0 0D ) G ( X H) 2 ( ) 1 ( ; Pentru calculul lui D( 3 ) :8

,_

,_

0 0 0 0 00 0 0 0 00 0 0 0 01 0 0 0 01 1 0 0 0D0 0 0 0 00 0 0 0 00 0 0 0 01 0 0 0 02 1 0 0 0D ) G ( X H) 2 ( ) 2 ( ; Pentru calculul lui D( 4 ) :) 4 ( ) 3 (D0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 01 0 0 0 0D ) G ( X H

,_

. Pentru calculul lui D( 5 ) :5 m ) ( , 0 D 0 D 0 D ) G ( X H) m ( ) 5 ( ) 4 ( .Pentru a calcula matricea sintetic D a drumurilor, vom nsuma matricile precedente :

,_

,_

+ + + 0 0 0 0 01 0 0 0 01 1 0 0 01 1 1 0 01 1 1 1 0D0 0 0 0 01 0 0 0 02 1 0 0 02 2 1 0 03 2 2 1 0D D D D H) 4 ( ) 3 ( ) 2 ( ) 1 (==//==9- 3.3 : ALGORITMUL Y. CHEN de construire a matricii DAcest algoritm este convenabil pentru probleme de dimensiuni mai mici : el const n urmtoarele etape : ca baz de pornire folosim matricea X(G) a arcelor ;fie n = numrul de vrfuri ale grafului pentru a construi linia i din matricea D , executm paii urmtori : a): dac n , 1 j ) ( , 0 xj i atunci n , 1 j ) ( , 0 dj i b): dacn , 1 h ) ( pentru care xi h = 1 dacn , 1 j ) ( pentru care ' +0 x x0 dj h j ij iatunci : dij = 1 . c ): etapa (b) se aplic pn cnd = se constat c n , 1 j ) ( , 1 dj i = se constat c n , 1 j ) ( , 0 x x 1 dhj ij h i + Algoritmul este valabil i pentru grafurile cu circuite .EXEMPLU : pentru graful precedent , avnd matricea arcelor X(G) dat de X(G) = a b c d ea 0 1 1 0 0b 0 0 1 1 0c 0 0 0 1 1d 0 0 0 0 1e 0 0 0 0 010vom determina matricea drumurilor folosind i algoritmul CHEN.= linia 1 din D : pentru a ncepe , observm c avem : ' 1 d 1 x1 d 1 x13 1312 12 deci pentru nceput linia 1 din D va avea aspectul

L1: 1*1 m ocup de valoarea1 d12 ( am marcat cu *) : aceasta se afl pecoloana 2 , deci n X(G) adun boolean linia 1 cu linia 2 : dac apareo nou valoare de 1 , o trec n linia L1 : avem 0 1 1 0 0 + 0 0 1 1 0 = 0 1 1 1 0deci obinem : L1: 1 1**1 m ocup de valoarea 1 d13 ( am marcat cu **) : aceasta se afl pecoloana 3 , deci n X(G) adun boolean linia 1 cu linia 3 : dac apareo nou valoare de 1 , o trec n linia L1 : avem 0 1 1 0 0 + 0 0 0 1 1 = 0 1 1 1 1deci obinem : L1: 1 1 1 1 ntruct un mai vor aprea alte valori de 1 , avem n final L1: 1 1 1 111= linia 2 din D : pentru a ncepe , observm c avem : ' 1 d 1 x1 d 1 x24 2423 23 deci pentru nceput linia 2 din D va avea aspectul

L2: 1*1 m ocup de valoarea 1 d23 ( am marcat cu *) : aceasta se afl pecoloana 3 , deci n X(G) adun boolean linia 2 cu linia 3 : dac apareo nou valoare de 1 , o trec n linia L2 : avem 0 0 1 1 0 + 0 0 0 1 1 = 0 0 1 1 1deci obinem : L2: 1 1**1 m ocup de valoarea1 d24 ( am marcat cu **) : aceasta se afl pecoloana 4 , deci n X(G) adun boolean linia 2 cu linia 4 : dac apareo nou valoare de 1 , o trec n linia L2 : avem 0 0 1 1 0 + 0 0 0 0 1 = 0 0 1 1 1deci rmne : L2 : 1 1 1 ntruct nu vor mai aprea alte valori de 1 , avem n final L2: 0 0 1 1 1 etc.In final obinem 12

,_

0 0 0 0 01 0 0 0 01 1 0 0 01 1 1 0 01 1 1 1 0D .= 4 : GRAF VALUAT : FUNCIE DE SINTEZ DECOMPOZABILUn graf valuat este un obiect de forma G = ( V , A , p ) , unde ( V , A ) este un graf p : A R este o funcie , numit funcie de valuare .Pentru un arc , A ) v , v (j inumrul ) v , v ( pj i se numete valoarea arcului A ) v , v (j i:aceast valoare va fi notat deobicei prin pij ;ij j ip ) v , v ( p .EXEMPLU: Un graf G are ca mulime de vrfuri mulimea V = { a , b , c , d } iar drept mulime de arce , A = { ( a, b) , ( a , c ) , ( b , c),( b , d ),( c ,d ) }.Funcia de valuare este dat de tabloul de mai jos : arcul ( a, b) ( a , c ) ( b , c) ( b , d ) ( c ,d )valoarea arcului 2 5 3 7 4Atunci graful se poate reprezenta schematic astfel :13

Ne propunem s tratm urmtoarea problem : ntr-un graf valuat considerm un drum ; cum putem defini un concept de valoare a drumului n funcie de valorile arcelor componente , astfel nct conceptul s fie corect i s permit determinarea drumurilor de valoare optim n graf printr-o procedur recursiv.Prin concept corect avem n vedere n primul rnd comportarea valorii drumului la fragmentarea acestuia : de exemplu , drumul ( d ) de mai jos se poate descompune n drumurile pariale ( d1 ) i ( d2 ) :14Cerem ca , prin compunerea valorii lui d1 cu valoarea lui d2 s se obin chiar valoarea lui d ,compunerea fcndu-se prin acelai procedeu ca la determinarea valorii drumului pe baza valorilor arcelor componente.Iat cteva exemple n acest sens := valoarea unui drum este media aritmetic a valorilor arcelor componente : valoarea drumului d este :334 3 2) d ( V + + valoarea drumului d1 este :5 , 223 2) d ( V1+ valoarea drumului d2 este :414) d ( V2 avem) d ( V ) d ( V ) d ( V 25 , 324 5 , 2) d ( V ) d ( V ; 4 ) d ( V2 1 2 1 + deci media aritmetic a valorilor arcelor un este un concept potrivit pentru a defini valoarea unui drum ;= valoarea unui drum este media aritmetic ponderat a valorilor arcelor, cu ponderi numrul de arce ce urmeaz n drum dup arcul dat : valoarea drumului d este : 381 2 31 4 2 3 3 2) d ( V + + + + valoarea drumului d1 este : 371 21 3 2 2) d ( V1+ + valoarea drumului d2 este :414) d ( V2 avem ) d ( V ) d ( V ) d ( V9261 21 4 237) d ( V ) d ( V ;38) d ( V2 1 2 1 + + 15NICI conceptul de medie aritmetic ponderat nu convine.Iat o list cu funcii de sintez care au proprietatea enunat := suma valorilor arcelor ;= produsul valorilor arcelor ;= minimul valorilor arcelor ; = maximul valrilor arcelor .Iat nc o cerin ce trebuie impus unei funcii de sintez , dup cum rezult din exemplul de mai jos ;considerm un drum d de lungime n , compus din arce avnd valorile p1, p2 , , pn ;definim valoarea drumului d , punnd+ n1 jj) | p | 1 ( ) d ( V.Acest concepu nu este potrivit :s considerm un drum d format dintr-un singur arc , de valoare p ;atunci = valoarea lui d considerat ca drum este : 1 + | p | = valoarea lui d considerat ca arc este : p .O metod de determinare a valorii drumului n funcie de valorile arcelor este considerat convenabil n condiiile urmtoare :Fiek , 1 j , R r ; N k | ) r ,..., r , r ( {j*k 2 1 ; fie funcia R : F , cu proprietile( S1 ) F( r ) = r , pentru orice R r( S2 ) pentru orice ) r ,..., r , r ( {k 2 1 i pentru orice1 k , 2 j avem ) r ,..., r ( F ] ) r ,..., r ( F ; ) r ,..., r ( F [ Fk 1 k 1 j j 1+( S3.1 ) sau :b ) ( , ) b , a ( F ) b , a ( F a a2 1 2 1 0, drumul a b c b dare valoarea > K drumul a b c b c b d are valoarea > 2K drumul a b c b c b cb d are valoarea > 3K etc .Dac ns : avem K < 0 , algoritmul se aplic pentru problemele de drum maxim avem K > 0 , algoritmul se aplic pentru problemele de drum minim .34EXEMPLU : fie graful

Valoarea unui drum este egal cu suma valorilor arcelor coponente : se cer valorile drumurilor minime cu destinaia d Observare : circuitul b c b are valoarea K = 2 + 3 > 0 , deci determinarea drumurilor minime este posibil . Calculele sunt cuprinse n tabelul de mai jos :a b c da 1 2 7 80b 1 3 4c 2 1 10d 1M(1)80 4 10 1M(2)min:80 ; 8; 70;80 8min: ; 4; 30;4 4min: ; 8; 10;10 8min: ; ; ;1 1M(3)min:8 ; 8; 56;80 8min: ; 4; 24;4 4min: ; 8; 8;10 8min: ; ; ;1 135Deoarece M(2) = M(3) , rezolvarea se termin : vectorul M(3) conine valorile drumurilor minime cu destinaia d , anume de la a la d , drumul minim are valoarea 8 de la b la d drumul minim are valoarea 4 de la c la d drumul minim are valoarea 8 un exist drumuri de la d la d . =7.2 : DRUMURIOPTIMECUSURSAFIXATFie G = ( V , A , p ) un graf valuat complet ( adic avem A = VxV ) ; fieV viun vrf fixat ; ca deobicei , notm | V | = n.Spre exemplificare, vom analiza cazul n care valoarea unui drum este egal cu suma valorilor arcelor componente .Pentru fiecare *N k , vom determina un vector n , 1 j) k (j) k (|| m || Munde) k (jmeste valoarea drumului optim format din cel mult k arce , de la vi la vj .Pentru aplicarea algoritmului , vom porni de la matricea valorilor arcelor grafului G ,anume V v , v ; , ) v , v ( p h cu , || h || Hj i j i j , in , 1 j , ij i - Pentru iniializarea algoritmului , s observm cn , 1 j ; h mj , i) 1 (j - presupunem c am construit deja vectorul n , 1 j) k (j) k (|| m || M- pentru trecerea la vectorul n , 1 j) 1 k (j) 1 k (|| m || M+ + , se foloseterelaia } h m { optim mj r) k (rn , 1 r) 1 k (j+ +- drepr criteriu de oprire , avem i aici : k h ) ( , M M M M) h ( ) k ( ) 1 k ( ) k ( +36EXEMPLU : n graful prezentat mai jos, valoarea unui drum este egal cu sumavalorilor arcelor componente : se cer valorile drumurilor maxime cusursa n vrful a . Aplicarea algoritmului apare n tabelul urmtor :37a b c d e f M(1)M(2)M(3)M(4)M(5)M(6)a 0 5 107 12- 0 0+0;5- 10- ;7- 12- ;- - 00+0;5- 10- ;7- 12- ;- - 00+0;5- 10- ;7- 12- ;- - 0 0 0b - 0 8 4 - 125 0+5;5+010- ;7- 12- ;- - 50+5;5+013- ;16- 17- ;25- 50+5;5+013- ;21- 20- ;29- 50+5;5+013- ;21- 20- ;29- 55c - - 0 - 7 1510 0+10;5+810+0;7- 12- ;- - 130+10;5+813+0;15- 17 - ;25- 130+10;5+813+0;21- 20- ;29- 130+10;5+813+0;21- 20- ;29- 13 13d - - - 0 - 9 7 0+7;5+410- ;7+012+4;- - 160+7;5+413- ;16+017+4;25- 210+7;5+413- ;21+020+4;29- 240+7;5+413- ;24+020+4;32- 2424e - - - 4 0 1212 0+12;5- 10+7;7- 12+0;- - 170+12;5- 13+7;16- 17+0;25- 200+12;5- 13+7;21- 20+0;29- 200+12;5- 13+7;24- 20+0;32- 2020f - - - - - 0 - 0- ;5+1210+15;7+912+12;- +0 250- ;5+1213+15;16+917+12;25+0 290- ;5+1213+15;21+920+12;29+0 320- ;5+1213+15;24+920+12;32+0 33 3338- 8 : ALGORITMDEDETERMINAREAVALORILORDRUMURILOR OPTIMEINTRETOATEPERECHILEDEVRFURISIMULTANFie G = ( V , A , p ) un graf valuat complet ( adic avem A = VxV ) ; fie V = { v1,v2,,vn } i fieV viun vrf fixat ; ca deobicei , notm | V | = n.Spre exemplificare, vom analiza cazul n care valoarea unui drum este egal cu suma valorilor arcelor componente .Pentru fiecaren , 2 k ne propunem s determinm matricea k , 1 j , ikj i) k (|| m || Munde kj im= valoarea drumului optim de la vi la vj , determinat n mulimea drumurilor avnd vrfurile n mulimea Vk = { v1,v2,,vk }. Iniializarea algoritmului :evident c avem 2 , 1 j , i ; ) v , v ( p mj i2j i deoarece singurul drum de la vi la vj care trece numai prin vrfurile j iv , veste arcul ( vi , vj ) . presupunem c am construit matricea k , 1 j , ikj i) k (|| m || M; ne propunem s determinm matricea 1 k , 1 j , i1 kj i) 1 k (|| m || M+ + +; acest lucru se va efectuan patru faze :- Faza 1: determinarea elementelork , 1 i , m1 k1 k , i++In cadrul acestei faze ne propunem s determinm valoarea drumului optim de la un vrfk iV vla vrful vk+1 nou adugat .Un astfel de drum const dintr-un drum n mulimea kV, de la vi la un vrf vj din kV ,urmat de arcul vj la vk+1 .In mulimea de drumuri care trec numai prin vrfurile mulimii } v { V V1 k k 1 k + + ,drumul optim ce pleac din vi i trece prin vjare valoarea

1 k , jkj i j ikj ih m ) v , v ( p m++ + Atunci , k , 1 i , } h m { optim m1 k , jkj ik , 1 j1 k1 k , i + +++.Aceast relaie va fi numit relaia de transfer a fazei 1.- Faza 2: determinarea elementelork , 1 i , m1 ki , 1 k++39Ne propunem s determinm un drum de valoare optim de la vrful vk+1 nouadugat ctre un vrf fixat k iV v .Un astfel de drum const din un arc de la vk+1 ctre un vrfk jV v un drum n kV, de la vj la vi .Conform principiului Bellman , acest drum trebuie s fie unul dintre drumurile de lungimeoptim din kV, de lungime ki jm , presupus cunoscut .astfel, pentru un vrf intermediar vj fixat , se obine un drum optim , de valoareki j j , 1 kki j j 1 km h m ) v , v ( p + ++ + .Considernd toate vrfurile intermediare vj posibile n Vk , obinem} m h { optim mki j j , 1 kk , 1 j1 ki 1 k+ +++.Aceast relaie este relaia de transfer pentru zona II .- Faza 3 : determinarea lui 1 k1 k , 1 km++ +.Drumul optim de la vk+1 la vk+1 va corespunde unui vrf intemediar k iV v pentru care valoarea total 1 k1 k , i1 ki , 1 km m+++++ va fi optim .Din pruden , punem n calcul i alegerea ntre valoarea rmnerii pe loc n vk+1

( adic a unui parcurs de valoare zero ) i cea mai bun rut de forma vk+1 vi vk+1 , de valoare 1 k1 k , i1 ki , 1 km m+++++.Aadar , n final obinem

;'+ ++++++ +} m m { optim ; 0 optim m1 k1 k , i1 ki , 1 kk , 1 i1 k1 k , 1 kAceast ultim relaie este relaia de transfer pentru zona III .40- Faza 4: determinarea elementelork , 1 j , i , m1 kj , i+Se urmrete determinarea drumului optim de la vrful k iV vla vrful k jV vn condiiile n care s-a adugat vrful 1 kv+ .apariia acestui nou vrf d ocazia construirii unui drum compus dintr-un prim parcurs vi vk+1 , urmat de ntoarcerea vk+1 vi ; acest drum are drept concurent drumul de la vila vj , din mulimea Vk , de valoare kj , im.Aadar , avem n final { }1 kj , 1 k1 k1 k , ikj i1 kj , im m ; m optim m++++++ .Aceast ultim relaie este relaia de transfer pentru zona IV .pentru aplicaiile practice , n vederea aplicrii algoritmului, matricea ) k (Mva fi mprit n 4 zone , astfel :zona IV zona Izona II zona IIIfiecare zon corespunznd fazei respective a algoritmului.In ce privete oprirea algoritmului, e clar c acesta se termin atunci cnd avem k = n ,deci Vk = V .Totui trebuie reinut c un ntotdeauna matricea ) n (M conine valorile drumurilor optime n graful dat : acest lucru se poate ntmpla, de exemplu , atunci cnd graful dat are circuite.Nu vom aprofunda astfel de situaii .EXEMPLU: fie graful41

Valoarea unui drum este suma valorilor arcelor componente ale drumului .S determinm valorile drumurilor maxime ntre toate perechile de vrfuri ale grafului.Matricea H a valorilor arcelor , completat cu valorile convenionale pentru arcele lips ,este urmtoarea :a b c d ea 0 8 7 - - H = b - 0 5 7 10c - - 0 4 6d - - - 0 3e - - - - 0Pasul 1 : k =2 , V2 = { a ; b } avem 0 8M (2) =- 0Pasul2: k =3 , } c { V V2 3 42 In vederea aplicrii regulilor de transfer, completm matricea M (2) prelund din H linia c i coloanele a , b trecut la dreapta ( transpus ) coloana c i liniile a i b trecut dedesubt ( transpus ) 0 8 - - 0 - 7 5Calculele sunt prezentate mai jos :max { 0 ; 13 - } = 0 max{ 8 ; 13 - } = 8 max{ 7+0 ;5+8} = 13max{- ; 5 - } = - max{0 ; 5 - } = 0 max{ 7- ; 5+0 } = 5max{0- ;- - } = - max{ 8 - ; 0 - } = - max{ 13 - ; 5 - ; 0} = 0Deci avem :0 8 13M (3) = 0 5 0Pasul3: k = 4 , } d { V V3 4 completm matricea M (3) folosind : linia d i coloanele a , b , c din H , la dreapta coloana d i liniile a , b , c din H , dedesubt43astfel :0 8 13 0 5 0 7 4Avem calculele :max{ 0 ; 17 } = 0 max{ 8 ; 17 } = 8 max{ 13; 17 }= 13 max{ +0;7+8;4+13}= 17max{ ; 9 } = max{ 0 ; 9 } = 0 max{ 5; 9 } = 5 max{ ;7+0;4+5}= 9max{ ; 4 } = max{ ; 4 } = max{ 0 ; 4 } = 0 max{ ;7 ;4+0}= 4max{0 ; ; }= max{8 ;0 ; }= max{13 ;5 ;0 }= max{ 0 ; 17 ;9 ;4 } = 0deci :

0 8 13 17 0 5 9M (4) = 0 4 044Pasul 4 : k = 5 , } e { V V4 5 completm matricea M (4 ) folosind : linia e i coloanele a , b , c i d din H , la dreapta coloana e i liniile a , b , c i d din H , dedesubtastfel :0 8 13 17 0 5 9 0 4 0 10 6 3Aplicnd relaiile de transfer obinem n final :a b c d ea 0 8 13 17 20M (5) =b 0 5 9 12c 0 4 7d 0 3e 0Iat semnificaia unor rezultate :13 m513 deci drumul maxim de la a la c are valoarea 13 4 m54 3 deci drumul maxim de la c la d are valoarea 13 52 4m deci un exist drumuri de la d la b , etc.Apoi : determinarea efectiv a drumului optim : drumul maxim de la a la e are valoarea 20 m55 1;pentru a gsi arcele care formeaz acest drum , procedm astfel : 3 17 } 3 17 ; 13 6 ; 10 8 ; 0 { max m55 1+ + + + , unde 44 1m 17) e ; d ( p 345deci : ultimul arc din drumul optim este arcul ( d ; e ) ; 13 4 } 13 4 ; 7 8 ; 0 { max m44 1+ + + , unde 33 1m 13) d ; c ( p 4deci : penultimul arc din drumul optim este arcul ( c ; d ) ; 8 5 } 8 5 ; 7 0 { max m33 1+ + + , unde 22 1m 8) c ; b ( p 5deci : al doileaarc din drumul optim este arcul ( b ; c ) ) b ; a ( p m22 1 , deci primularc din drumul optim este arcul ( a ; b ).In final , am gsit c drumul optim de la a la e este : a b c d e .EXEMPLU: fie graful Valoarea unui drum este suma valorilor arcelor componente .Se cer valorile drumurilor minime ntre toate perechile de vrfuri ale grafului ;- se cere drumul minim de la c la e .46Rezolvare : matricea H a valorilor ( convenionale ) ale arcelor grafului este :a b c d ea 0 -2H =b 4 0 3c -3 1 0 2 5d 2 -30 -4e 0Pasul 1 : pentru V2 = { a ; b } avem :

a bM ( 2 ) = a 0b 4 0Pasul 2 : pentru } c { V V2 3 la M ( 2 ) adugm: linia c i coloanele a , b la dreapta luiM ( 2 ) coloana c i liniile a , b sub M ( 2 ) obinem : 0- 34 0 1 Aplicm relaiile de transfer ale fazelor :min { 0 ; -3 } = 0 min{ ;+1}=min{0+;+}=min{4; -3 } = 4 min{ 0 ; +1 }=0 min{ 4+;0+} =min{ 0 3 ; 4 + 1} = - 3 min{ -3; 0+1} =1 min{ 0 ; -3 ; 1 +} = 047deci0 M (3 ) = 4 0- 3 1 048Pasul 3 : pentru } d { V V3 4 la M ( 3 ) adugm: linia d i coloanele a , b i cla dreapta lui M ( 3 ) coloana d i liniile a , b i c sub M ( 3 ) obinem :

0 24 0- 3- 3 1 0 2Aplicarea relaiilor de transfer este prezentat n tabelul de mai jos :min{0 ; 1 +} = 0 min{;-3 } = min{;+}=min{+0; +;2+}=min{ 4 ; +1 } = 4 min { 0 ; - 3 } = 0 min{ ;+}=min{+4; +0;2+}=min{ - 3 ; +}= -3 min{ 1 ; 2 3 } = -1min{ 0 ; 2+} = 0 min { -3; +1;2+0} = 2min{0+2;4-3;-3+}= 1 min{ +2;0-3;1+}=-3 min{+2; -3;0+}=min{ 0 ; 1+;-3+;+2}=0deci : 0 M ( 4 )= 4 0 - 3 - 1 0 21 - 3049Pasul 4: pentru } e { V V4 5 In vederea aplicrii regulilor de transfer, completm matricea M (4 ) prelund din H linia e i coloanele a , b i c trecut la dreapta ( transpus ) coloana e i liniile a i b i ctrecut dedesubt ( transpus )0 4 0 5 9- 3 - 1 0 21 - 30- 2 3 5 - 4Aplicarea regulilor de transfer este fcut n tabelul urmtor :min{ 0 ; -2}=0 min{;-2 } = min{;-2}=min{;-2 } = min{0-2; +3; +5; - 4}= - 2min{4; +2}= 4 min{0;2+}=0 min{;+2}=min{;+2}=min{4-2;0+3; +5; - 4}= 2min{ -3; -5}= - 3 min{-1; -5}= -1 min{0; -5} = 0 min{ 2 ; -5}= 2 min{-3-2;-1+3;0+5;2- 4}= 5min{1; - 4 } = 1 min{- 3; - 4} = - 3 min{;- 4} = min{ 0; - 4 }= 0 min{1-2;3- 3; +5;0- 4}=- 4min{0+;4+;-3;1+}= min{+;0+;- 1+;3+}= min{+;+;0+;+} = min{+;+;2+;0+}= min{0 ; - 2;+2; -5; - 4} = 050adic

a b c d ea 0 - 2b 4 0 2M ( 5 ) =c - 3 - 1 0 2 - 5d 1 - 30 - 4e 0Iat cteva interpretri ale rezultatelor : 4 m51 2 deci drumul optim de la b la a are valoarea 4 5 m55 3 deci drumul optim de la c la e are valoarea 5 53 2m deci un exist drumuri de la b la c , etc .Drumul minim de la c la e are valoarea 5 : s determinm arcele componente . 2 3 } 4 2 ; 5 0 ; 3 1 ; 2 3 { min m55 3 + + unde: - 2 = p( a; e) ,deci ultimul arc n graf este ( a; e) - 3 = 41 3m 3 } 2 1 ; 3 { min m41 3 + , unde : - 3 = 31 3m 3 0 } 1 4 ; 3 0 { min m31 3 + , unde 3 = p( c , a ) deci penultimul arc este ( c , a ).In final , drumul minim de la c la e este : c a e .==//==51- 9 : PROBLEMEDECONEXIUNEINTR-UNGRAF ORIENTATFie G = ( V , A ) un graf i fie un drum simplu : { 1,2,, k } An graful G. drumul se numete drum elementar , dac funcia 2 0 este injectiv ; drumul elementar pentru care avemV ) ( Im ) ( Im 2 1 se numete drum hamiltonian n graful G. EXEMPLE :- 1: drumula b c d e fde mai jos

un este drum elementar , deoarece trece de dou ori prin vrful c .- 2 : n graful de mai jos :

drumul : a b c e d f este un drum hamiltonian.52- 9.1 : GRAFCONDENSAT Definiie : graful G1 = ( V1 , A1 ) este un subgraf al grafului G = ( V , A )dac avem :) V x V ( A A ; V V1 1 1 1 .EXEMPLU : n exemplul anterior , pct. 2 , subgraful determinat de V1 = { a , c , d, e }este : Definiie : a: un graf G este tare conex dac pentru orice dou vrfuri V v , vj i, avem : exist drum de la vi la vj ; exist drum de la vj la vi . b: o component tare conexa grafului G este un subgrafG1 = ( V1 , A1 ) al lui G , unde G1 este un graf tare conex G1 este maximal n raport cu proprietatea de conexiune .Precizare : maximalitatea are aici sensul urmtor :pentru orive vrf 1V \ V vi , subgraful lui G determinat de ctre 1V } v {i nu este tare conex. pentru un vrfV v 0fixat , definim urmtoarele mulimi asociate lui v0 : EXT (v0 ) = { vi | exist un drum de la v0 la vi } INT (v0 ) = { vj | exist un drum de la vj la v0 } C (v0 ) este componenta tare conex care l conine pe v053LEM : } v { ] ) v ( INT ) v ( EXT [ ) v ( C0 0 0 0 In adevr , fie } v { ] ) v ( INT ) v ( EXT [ v , vj i 0 0 0 ; atunci exist drumuri 'd1 de la vi la v0 i ' 'd1 de la v0 la vi exist drumuri 'd2 de la vj la v0 i ' 'd2 de la v0 la vjAtunci : ' ' 'd d2 1 este un drum de la vi la vj ' ' 'd d1 2 este un drum de la vj la vi , deci v0 , vi i vj aparin aceleiai componente tare conexe.Observare : fie || dij || i ,j = 1,n matricea sintetic a drumurilor grafului dat : atunci

. } d | V v { ) v ( INT} d | V v { ) v ( EXTji j iij j i11 Exemplu : Un graf G are urmtoarea matrice sintetic a drumurilor

v1v2v3 v4v5v6v11 1 1 1 1 1v21 1 1 1 1 1v31 1 1 1 1 1v40 0 0 1 1 1v50 0 0 1 1 1v60 0 0 0 0 1Atunci : } v , v , v { ) v ( INT }; v , v , v , v , v , v { ) v ( EXT3 2 1 1 6 5 4 3 2 1 1 deci } v , v , v { ) v ( C3 2 1 1 } v , v , v , v , v { ) v ( INT }; v , v , v { ) v ( EXT5 4 3 2 1 1 6 5 4 4 deci } v , v { ) v ( C5 4 454LEM : fie C1 ,C2 dou componente tare conexe n graful G : atunci sau C1 = C2 sau 2 1C CDemonstraie : rezult din condiia de maximalitate a cmponentelor tare conexe.Fie un graf G = ( V , A ) avnd componentele tare conexe C1 ,C2 ,, Ck ; definimgraful condensat G* = ( V* , A* ) corespunztorgrafului dat astfel : G* = { C1 ,C2 ,, Ck } avem (Ci ,Cj ) *A dac : j j i iC v ; C v astfel ca A ) v , v (j iEXEMPLU: fie graful Componentele tare conexe ale acestui graf sunt C1 = { a , b , c } i C2 = { d ; e }.Avem: *A ) C , C (A ) d , b (C dC b 2 1 21deci graful condensat corespunztor va fi :

-9.2 : DRUMHAMILTONIANINTR-UNGRAFFRCIRCUITE55Definiie : puterea de atingere) v ( pia vrfuluiV vi n graful ) A , V ( G este egal cu cardinalul mulimii) v ( EXTi.Lem : fie n , j , iij|| d || D1 matricea sintetic a drumurilor grafului ) A , V ( G, avnd }. v ,..., v , v { Vn 2 1 Atunci ) v ( p ) v ( p dj i ij 1.In adevr , dac 1 ijd, atunci orice vrf atins de ctre vj poate fi atins i de ctre vi , deoarece exist drum de la vi la vj .Este clar c printr-oeventual renumerotare a vrfurilor , se poate aranja s avem 1 ijd j i.Deasemeni , primul 1 de pe fiecare linie a matricii D triangularizate corespunde unui drum format dintr-un singur arc .56In fine, s observm c ntr-un graf) A , V ( Gfr circuite , avnd } v ,..., v , v { Vn 2 1 , avem 211) n ( n) v ( pn , ii ,ceeace rezult din faptul c 11 1 1ijdn , j , iijn , j , iijn , iid d ) v ( p.Din cele prezentate se deduce urmtorul rezultat :Teorem ( CHEN): Fie G un graf finit fr circuite : atunci n G exist drum hamiltonian 211) n ( n) v ( pn , ii unde n este numrul de vrfuri ale grafului.Pentru a gsi efectiv drumul hamiltonian, se scriu vrfurile grafului n ordinea descresctoare a puterilor de atingere.- 9.3 : Determinarea drumului hamiltonian ntr-un graf cu circuite :Sobservmnticungraf condensat estegraf frcircuite:nadevr , fieG*graful condensat corespunztor unui graf finit G , i fie C1 ,C2 ,, Ck componentele tare conexe ale lui G .Presupunem c n G ar exista circuitul

Atunci ar fi valabil urmtoarea schem :57 adic - fie2 2 1 1 2 1C v , v , C v , v' ' ' ' ' ' (cazul ncareC1sauC2arconinecteun singur vrf se trateaz asemntor )- C1fiindcomponentconex, exist'd1drumdela' 'v la v2 1i'd2drumdela ' 'v la v1 2- C2fiindcomponentconex, exist' 'd1drumdela' ' ' 'v la v2 1i' 'd2drumdela ' ' ' 'v la v1 2- atunci' 'd2 2 ar fi undrumdela' ' 'v la v1 2i'd1 1 drumdela ' ' 'v la v2 1, deci C1 , C2 un ar fi componente tare conexe, nefiind maximale .Este evident proprietatea urmtoare :dac n G* un exist drum hamiltonian , atunci nici n G un exist drum hamiltonian Din observaiile precedente , rezult o metod de construire a drumului hamiltonian ntr-un graf cu circuite :58- se determin graful condensat al grafului dat ;- dac n graful condensat un avem drum hamiltonian, atunci nici n graful dat un exist drum hamiltonian , i rezolvarea se termin- dacngrafulcondensat se gseteun drum hamiltonian ,d*,atuncitrecem la pasul urmtor :o se ntocmete o schem care conine componentele grafului condensat , n ordinea n care apar n d* ;o n fiecare component se trec drumurile hamiltoniene din acea component- se conecteaz drumurile din componente cu arcele lui d* .- se stabilete dac astfel se obin sau un drumuri hamiltoniene n graful dat .EXEMPLU : Graful G are ca mulime de vrfuri V = { a,b,c,d,e,f,g,h }: matricea arcelor este urmtoarea a b c d e f g ha 1 1H = b 1c 1 1 1d 1 1e 1f 1g 1 1 1h 1 1 1Valorile de zero din matricea H un au mai fost trecute n tabel.Matricea sintetic a drumurilor grafului dat este urmtoarea :a b c d e f g ha 1 1 1 1 1 1 1 1D = b 0 1 1 1 1 1 1 0c 0 1 1 1 1 1 1 0d 0 0 0 1 1 1 0 0e 0 0 0 1 1 1 0 0f 0 0 0 1 1 1 0 0g 0 1 1 1 1 1 1 0h 1 1 1 1 1 1 1 1Acum determinm componentele tare conexe ale grafului : ' } h , a { ) a ( C} h , g , f , e , d , c , b , a { ) a ( EXT} h , a { ) a ( INT;59 ' } g , c , b { ) b ( C} g , f , e , d , c , b { ) a ( EXT} h , g , c , b , a { ) b ( INT; ' } f , e , d { ) a ( C} f , e , d { ) a ( EXT} h , g , f , e , d , c , b , a { ) d ( INTAcum rescriem matricea H , cu vrfurile n ordinea n care apar n componente , adic{ a , h , b , c , g , d , e , f } : obinema h b c g d e fa 1 1H1 = h 1 1 1b 1c 1 1 1g 1 1 1d 1 1e 1f 1Graful condensat G* va fi

Drumul hamiltonian n graful G* va fi : d* = { C(a) ; C(b) ; C(d) }.Tabelul final careconinecomponentelescrisenordineadatded*precumi drumurile hamiltoniene din cadrul componentelor apare mai jos :60C(a) C(b) C(d)drumuri hamiltonienen C(a)drumuri hamiltonienen C(b)drumuri hamiltonienen C(d)a hh ab g cg c bc b gf d ed e fe f dPentru a racorda sfritul unui drumdintr-o component cu nceputul unui drumdin componenta urmtoare, putem folosi arcele :- de la componenta C(a) la componenta C(b) : arcul a b ;- de la componenta C(b) la componenta C(d) : arcul c f i arcul c d .In final , drumurile hamiltoniene n graful dat sunt : d1 = { h ; a ; b; g ; c ; f ; d ; e } d2 = { h ; a ; b ; g ; c ; d ; e ; f }E N D61