Curs nr. 1 NOIUNI INTRODUCTIVETeoria grafurilor, la nceputurile ei, s-a dezvoltat paralel cu algebra. Grafurile au multiple aplcaii practice, fiind strns legate de multe ramuri ale matematicii (cercetri operaionale, teoria grupurilor, teoria numerelor), dar sunt folosite i ca modele matematice n rezolvarea unor probleme tehnice, economice, etc. Studiul grafurilor i are originea n lucrrile lui Euler din 1736, n care studia problema podurilor de la Knigsberg. Oraul Knigsberg se afl aproape de punctual de vrsare a rului Pregolea n Marea Baltic. Rul are pe teritoriul oraului dou brae confluente iar n punctual de confluen se afl o insul, numit Curtea Hanului1. Aceast insul este legat de maluri prin cinci poduri. Peste fiecare bra al rului mai exist cte un pod. Problema care a aprut cerea s se gseasc un traseu continuu care s treac o singur dat pe fiecare din cele apte poduri.(vezi figura 1.) Euler a fost primul care a artat c aceast problem nu are soluie. Fig.1.1.

Prima carte de teoria grafurilor a fost publicat de D. Knig n 1936, Theorie der endlichen und unendlichen Grphen, urmat de cartea lui C. Berge n 1957 Thorie des graphes et ses applications.1

H. R. Radian, T. J. Radian, Recreaii matematice, Editura Albatros, Bucureti, 1973.

1

Fie X o mulime finit nevid, X={x1, x2 ,,xn }. Se numete graf o pereche G = (X, U) format din mulimea X de vrfuri sau noduri i din mulimea U={u1, u2, , um } de perechi de vrfuri numite arce sau muchii. Reprezentarea grafurilor poate fi fcut n diferite moduri n funcie de cine este utilizatorul. Dac este calculatorul, este de preferat ca graful s fie dat cu ajutorul matricei sale de adiacen. Altfel, oamenii, prefer vizualizarea grafului sub forma unei colecii de puncte legate prin linii, ceea ce implic darea unor informaii geometrice despre graf. Cardinalul mulimii X, se noteaz |X|, i se numete ordinul grafului G. n cele ce urmeaz vom lucra numai cu grafuri finite. n mulimea U putem avea mai multe perechi identice. Dac numrul lor nu depete un numr natural q, spunem c G este un q-graf Un 1-graf se mai numete i graf orientat. n aceast situaie U este o submulime a produsului cartezian X X . Atunci orice element u U este o pereche ordonat, de forma u = ( x, y ), cu x, y X i l numim arc. Vrful x se numete extremitatea iniial iar vrful y se numete extremitatea final. n acest caz vrfurile x i y se numesc adiacente. n cazul n care nu tinem cont de orientarea arcelor, atunci (x, y) nu mai este o pereche ordonat. Deci, U va fi format din submulimi ale mulimii X, cu dou elemente, {x, y}, sau cu un singur element {x}. n aceast situaie ele se vor numi muchii, respectiv bucle. Dac graful G nu are bucle i nu conine dou muchii egale(egalitate ca mulimi), adic U este o submulime a mulimii prilor mulimii X, cu dou elemente, atunci perechea G = (X, U) se numete graf simplu sau neorientat. Definiia 1.1. Fie G = (X, U) un graf , x X un vrf al su. i) Mulimeax+

= { y X / (x, y) U }

2

se numete mulimea succesorilor vrfului x. Deci orice element y x se numete succesor al vrfului x. n cazul grafurilor orientate, x numete semigradul exterior al vrfului x i-l notm cu d+x. ii) Mulimea+

+

se

x = { y X / ( y, x) U }se numete mulimea predecesorilor vrfului x. Deci orice element y x se numete predecesor al vrfului x. n cazul grafurilor orientate, x numete semigradul interior al vrfului x i-l notm cu iii) Mulimeax

se

dx-.

=

+ x

x

se numete mulimea vecinilor vrfului x sau a vrfurilor adiacente cu vrful x. n cazul grafurilor orientate, dx = d+x + d x se numete gradul vrfului x. n cazul grafurilor neorientate, gradul unui vrf x este este numrul muchiilor pentru care x este o extremitate, deci: 1 + d x = (d + x + d x ) = x = x . 2 Definiia 1.2. Fie G = (X, U) un graf i A X . i) Mulimea

+ ( A) = {u U / u = (a, x), a A, x X \ A}.se numete mulimea arcelor incidente cu A ctre exterior. ii) Mulimea

( A) = {u U / u = ( x, a), a A, x X \ A}.

3

se numete mulimea arcelor incidente cu A ctre interior. Mulimea arcelor incidente cu A este mulimea:

( A) = + ( A) ( A).Definiia 1.3. Fie G = (X, U) un graf i = (u1 , u 2 ,..., u q ) un ir de arce. i) Dac irul are proprietatea c extremitatea final a arcului u i coincide cu extremitatea iniial a arcului u i +1 , atunci se numete drum. Numrul de arce care compun un drum se numete lungimea drumului, n cazul nostru lungimea fiind q. Un drum se numete elementar dac nu folosete de dou ori acelai vrf, iar dac nu folosete de dou ori acelai arc se numete simplu. Dac extremitatea final a arcului u q coincide cu

extremitatea iniial a arcului u1 , drumul se numete circuit. ii) Dac irul are proprietatea c o extremitate a arcului u i coincide cu o extremitate a arcului u i +1 , iar cealalt extremitate a arcului u i +1 coincide cu o extremitate a arcului u i + 2 , atunci se numete lan. Numrul de arce care compun un lan se numete lungimea lanlui, n cazul nostru lungimea fiind q. Un lan se numete elementar dac nu folosete de dou ori acelai vrf, iar dac nu folosete de dou ori acelai arc se numete simplu. Dac o extremitate a arcului u q , necomun cu arcul u q 1 , coincide cu o extremitate a arcului u1 , necomun cu arcul u 2 , lanul se numete ciclu. n cazul grafurilor neorientate cele dou noiuni, de lan i drum, coincid. Definiia 1.4. Fie G = (X, U) un graf A X , V U , o submulime de vrfuri, respectiv arce. i) Subgraful generat de submulimea de vrfuri A este un graf, G ( A) = { A,U ( A)}, unde U ( A) = {u U / u = ( x, y ), x, y A}.

4

ii) Graful parial al unui graf G, generat de submulimea de arce V, este graful G= (X, V), adic graful care are aceleai vrfuri ca i G dar arcele sale sunt din mulimea V. Definiia 1.5. i) Fie G = (X, U) un graf. El este tare conex dac pentru oricare dou vrfuri x, y X exist un drum de la x la y i un drum de la y la x. O component tare conex a grafului G este un subgraf G(A) al lui G, cu A X , care este tare conex i este maximal fa de aceast ptoprietate n raport cu incluziunea.(Acest lucru nseamn c dac lum x X \ A, subgraful lui G, generat de B = A {x}, G ( B ), nu mai este tare conex). ii) Un graf G este conex dac pentru orice dou vrfuri diferite, x, y X , putem gsi un lan care s aib ca extremiti aceste dou vrfuri. O component conex a grafului G este un subgraf G(A) al lui G, cu A X , care este conex i este maximal fa de aceast ptoprietate n raport cu incluziunea.(Acest lucru nseamn c dac lum x X \ A, subgraful lui G, generat de B = A {x}, G ( B ), nu mai este conex). Fie G = (X, U) un graf. Pe mulimea X definim urmtoarea relaie binar: x ~ y dac i numai dac x = y sau exist un drum de la x la y i un drum de la y la x. Aceast relaie este o relaie de echivalen, iar clasele de echivalen ale acestei relaii de echivalen sunt componentele tare conexe ale grafului G. Dac pe mulimea X definim urmtoarea relaie binar: x y dac i numai dac x = y sau exist un lan care are ca extremiti pe x i y, atunci aceast relaie este o relaie de echivalen, iar clasele de echivalen ale acestei relaii de echivalen sunt componentele conexe ale grafului G. tim c o relaie de echivalen determin pe mulimea pe care a fost dat o partiie, deci componentele conexe si tare conexe ale unui graf definesc o partiie pe mulimea de vrfuri X. Definiia 1.6. Fie G = (X, U) un graf, x X un vrf dat. Definim

2 x = { y x } = x (x ),..., k x = x ( ( k 1) x ) ,

+

+

+

+

+

+

+

5

iar+ + x = {x} x 2 x ... o submulime a mulimii X format din x i din toate vrfurile care se gsesc pe drumuri care pleac din x. Cu aceste notaii definim aplicaia:

: X X , ( x) = x i obinem graful G = ( X , ), numit nchiderea tranzitiv a grafului G.

Definiia 1.7. Fie G = (X, U) un graf, x X un vrf dat. Definim

2 x = { y x } = x (x ),..., k x = x ( ( k 1) x ) ,iar x = {x} x 2 x ... o submulime a mulimii X format din x i din toate vrfurile care se gsesc pe drumuri care se termin n x. Cu aceste notaii definim aplicaia:

: X X , ( x) = x i obinem graful G = ( X , ), numit nchiderea tranzitiv invers a grafului G.

Folosind notaiile de mai sus, pentru orice dou vrfuri x, y X , definim relaia binar: x y x y i y x x y y ,

6

care este o relaie de echivalen. Atunci, clasa de echivalent a vrfului y este C ( y ) = y y , adic tocmai componenta tare conex a vrfului y. Definiia 1.8. Un graf orientat G = (X, U) este complet, dac orice dou vrfuri sunt legate printr-un arc sau dou arce n sensuri opuse, adic pentru orice x, y X , avem ( x, y ) U ( x, y ) U . Dac graful nu este orientat, atunci el este complet dac i numai dac orice dou vrfuri sunt unite printr-o muchie. n figura 1.2. avem graful neorientat complet de ordin 5, K5. Fig. 1.2.1

2

5

3

4

Definiia 1.9. Fie G = (X, U) un graf. Fie A X o submulime de varfuri ale grafului G. A este o clic a grafului G dac subgraful generat de A, G(A), este complet.

7

8

Curs nr. 2 DRUMURI OPTIME NTR-UN GRAF 1. Matrice asociate unui graf Fie G = (X, U) un 1-graf (sau graf orientat), cu X = {x1, x2 ,., xn } mulimea vrfurilor sale. Acestui graf i se asociaz o matrice A = ( ai , j ) i , j =1,n Mn (), astfel:

1, dac xi i x j sunt adiacente, adic ( xi , x j ) U , aij = 0, altfel.Dac avem o bucl ( xi , xi ) U, atunci aii = 1, n caz contrar aii = 0. Aceast matrice se numete matricea de adiacen asociat grafului G. Folosind programul Mathematica 4, putem da un graf cu ajutorul matricei sale de adiacen astfel:>lp / PA (li) = 0, li valoare proprie de ordin de multiplicitate mi }, unde PA( ) este polinomul caracteristic al matricei A. Putem reprezenta spectrul unui graf sub forma unei matrice S M2,p (), 2 ... p . SG= 1 m m ... m 2 p 1 Exemplul 2.1.2. Pentru graful neorientat complet de ordin cinci, K5 , matricea de adiacen este: 0 1 1 1 1 1 0 1 1 1 4 1 A = 1 1 0 1 1 , iar S K 5 = 1 3 . 1 1 1 0 1 1 1 1 1 0

3

Numim valori proprii pentru graful neorientat G valorile proprii corespunztoare matricei sale de adiacen A iar polinomul caracteristic PA(l) ataat matricei de adiacen A va fi polinomul caracteristic al grafului neorientat G, notat la fel:PA(l) = ln - 1ln-1 + 2ln-2 - 3ln-3++(-1)nn ,

unde i reprezint suma minorilor principali ai matricei A, de ordin i. Polinomul caracteristic al matricei de adiacen A ne poate da diverse informaii despre graful studiat, dup cum vom vedea n cele ce urmeaz.Propoziia 2.1.3. Fie G=(X, U) graf neorientat , A matricea sa de adiacen i PA(l) polinomul caracteristic asociat. Atunci: a) 1 = 0; b) 2 = - |U| = i j ;i j

c) - 3 = 2N, N este numrul triunghiurilor care pot fi formate cu vrfurile grafului G. Demonstraie: a) tim c 1 = Tr A = 0. b) Deoarece i este suma minorilor principali ai matricei A, de ordin 0 1 , i, avem c 2 este suma tuturor minorilor de ordin doi de forma 1 0 `2 care sunt n numr de C n . Un astfel de minor, care are valoarea -1, corespunde fiecrei perechi de vrfuri adiacente din graf. Atunci avem c 2 =- |U|, iar ultima relaie rezult folosind relaiile lui Vite. c) Minorii principali de ordin trei ai matricei A sunt de forma:

0 1 1 0 1 0 0 1 1 1 0 1, 1 0 0, 1 0 0 , 1 1 0 0 0 0 1 0 0

4

primul avnd valoarea 2 iar ultimii doi sunt nuli. Acest minor nenul corespunde unui triunghi pe care-l putem forma cu vrfurile grafului. Deci -3 = 2N.Propoziia 2.1.4. Fie G=(X, U) un graf neorientat. Atunci numrul drumurilor de lungime l din G care unesc vrfurile xi cu xj , xi x j , este dat de elementul aflat pe poziia (i,j) din matricea Aq, unde A este matricea de adiacen a grafului G. Demonstraie: Prin inducie dup q. Pentru l=0, deoarece A0 =I, afirmaia este adevrat. Pentru q=1, Aq=A, obinem matricea de adiacen, deci afirmaia este adevrat. Presupunem afirmaia adevrat pentru q i o demonstrm pentru q+1. Avem: n n n (q) A ( A q +1 ) ij = aik ( q 1) a kh a hj . A q +1 = A q A = aik a kj k =1 h =1 k =1 i , j =1,n

n cazul nostru, din ipoteza de inducie,

ak =1

n

( q 1) ik

a kh reprezint numrul

tuturor drumurilor de lungime q ntre xi i xh. Dac xh este adiacent cu xj atunci ahj =1, altfel ahj =0 i pentru h{1,2,,n} vom obine toate drumurile de lungime q+1 dintre i i j.Definiia 2.1.5. i) Numrul muchiilor pe care le are cel mai scurt drum dintre xi i xj se numete distana n graful neorientat i conex G dintre vrfurile xi i xj. ii) Se numete diametru al grafului neorientat i conex G cea mai mare distan dintre oricare dou vrfuri ale grafului dat. Propoziia 2.1.6. [Biggs] Fie G=(X, U) un graf conex neorientat cu n vrfuri i de diametru . Atunci graful G are cel puin +1 valori proprii distincte.

5

Demonstraie. Fie A matricea de adiacen a grafului G i fie xi, xj X, dou vrfuri ale grafului G, astfel nct exist ( xi , xi1 ), ( xi1 , xi2 ),..., ( xi 1 , xi ), cu xi = xj , drum de lungime ntre xi i xj .

poziia (i, ik) un element nenul, iar matricele I, A,, Ak-1 pe aceeai poziie, (i, ik), au zero. ntr-adevr, deoarece drumul dintre xi i xj este cel mai scurt, de lungime , rezult c drumul dintre xi i xik , de lungime k, k , este cel mai scurt. Dac pe poziia (i, ik) din matricea Ak-1 avem un element nenul, rezult c ntre xi i xik avem un drum de lungime k-1, deci nseamn

Pentru orice k 1, , vom considera matricea Ak. Deoarece ntre xi i xik avem cel puin un drum de lungime k, rezult c n Ak vom avea pe

c putem elimina un vrf din irul { xi , xi1 ,..., xik } i atunci ntre xi i xj vom avea un drum de lungime strict mai mic dect , fals. Din cele de mai sus, rezult c matricele {I, A,, A } sunt liniar independente n Mn (), deci polinomul caracteristic are cel puin +1 valori distincte. ntr-adevr, dac am avea t valori proprii distincte, cu t< +1, atunci polinomul minimal al matricei A ar avea gradul t. De aici rezult c matricele {I, A,, At} ar fi liniar dependente, fals.

6

7

Curs nr. 3 DRUMURI OPTIME NTR-UN GRAF (continuare)

Propoziia 2.1.7. a) Fie G un graf neorientat cu n vrfuri . Atunci graful G este conex dac i numai dac matricea (A+I)n-1 nu are nici un element nenul. b) Dac G este un graf neorientat, cu n vrfuri i cu m muchii, care are valorile proprii l1 l2 ln, atunci avem: i) ii)

i =1

n

i =1 n

i

=0;= 2m ;

2 i

iii) 1

2m(n 1) . n

Demonstraie: a) Presupunem c graful G este conex. Rezult c ntre orice dou vrfuri avem un drum. Fie X={x1,x2,,xn} vrfurile grafului. Fie d diametrul grafului. Atunci ntre orice dou vrfuri, xi i xj, exist un drum care are lungimea maxim d n 1, l pe care o notm lij. Atunci matricea A ij va avea pe poziia (i,j) un element nenul. Deci, n matricele A, A2,..., Ad nu exist o poziie (i,j) care s fie nul n toate aceste d matrice, dect dac i = j. Atunci n matricele I, A, A2,..., Ad nu exist o poziie (i,j) care s fie nul n toate, deci (A+I)n-1 nu are nici un element nenul. Reciproc, deoarece (A+I)n-1, are numai elemente nenule, avem c ntre orice dou vrfuri distincte ale grafului G avem un drum. Dac nu ar fi aa, pentru orice t 1, n 1 , At ar avea pe poziia (i, j) element nul, fals. b) Afirmaia i) este evident.2 ii) Avem c 0 = (1 + 2 + ... + n ) = 1 + 2 + ... + 2 + 2 i j , de une rezult 2 n 2 i j =1 n

c + + ... + = 2m. iii) Folosim inegalitatea Cauchy-Schwarz pentru numerele reale (l2 ln) i (1,1,,1). Rezult2 1 2 2 2 n

n n n 2 2 2 i i (n 1) 1 2m 1 (n 1) 1 [1 + (n 1)] 2m(n 1) i=2 i=2 Demonstra 2m(n 1) 2 . 1 n ia este astfel ncheiat.

2

(

)

1

Definiia 2.1.8. a) Dou grafuri G=(X, U), i G=(X, U) se numesc izomorfe dac i numai dac exist f : X X ' aplicaie bijectiv astfel nct aplicaia g : U U ' , g (uij ) = u 'ij , unde uij = (xi , x j ) U i u 'ij = ( f ( xi ), f (x j )) U ' s fie o bijecie. b) Dac G=(X, U) este un graf, se numete automorfism al lui G o aplicaie bijectiv f : X X cu proprietatea c exist aplicaia g : U U , definit ca la punctul a), care s fie bijecie. Mulimea automorfismelor grafului G formeaz, n raport cu operaia de compunere a aplicaiilor, un grup, numit grupul automorfismelor grafului G i notat Aut(G). Dou grafuri izomorfe au aceeai matrice de adicen, deci aceleai valori proprii i acelai polinom caracteristic, dar exist i grafuri neizomorfe care au aceeai proprietate Definiia 2.1.9. Dou grafuri se numesc cospectrale dac sunt neizomorfe i au aceleai valori proprii cu aceleai ordine de multiplicitate. Un exemplu de 2 grafuri cospectrale a fost dat n 1971 de Cvetkovi. Urmtoarele dou grafuri cu 6 elemente, din figura 2, sunt neizomorfe, conexe, cospectrale si au acelai polinom caracteristic P(l)=l6-7l4-4l3+7l2+4l-1[Biggs]: Fig. 2.1.

Definiia 2.1.10. Un graf se numete regulat de grad p dac gradul oricrui vrf al su este p. Propoziia 2.1.11. [Biggs] Fie G = (X,U) un graf regulat de ordin p. Sunt adevrate afirmaiile: i) p este valoare proprie pentru graful G. ii) Dac G este conex, atunci p este valoare proprie de multiplicitate 1. iii) Valoarea proprie p este cea mai mare, adic pentru orice l, valoare proprie a grafului G avem |l| p. Demonstraie. i) Fie G=(X, U), X = n , w=(1,1,...,1)tMn,1 () i A matricea de adiacen a grafului G. Deoarece graful este regulat de grad p, avem c suma elementelor de pe fiecare linie (coloan) din A este p, deci Aw=pw, de unde rezult c p este valoare proprie pentru A i w este vector propriu.

2

ii) Fie uMn,1 () un vector nenul astfel nct Au=pu, u=(u1,u2,,un).Presupunem c uj = max ui . Din Au=pu rezult c pu j = a jk uk . De aici obinem cn

pu j = uk , I {1, 2,..., n} , I este mulimea indicilor poziiilor de pe linia j unde avem 1k I

i =1, n

k =1

n matricea de adiacen. Se observ c I = p . Datorit maximalitii lui uj, rezult c

uj=uk ,"kI, deci p+1 elemente din vectorul u sunt egale. n cazul n care graful G este conex, repetnd procedeul, rezult c u1 = u2 = = un. ntr-adevr, pentru k I , avem c uk = ut, pentru orice t I 1 , cu I1 mulimea indicilor poziiilor de pe linia t unde avem 1 n matricea de adiacen, .a.m.d. Avem atunci c u = w , deci subspaiul corespunztor valorii proprii p are dimensiunea 1. iii) Presupunem Ax = lx, x 0, xMn,1 () i fie xj = max xi . Cu notaiilede la punctul ii), avem urmtoarea relaie

x j = xk ,k I

i =1, n

deci

xj =

xkI

k

x k p x j p. kI

Propoziia 2.1.12. (Hoffman 1963) Graful G=(X,U) este conex i regulat de ordin p dac i numai dac exist r i a0, a1,...,ar astfel nct E=a0I+a1 A++arAr, unde E = (eij ) i , j =1,n , eij=1, " i,j = 1, n , iar A este matricea de adiacen a

grafului G.Demonstraie. Presupunem c E=a0I+a1 A++arAr . Vom nota cu dj graduln n

vrfului xj. Obinem:

aik ekj = di ik =1

ek =1

ik

akj = d j . Se observ c AE=EA, de unde

obinem c di=dj, "i, j 1, n arbitrari alei, deci graful este regulat. Presupunem c G nu este conex. Atunci exist dou vrfuri xi i x j care nu sunt adiacente i ntre care nu exist nici un drum. De aici rezult c pe poziia (i, j) din Ak avem zero pentru orice k 0. Atunci orice expresie de forma a0I+a1 A++akAk va avea un zero pe poziia (i, j) i deci nu poate fi matricea E. Reciproc, presupunem c graful G este conex i regulat de grad p. Atunci p este valoare proprie pentru G de ordin de multiplicitate 1. Polinomul minimal al matricei A va fi de forma PA(l )= (l - p)Q(l), deci AQ(A)=pQ(A) . Rezult c fiecare coloan a matricei Q(A) este vector propriu al grafului G, corespunztor valorii proprii p, deci este de forma i w, i = 1, n , w = (1,1,...1) , i 0 i deoarece Q(A) este o matrice simetric, rezult c i = , i = 1, n , deci Q(A) = E.

3

Definiia 2.1.13. Matricea A = (aij ) i , j =1,n Mn () se numete circular

dac i numai dac aij = a1, k-1 unde k j-i+1mod n , k {1,2, , n}. Dac se cunoate prima linie ntr-o matrice circular, atunci putem determina orice alt linie i pornind de la aceasta, mutnd ultimele i-1 elemente ale liniei 1 (de la n pn la n-i+1) n fa. Se procedeaz astfel: se mut elementul de pe poziia n n faa celui de pe poziia 1, apoi elementul care era pe poziia n-1 (i care acum este pe poziia n) se trece n faa celui care are actuala poziie 1 (i care iniial avea poziia n), .a.m.d. Vom nota cu C matricea circular care are prima linie (0,1,0,...,0).Propoziia 2.1.14. Fie A Mn () o matrice circular a crei prim linie este (a1, a2,, an). Atunci avem:

a) A = a j C j 1 ;j =1

n

b) Valorile proprii sunt i = a j ( j 1) i , unde 1, ,..., n 1 sunt rdcinile dej =1

n

ordin n ale unitii.Demonstraie. a) Notm cu L1, L2,..., Ln liniile matricei C. Se observ c Cn=In iar matricea Cj, j= 1, n se obine din matricea C mutnd primele j-1 linii la sfrit. De exemplu C2 va avea prima linie pe L2, linia 2 pe L3 i ultima linie pe L1. C3 va avea prima linie pe L3, linia 2 pe L4, penultima pe L1 i ultima pe L2, .a.m.d. b) Din Cn=In rezult c Cn-1+Cn-2+...+C+In =0, deci valorile proprii ale matricei C sunt rdcinile de ordin n ale unitii. Atunci vom avea c Cj-1x= j 1 x, j =1, n , cux Mn,1 (). Obinemn

Ax = ( a j Cj =1

n

j 1

) x, deci

Ax = ( a j j 1 ) x . Rezult cj =1

n

= a j j 1 este o valoare proprie pentru rdcina de ordin n a unitii. Lundj =1

toate rdcinile de ordin n ale unitii, i , vom obine relaia din enun Definiia 2.1.15. Un graf G=(X,U) se numete circular, dac matricea sa de adiacen este circular. Din cele de mai sus, rezult c pentru un graf circular valorile proprii sunt:

i = a j ( j 1)i , i = 0, n 1 .j =2

n

Deorece matricea unui graf circular este simetric, rezult c valorile sale proprii sunt reale i nu n mod necesar distincte. Ca exemplu, avem graful complet Kn, care este circular i care are ca valori proprii 1 = n 1, simpl i 2 = 1, multipl de ordin n-1.

4

Definiia 2.1.16. Fie G=(X,U) un graf. Graful linie, L(G), asociat lui G este graful ce are ca mulime de vrfuri mulimea U iar dou vrfuri in L(G) sunt unite printro muchie atunci cnd muchiile corespunztoare n G au n comun un vrf.

Fie G=(X,U) un graf cu X= {x1 , x 2 , ... , x n }, U = {u1 , u 2 ,..., u m } . Vom defini matricea F= ( f ij ) i =1,n Mn x m(),j =1, m

1, dac xi este o extremitate a muchiei u j , fij = 0, altfel.

Propoziia 2.1.17. [Biggs] Dac A este matricea de adiacen a grafului G i AL matricea de adiacen a grafului L(G), atunci avem: i) FtF = AL+2Im; ii) Dac G este regulat de ordin p, atunci FFt = A+pIm. Demonstraie. i)

(F F ) = ft m ij k =1

ki

f kj . De aici rezult c elementele

(F F )t

ij

reprezint numrul de vrfuri xk ce sunt incidente cu muchiile ui i uj , adic tocmai elementul (aij)L, pentru i j . De aceea, cnd i = j, ( F t F ) ii reprezint numrul de vrfuri xk ce sunt incidente cu muchiile ui , deci avem 2 pe diagonala pricipal.

ii) Avem ( FF t ) ij = f ik f jk , deci elementele ( FF t ) ij reprezint acele muchii ukk =1

m

care au ca extremiti vrfurile xi i xj , adic tocmai elementul aij, pentru i j . Pentru i = j, elementul ( FF t ) ii reprezint numrul muchiilor uk care pleac din vrful xi, adic tocmai gradul vrfului care este p, deci pe diagonala principal vom avea p. Propoziia 2.1.18. Dac l este o valoare proprie pentru graful linie L(G), atunci l -2. Demonstraie. Matricea FtF este pozitiv definit, deci valorile proprii ale matricei FtF sunt pozitive. Dar AL=FtF-2In i obinem c t det ( AL I n ) = det F F ( + 2)I n , deci valorile proprii ale lui AL sunt -2.

(

)

EXERCIII Exerciiul 1. Fie EMn(), E = (eij )i , j =1, n , eij=1, " i,j = 1, n . Dac G=(X,U) este

un graf regulat de grad p i A matricea sa de adiacen, atunci AE=EA=pE.

5

Exerciiul 2. Cu notaiile de mai sus, fie G=(X,U) un graf regulat de grad p, conex cu X = n i p>l1>>lt-1, valorile sale proprii distincte. Dac notm Q(l) =

( ) vom avea:i i =1

t 1

n E = Q( p) Q( A) . Rezolvare. Avem relaia Q(A) = E, cu . Valorile proprii corespunztoare matricei Q(A) sunt Q(p)sau Q(li) , i = 1, t 1 . Dar Q(li) = 0, pentru i =

1, t 1 . Singura valoare proprie nenul a matricei E este n ( Demonstrai acest Q( ) lucru! ), deci n = Q( ) de unde rezult = . nExerciiul 3. Vom nota cu C matricea circular care are prima linie (0, 1, 0,,0). S se arate c valorile proprii ale acestei matrice sunt rdcinile de ordin n ale unitii: 1, ,..., n 1 .

6

Curs nr. 4

DETERMINAREA MATRICEI DRUMURILOR INTRUN GRAF. DETERMINAREA COMPONENTELOR TARE CONEXEn cele ce urmeaz ne vom ocupa de grafuri orientate sau de 1-grafuri. Fie G=(X,U) un graf i A matricea sa de adiacen. Definiia 2.1. Matricea drumurilor grafului G, notat A* = a*ij astfel:

( )

i , j =1, n

, este definit

(a ) = * ij

1, dac exist n graf un drum ce pleac din xi i ajunge n x j ,

0, n caz contrar.

Folosind programul Mathematica 4, vom da un graf cu ajutorul matricei sale de adiacen. a:=matrix(n,n,[[0,0,1,0,0,0,0], > [1,0,0,0,0,0,0], > [0,1,0,0,0,0,0], > [1,1,0,0,1,1,0], > [0,1,1,0,0,1,1], > [0,0,1,1,0,0,0], > [0,1,0,0,0,1,0] > ]): > > for k from 1 to n do > for i from 1 to n do > for j from 1 to n do if ik and jk then b[i,j]:=max(a[i,j],min(a[i,k],a[k,j])):a[i,j]:=b[i,j]:fi: > od: > od:od: >

4

> print(`Matricea drumurilor este:`);

Matricea drumurilor este:

> print(a);

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

0 0 0 1 1 1 1

0 0 0 1 1 1 1

0 0 0 1 1 1 1

0 0 0 1 1 1 1

Exemplul 2. Determinarea componentelor tare conexe ce ajutorul algoritmului RoyWarshall > > > > with(linalg): > n:=7: > a:=matrix(n,n,[[1,1,1,0,0,0,0], > [1,1,1,0,0,0,0], > [1,1,1,0,0,0,0], > [1,1,1,1,1,1,1], > [1,1,1,1,1,1,1], > [1,1,1,1,1,1,1], > [1,1,1,1,1,1,1] > ]): > > w:={}:c:={}:nc:=0:t1:=table():s:={}: > for j from 1 to n do if member(j,s)=false then w:=w union{j}: > for i from 1 to n do > if > a[i,j]=1 and a[j,i]=1 and member(i,w)=false then w:=w union {i}:fi > od:nc:=nc+1: > t1[nc]:=w:c:=w:s:=s union c:w:={}:fi: > od:

5

> print(`Numarul componentelor tare conexe este:`); Numarul componentelor tare conexe este: > print(nc); > print(t1);

2table([1 = { 1, 2, 3 }, 2 = { 4, 5, 6, 7 }])

> > Algoritmul lui Malgrange Acest algoritm determin componentele tare conexe ale grafului orientat G , pornind de la matricea sa de adiacen A. Pasul 1. Se determin x . Aceast mulime va fi reprezentat printr-un vector de lungime n n care n csua corespunztoare vrfului x vom pune zero. Cutm arcele ce pleac din x prin citirea liniei corespunztoare vrfului x. n poziiile unde gsim 1, pe aceleai poziii, vom pune 1 n vectorul x . Cutm n vrfurile marcate cu 1 i apoi cutm pe liniile lor din matricea A elementele egelex

cu 1. Pe aceste poziii n x vom pune 2. La fel procedm cu vrfurile marcate cu 2. Pe liniile corespunztoare lor din A cutm poziiile marcate cu 1. n , acestex

poziii vor fi marcate cu 3, . a. m. d. Vrfurile care nu mai pot fi marcate prin acest procedeu vor primi semnul - n casia corespunztoare lor n x . Pasul 2. Se determin Cx. Aceast mulime va fi reprezentat printr-un vector de lungime n. Poziia corespunztoare vrfului x va fi marcat cu zero. Punem 1 pentru orice vrf de pe coloana vrfului x care are 1 i vare se afl n x . Pentru vrfurile xi care au fost marcate cu 1 n Cx punem 2 , n Cx, pe poziiile n care gsim elemente egale cu 1 pe coloanele corespunztoare lor din matricea A* i care se afl i n xi , . a. m.d. Gsim astfel Cx . Considerm x X C x i continum procedeul. Iat i algorimul, implementat n Maple, pe urmtorul exemplu:

6

> with(linalg): > n:=8: > a:=matrix(n,n,[[0,1,1,0,1,0,0,0], > [0,0,0,0,1,1,1,0], > [1,1,0,1,0,0,1,0], > [1,1,0,0,1,1,0,0], > [0,0,0,0,0,1,1,0], > [0,0,0,0,0,0,1,1], > [0,0,0,0,0,0,0,0], > [0,0,0,0,1,1,1,0]]): > for k from 1 to n do > for i from 1 to n do > for j from 1 to n do if a[i,j]=0 then a[i,j]:=a[i,k]*a[k,j]:fi: > od: > od: > od: > t:={}:nc:=0:t1:=table(): > for i from 1 to n do > c:={}:

7

>

if member(i,t)=false then nc:=nc+1: > s:={}: > for j from 1 to n do if a[i,j]=1 then s:=s union {j}:fi:od: > p:={}: > for j from 1 to n do if a[j,i]=1 then p:=p union {j}:fi:od: > c:=(s intersect p) union {i}: > t1[nc]:=c: > t:=t union c: > fi: > od: > print(`Numarul de componente tare conexe este:`);nc; > print(`Componentele tare conexe sunt:`); > tare_conexe:=copy(t1);

Numarul de componente tare conexe este: 4 Componentele tare conexe sunt: tare_conexe := table([1 = { 1, 3, 4 }, 2 = { 2 }, 3 = { 5, 6, 8 }, 4 = { 7 }])

8

Curs nr. 5

DRUMURI OPTIME INTR-UN GRAFFie G = ( X ,U ) un graf orientat. Fie L : U +, o funcie u L(U ) numit lungimea arcului u. Lungimea unui drum este egal cu suma lungimilor arcelor sale, iar distana minim dintre dou vrfuri este cea mai mic lungime a drumurilor dintre dou vrfuri. Vom defini matricele:l ((xi x j )) daca (xi x j ) U D = (d ij )i , j =1,n , d ij = 0, x x i j

minime M = (mij )i , j =1,n :

D se numete matricea distanelor directe ale grafului G, i matricea distanelor

cea mai mic lungime a drumurilor de la xi la x j , dac acestea exist mij = 0, altfel

Algoritmul Roy- Floyd gsete matricea distanelor minime M pornind de la matricea distanelor directe D, ct i drumul minim. Descrierea algoritmului: Pasul 1: k = 1 Pasul 2: pentru i = 1, u , j = 1, u , i j , i k , j k elementul aij se nlocuiete cu min (aij , aik + akj) Pasul 3: k k+1 i se repet pasul 2. La sfrit obinem matricea M. Justificare: Prin inducie dup k.

1

Fixm dou vrfuri v i w ntre care vrem s calculm drumul de lungime minim. Vom defini un K-drum ntre v i w, un drum care s treac prin cel mult Knoduri intermediare (deci w este al k-lea nod). Vom nota cu P(K) afirmaia: la pasul K, aij = dmin (u,v) obinut la pasul 2 al algoritmului este distana minim a celui mai scurt k-drum dintre u i w (dac exist !), altfel este infinit (dac nu exist un astfel de drum). Presupunem P(K) adevrat i s vedem ce se ntmpl cu dmin (v,w) la pasul k+1. Presupunem c este un k+1 drum de la v la w. Sunt dou posibiliti, funcie dac conine sau nu vrful uk+1 = de la pasul k+1. i) dac este un k-drum, atunci ntrece prin nodul k+1 i atunci din ipoteza de inducie dmin (v,w) rmne egal cu lungimea drumului dup iteraia k. Este clar c dmin (v,w) nu poate fi schimbat la pasul k+1, deoarece nu avem k+1 drumuri. ii) Dac este un k+1 drum, presupunem c trece doar o dat prin vrful uk+1 (pentru c un ciclu ar face s creasc distana). Atunci este suma a dou k-drumuri, 1 i 2, 1 de la v la uk+1 i 2 de la uk+1 la w. Din ipoteza de inducie avem c dmin (v, uk+1) i dmin (uk+1,w) sunt lungimile drumurilor 1 i 2 la pasul k. Se observ c aceste distane nu se vor modifica la pasul k+1, deci lungimea drumului la pasul k+1 este suma celor dou drumuri 1 i 2 i este cea mai scurt. Pentru k = u - 1, avem c dup ce am terminat iteraia n, dmin (v,w) este cea mai mic distan a unui (n-1) drum de la v la w. Dar deoarece orice drum este un (n-1) drum, n cazul nostru, demonstrm c aij = dmin (v,w) este distana minim dintre v i w. Cu acest algoritm, putem obine i drumurile minime dintre vrfurile grafului. Definim o nou matrice = (ij)ij = 1,u ale crei ij P(X) (deci

2

ij sunt mulimi de noduri). Vrem s gsim drumul minim dintre v = xi i w = x j. ij va reprezenta mulimea vrfurilor vecine vrfurilor w care se gsesc pe drumuri de la v la w. Iniial, ij = {xi} dac aij < i ij = dac aij = . Pasul 1. Se face k = 1. Pasul 2. dac aij < aik + akj , atunci ij = ij; dac aij = aik + akj , atunci ij = ij kj; dac aij > aik + akj , atunci ij = kj,

pentru i j, i k, j k. Pasul 3. Se repet pasul 2 pentru k = 2,u. La sfritul aplicrii algoritmului ij va reprezenta mulimea vrfurilor vecine cu w ce se gsesc pe drumurile minime de la v la w. Aceste vrfuri vecine sunt date n ordine invers orientrii drumului. Folosind Maple 6 obtinem urmatorul program pentru algoritmul RoyWarshall Exemplul 1. > with(linalg): > > n:=8: > a:=matrix(n,n,[[0,1,3,5,infinity,infinity,infinity,infini ty], > [infinity,0,2,infinity,infinity,infinity,13,infinity], > [infinity,infinity,0,infinity,5,11,14,infinity], > [infinity,infinity,2,0,6,8,infinity,15], > [infinity,infinity,infinity,infinity,0,3,infinity,9], > [infinity,infinity,infinity,infinity,infinity,0,2,6],[inf inity,infinity,infinity,infinity,infinity,infinity,0,4],[ 3

infinity,infinity,infinity,infinity,infinity,infinity,inf inity,0]]): > > print(a): 0 1 3 5 0 2 13 0 5 11 14 2 0 6 8 15 0 3 9 0 2 6 0 4 0 > d:=array(1..n,1..n):for i from 1 to n do for j from 1 to n do d[i,j]:={}:od:od:for i from 1 to n do for j from 1 to n do if a[i,j] c:=array(1..n,1..n):for i from 1 to n do for j from 1 to n do c[i,j]:={}: od:od: __

> for k from 1 to n do > for i from 1 to n do > for j from 1 to n do a[k,j]:=a[k,j]: d[k,j]:=d[k,j] : if ji and jk then > > if a[i,j]a[i,k]+a[k,j] then c[i,j]:=d[k,j]end if:end if:end if:

4

> if i=k and j=k then a[i,j]=a[i,j] else b[i,j]:=min(a[i,j],a[i,k]+a[k,j]):a[i,j]:=b[i,j]:fi:fi:od : a[i,k]:=a[i,k]:d[i,k]:=d[i,k]: > > od: > for i from 1 to n do > for j from 1 to n do if ji then d[i,j]:=c[i,j] else d[i,i]={xi} end if:od:od: > for i from 1 to n do > for j from 1 to n do if a[i,j]=infinity then d[i,j]:={}:fi: od:od: > od: > i1:=1:j1:=8: > print(`Matricea distantelor minime este:`);

Matricea distantelor minime este:>

> print(a);

0

1 0

3 2 0 2

5 0

8 7 5 6 0

11 10 8 8 3 0

13 12 10 10 5 2 0

17 16 14 14 9 6 4 0

> print(`Distanta minima intre x1 si x8 este:`); Distanta minima intre x1 si x8 este: > print(a[i1,j1]):

17

> print(`Matricea care ajuta la determinarea drumurilor minime este:`): Matricea care ajuta la determinarea drumurilor minime este: > print(d);

5

{ 1 } { } { } { } { } { } { } { }

{1} {2} { } { } { } { } { } { }

{ 1, 2 } {2} {3} {4} { } { } { } { }

{1} { } { } {4} { } { } { } { }

{3} {3} {3} {4} {5} { } { } { }

{5} {5} {5} {4} {5} {6} { } { }

{6} {6} {6} {6} {6} {6} {7} { }

{ 5 , 6, 7 } { 5 , 6, 7 } { 5 , 6, 7 } { 6, 7 } { 5 , 6, 7 } { 6, 7 } {7} {8}

> p:=0:m:=array(1..n): for j from 1 to n do m[j]:=0 od: > for i from 1 to n do for j from 1 to n do if member(j, d[1,i])=true then p:=p+1:fi:od:m[i]:=p:p:=0:od: print(m): > [ 1, 1, 2, 1, 1, 1, 1, 3 ] > nrd:=1:v:=1:w:=1: > for i from 1 to n do nrd:=nrd*m[i]:od:print(`Numarul maxim de drumuri este:`):print(nrd): > Numarul maxim de drumuri este:

6> vf:=table():q:=0:nod:={}: > for i from 1 to n do for j from 1 to n do if member(j,d[i1,i])=true then nod:=nod union {j}:fi:od:q:=q+1:vf[q]:=nod:nod:={}:od:print(vf): table([1 = { 1 }, 2 = { 1 }, 3 = { 1, 2 }, 4 = { 1 }, 5 = { 3 }, 6 = { 5 }, 7 = { 6 }, 8 = { 5, 6, 7 } ]) > mnod:=array(1..n,1..n):sw:=array(1..n,1..n):for i from 1 to n do for j from 1 to n do mnod[i,j]:=0:sw[i,j]:=0:od:od: > k:=j1:t2:=table():M:=0:nr:={j1}:r:=1:nm:=table(): > for j from 1 to n do for i from 1 to n do if member(i,vf[j1-j+1])=true then mnod[j1j+1,i]:=1:fi:od:od:for j from 1 to n do for i from 1 to n do sw[i,j]:=mnod[j,i]:od:od:print(sw):

6

1 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 1 1 1 0

> vec:={}:r:=i1:t4:=table():P:=1:h:=0:t5:=table():t8:=table ():Q:=0: > > ncol:=array(1..n):for i from 1 to n do ncol[i]:=0:od: for i from 1 to n do for j from 1 to n do if mnod[j,i]=1 then h:=h+1:ncol[i]:=h :fi :od:h:=0:od:for i from 1 to n do if ncol[i]>1 then Q:=Q+1 :t8[Q]:=i:fi:od: print(ncol):print(t8):print(Q): [ 4, 1, 1, 0, 2, 2, 1, 0 ]

table([1 = 1, 2 = 5, 3 = 6]) 3> for j from 1 to n do for i from 1 to n do if mnod[i,j]=1 then r:=i:vec:=vec union {r}:next: fi:od:t4[P]:= vec:P:=P+1:vec:={}:od:print(vec):print(t4):

{ }table([1 = { 1, 2, 3, 4 }, 2 = { 3 }, 3 = { 5 }, 4 = { }, 5 = { 6, 8 }, 6 = { 7, 8 }, 7 = { 8 }, 8={ } ])

> ind:=table():nq:=0:for i from 1 to n do if sw[i1,i]=1 then nq:=nq+1:ind[nq]:=i:fi:od:print(ind):print(nq): table([1 = 1, 2 = 2, 3 = 3, 4 = 4])

4> P:=1:r:=1:t5:=table():A:={}: > for z from 1 to nq do for y from 1 to Q do l:=Q-y: if l>0 then for h from 1 to ncol[t8[l]] do for j from 1 to ncol[t8[l+1]] do for i from 1 to n do if sw[r,i]=1 then r:=i: vec:=vec union {r}:fi:od:if r > >

8

Curs nr. 6

DRUMURI OPTIME INTR-UN GRAF (continuare)

Algoritmul lui Dijkstra (pentru determinarea distanelor minime ntre dou vrfuri fixate). Spre deosebire de algoritmul lui Floyd, care determin distana i drumul minim dintre orice dou vrfuri ale unui graf dat, acest algoritm determin distana dintre dou vrfuri date u i v. n esen, algoritmul Dijkstra i propune s descopere minimul distanei dintre un vrf dat , considerat ca surs, ctre alte vrfuri n ordinea acestor distane minime, cu alte cuvinte, mai nti, ctre cel mai apropiat nod. Presupunem c am selectat cteva vrfuri n graful ntre care cunoatem distanele minime. Aceast mulime include mereu vrful surs n cazul nostru . Pentru un vrf neselectat v, vom considera lungimea celui mai scurt drum special, care este un drum ce pornete din vrful surs, trece doar prin nodurile selectate, iar la ultimul pas, sare din regiunea selectat (din mulimea vrfurilor selectate) ctre vrful v. Dac este un vrf selectat, voi nota cu d(u) lungimea celui mai scurt drum de la sursa ctre . Dac u nu este selectat, atunci d(u) este lungimea celui mai scurt drum special de la la u. La nceput singurul vrf selectat va fi u, deci d(u) = 0. Dac exist un arc de la u la u, atunci d(u) este chiar lungimea arcului (u,u). Observaie: Dac u este singurul vrf selectat, atunci singurele drumuri speciale sunt arcele ce pleac din u, deci d(u) = lungimea arcului (u,u), dac avem un astfel de arc. 1

d(u) =

l (u , u ' ), daca exista arc int re u si u ' , in caz contrar

Presupunem c S X este mulimea vrfurilor selectate. Fie v un vrf neselectat, astfel nct distana de la v la orice alt vrf neselectat s fie cea mai mic. Vrful v va fi selectat i atunci avem: 1) d(v) este cea mai mic distan de la u la v. 2) Vom adapta valoarea distanei (u) pentru toate vrfurile u care au rmas neselectate, innd cont c v este acum selectat. Aceast adaptare o vom face astfel: Vom compara d(u) cu d(v) + l(v,u). Dac d(v) + l(v,u) < d(u) se nlocuiete d(u) cu d(v) + l(v,u). Dac nu exist arc ntre v i u nu vom modifica d(u).

Justificarea algoritmului Dijkstra. Atenie ! Lungimile arcelor trebuie s fie pozitive, altfel acest algoritm nu merge. Fie S mulimea nodurilor selectate cu |S|= k. Vom face inducie dup k; vom face notaiile: i) ii) pentru fiecare nod selectat u, d(u) este cea mai mic distan de la u la u, iar drumul cel mai scurt este format doar din noduri selectate. pentru fiecare nod neselectat u, d(u) este cea mai mic distan a unui drum special de la u la u (poate fi dac un astfel de drum nu exist). Pentru k = 1, u este singurul nod selectat iar d(u) = 0 i satisface condiia i). Pentru orice alt nod u vom defini d(u) ca fiind lungimea arcului (u,u) dac exist i infinit n caz contrar, fiind astfel ndeplinit condiia ii). Presupunem c sunt ndeplinite condiiile i) i ii) dup ce am selectat k noduri i fie v al (k+1) lea nod selectat. Afirmm c i) rmne adevrat, deoarece d(v) este cea mai mic distan a unui drum ntre u i v. Dac nu s-ar ntmpla acest lucru, din condiia ii) a ipotezei de inducie cnd avem k noduri selectate, d(v) este cea mai mic distan a unui drum special de la u la v, i deci trebuie s fie un drum nespecial scurt ctre v. De aici avem c drumul trebuie neaprat s ias din mulimea de noduri selectat, ca n final s ajung n k. 2

Oricum, v este al (k+1) lea nod selectat, ceea ce nseamn c n aceast situaie d(u) poate s nu fie mai mic dect d(v), sau n plus vom selecta pe u ca fiind al (k+1) lea nod. Din condiia ii) a ipotezei de inducie, d(u) este lungimea minim al unui anumit drum ctre u. Atunci condiia i) este adevrat pentru (k+1) noduri, ceea ce nseamn c i) este adevrat i cnd includem pe v n mulimea de noduri selectate. Mai trebuie artat c relaia ii) este adevrat cnd includem pe v n mulimea de noduri selectate S. Considerm un nod u rmas neselectat dup ce v a fost indus n S. Pe un drum special ctre u, trebuie s existe un penultim nod care s poat fi v sau alt nod w. Mai nti, presupunem c penultimul nod este v. Atunci lungimea unui drum de la u la v este d(v) plus lungimea arcului (v,u). Dac penultimul nod este w, din ipoteza de inducie i), cel mai scurt drum de la u la w este format doar din acele noduri care au fost selectate naintea lui v i deci v nu apare n drum. Atunci lungimea celui mai scurt drum special ctre u nu se modific atunci cnd includem pe v n mulimea nodurilor selectate. Reamintim c, atunci cnd am selectat vrful v, se modific i d(u) ca fiind cea mai mic dintre vechea distan d(u) i d(v) + l(v,u), q.e.d. Dac drumul (x1,x2,x3,...,xn) are valoarea minim, atunci orice parte a sa (xb,...,xl) are, n mulimea drumurilor ce unesc pe xb cu xl valoare minim. Dem. Presupunem contrariul. Dac 1 = (xb,...,xl) nu este drum de valoare minim ntre xb i xl , vom considera un drum 2 cu valoare minim ntre xb i xl pe care l vom pune n locul lui 1 obinnd astfel ntre xm i xn un drum de valoare mai mic. Algoritmul Bellman Kalaba. (de determinare a drumului minim pornind de la matricea D). Fie G = (X,U) un graf cruia i atam matricea D = (dij) a distanelor directe. Fie vi valoarea minim a drumurilor in (i=1,u) existente de la vrful xi la vrful xu. vi = min i vn = 0. Conform principiului optimalitii, avem c: (*) vi = minji(vj + dij) j = 0,u , i = 0,u-1 i vn = 0

3

Problema gsirii valorilor minime ale drumurilor de la xi la xn (i x, i ...n 1) , .........la rezolvarea sistemului (*). Vom da o demonstraie inductiv.K = 1 Vi1 = din i = Qu 1 Vn1 = 0

K = 2 Vi 2 = min (V j1 + d ij ), i = u 1, j = , u , Vu2 = 0.j =i

La paxel K Vi k = min (V jk 1 + d ij ), i = u 1, j = u , Vnk = ij i

Se

observk 1 j

c

Vi k Vi k 1 , i = 1, u .

ntr-adevr,

dac

avem

d ij + V

> Vi

k 1

, j , j i, atunci val. minim ar fi Vi k = d ii + Vi k 1 = Vi k 1 ,

Numerele Vi k formeaz un ir monoton descresctor, i u , K 1, u 1 , ajungem la un minim dup cel mult n-1 pai. Deci algoritmul ia sfrit atunci cnd gsim un K a.. Vi k = Vi k +1 , i = 1, u . Acest lucru nu asigur c: 1) Drumurile pariale, n drumul de lungime minim sunt minime. 2) Valoarea drumului minim ntre vrfurile x1 i xn este Vi k = Vi k +1 Putem determina i nodurile care fac parte din drumul minim astfel. La ultima iteraie presupunem c aceasta este a-K-a .........., avem: Vi k = d ij + V jk 1 = d ij + V jk i pe celelalte drumuri avem: Vi k > d ij + V jk . Deci arcul (xi ,xj) aparine drumului de valoare minim dac i numai dac V jk = Vi k d ij . Algoritmul lui Ford (de det. a distanei minime) ntre 2 vrfuri xp i xf - Fie xi X un vrf arbitrar. Vom nota cu li lungimea unui drum arbitrar de la vrful xp la xi. Pentru nceput vom lua pentru xp , lp = 0 i li = 0 pentru i p - Vom considera toate arcele ( xi x j ) V i vom calcula diferena l j l i pe care o vom compara cu l ( xi , x j ) ( An2 operaii i comparaii) Dac l j l i > l ( xi , x j ) , atunci se nlocuiete lj cu l j = l i + l ( xi , x j ) < l j . Deci vom face urmtoarele modificri la pasul K l j , dac l j li l ( xi , x j ) lj = li + l ( xi , x j ), dac l j l i > l ( xi , x j ) Vom continua acest procedeu pn cnd pentru orice arc ( xi , x j ) U aveml j li l ( xi , x j )

Dac am ajuns n aceast situaie putem avea cazurile: 1) l f = deci nu avem drum de la xp la xf , deoarece un astfel de drum plecnd din xp cu valoarea lp finit, trebuie s aib un ultim vrf xi cu marca lj finit i atunci marca xf urmtor s-ar putea reduce, deci nu ar mai fi . 2) lf este finit i reprezint valoarea drumului minim de la xp la xf

4

Vom arta c exist un drum de la xp la xf de lungime lf i c nu exist un altfel de lungime mai mic.

ExistenaFie x f1 ultimul vrf care a servit la reducerea lui lf , x f 2 ultimul vrf care a servit la reducerea luil f1 s.a.m.d.

Obinem

l f l f1 = l ( x f1 , x f ), l f1 l f 2 = l ( x f1 , x f 2 )

Continund procedeul obinem un ir descresctor de numere pozitive: l f > l f1 > l f 2 > ... > 0. Dup un numr finit de pai vom gsi un vrf xr a.. l f r 1 l f r = l ( x f r , x f r 1 ) il sk l p = l ( x p , x sk .

Dac adunm aceste egaliti i inem cont c l0 = 0, vom obine: l s = l ( x p , x s ) + l ( x sk , x s ) + ... + l ( x s , x s ) . Deci am gsit drumul ( x p , x s , x s ,..., x s ) de lungime ls Unicitatea: Presupunem c mai avem un drum ntre x p i x s , = ( x p , xi1 ,..., xir , x s ). Deoarece reducerea mrcilor s-a terminat avem: li1 l p l ( x p1 , xi1 ), li li1 l ( xi1 , xi2 )...li2 ...lir lir 1 l ( xir 1 , xir ), l s lir l ( xir , x s ) Dc facem suma acestor inegaliti termen cu termen avem c l ( ) l a Observaie: Algoritmul ne d i un procedeu de gsire a drumului de lungime minim. Algoritmul: Pa1 i = 1 l p = 0, l i = 0, i p.l j , l j li l ( xi , x j ) Pa2 i = 2 l j = li + l ( xi , x j ), l j l i > l ( xi , x j ) K = {3,...n} Dac l j l i l ( xi , x j ), i, j

Dac l f = , atunci nu avem drum STOP Dac l f < , atunci lf este val. de. minim. K K + 1 i se trece la pasul 2. Algoritmii Ford i Bellman Kalaba pot fi modificai astfel nct s determinm drumurile de lungime maxim dintre dou vrfuri, cu condiia ca ...aful dat s nu conin circuite. Algoritmii Ford. (pt. det.dr. maxim) 1) Lum l p = 0 i l i = pentru i P 2) Pentru orice arc ( xi , x j ) U calculm toate diferenele lj - li Dac l j l i l ( xi , x j ) , atunci lj rmne nesdruibat i continum procedeul. Dac l 'j li < l ( xi , x j ), nlocuim pe lj cu l j = l i + l ( xi , x j ) > l il j , dac l j l i l ( xi , x j ) deci l 'j = li + l ( xi , x j ), dac l j l i < l ( xi , x j ) Vom continua algoritmul pn cnd, pentru orice arc (xi, xj), avem lj - li l(xi, xj)

5

Sunt posibile situaiile: i) l s = nu exist drum de la vrful xp la xs, deoarece orice vrf care nu se afl pe un drum ce pleac din xp rmne cu marca infinit. Lema: Orice vrf care poate fi atins printr-un drum de la vrful xs va avea o marc finit. x X 1 avem Demonstraie: Fie X 1 = {x | x X | x s }, atunci pentru l x l s = < l ( x s , x) l x = l ( x s , x) va fi finit. Fie X 2 = {x X | x X 1} Oricrui vrf x X 2 . i va corespunde un vrf I X 1 , cu l x l y = < l ( x, y ), deci lx se va modifica i va deveni l x = l ( y , x ) + l y continund procedeul, vom defini l xi pentru toate vrfurile xi, ce aparin drumului care pleac din xp, l xi < finite Rezult c orice vrf z care nu aparine drumului ce pleac din x0 are l2 infinit. Acest lucru se ntmpl deoarece pentru a obine o valoare finit pentru marc dintr-o marc infinit, acest vrf ar trebui s fie marcat de la un alt vrf cu marc finit iar acestea sunt numai x0 i toate vrfurile ce se gsesc pe drumul care pleac din xp. ii) ls este finit, atunci reprezint valoarea drumului maxim de la xp la xn. Demonstraie: Existena unui astfel de drum de la xp la xs. Fie xst ultimul vrf care a permis creterea mrcii vrfului xs, decil s l st = l ( x st , x s ), l st > 0, l st < l s ), x st 1 ultimul vrf care a permis creterea mrcii

vrfului

x st , deci

l st l st 1 = l ( x st 1 , x st ) 0 < l st 1 < l st sau continund procedeul

obinnd un ir descresctor de numere pozitive; l s > l st > l st 1 > ... > o, deci exist un vrf x s1 astfel nct l s2 l s1 = l ( x1 , x s2 ) i l s1 l p = l ( x p , x s1 ). inem cont de faptul c l0 = 0 i adunm aceste inegaliti. Obinem c l s = l ( xo , x s1 ) + l ( x s1 , x s2 ) + ... + l ( x sk , x s ), deci drumul ( x p , x s1 ,..., x st ) are valoarea maxim ls. Unicitatea Vom arta c orice drum de la vrful xp la xs are valoarea cel mult ls. Fie = ( x p , x j ,..., x jk , xs ) nu da astfel de drum. Avem inegalitile:l ji l p l ( x p1 , x j1 ) l j2 l j1 l ( x j1 , x j2 )

---------------------l jk l jk 1 l ( x jk 1 , x jk )l s l jk l ( x j k , x s )

Facem suma termenilor i obinem l ( ) l s Alg. Bellman-Kalaba pentru determinarea drumului de valoare maxim. Fie 6 = ( X ,U ) ...... i matricea l ( xi , x j ), ( xi , x j ) U 0 , i= j C = (ci j )i, j = 1, u ci j = , ( x , x ) U i j

6

Vi o = ci i = o, u 1 n Pasul 1: 0 Vu = 0 Vi1 = max(V j0 + cij ), i = 0, u 1, j = 0, u Pasul 2: (1) Vu1 = 0 2 Vi max (V j1 + cij ) i = 0, u 1, j = 0, u j i (2) 2 Vu = 0 Vi k = max{V jK 1 + Cij ) i = 0, u 1, j = 0, u j +i (K) k Vu = 0Vi k +1 = max{V jk + Cij ), i = 0, u 1, j = 0, u j i (K+1) VuK +1 = 0 Dac Vi k = Vi K +1 , i = 0, u ne oprim gsind drumul de valoare maxim V0k = V0k +1 . Pentru determinarea efectiv a acestuia vom proceda ca la (B-K) min. Algoritmul lui Dautzing (1) (de determinare a drumurilor de valoare minim pornind de la matricea de .... Fie G = ( X ,U ) graf cu | x |= n, X = {x1 ,..., xn } . Acest algoritm este mai general verificnd dac avem i circuite pe care funcia distana l : U ia i valori negative. Obs. Dac un graf admite un circuit de lungime total negativ, atunci ntre orice 2 vrfuri ale circuitului distana este negativ i poate fi facut orict de mic dac parcurgem acest circuit de un numr suficient de mare. Deci nu putem gsi cea mai mic distan ntre vrfurile circuitului. t Fie X t = {x1 , x2 ,..., xt } t u . Vom nota cu d ij distana minim de la xi la xj n

subgraful lui G,Gt, generat de mulimea X, pentru orice i, j {1,2,.., t ) . 2 2 Pasul 1: Definim d12 = a12 , d 21 = a21 2 2 Dac a 2 d12 + d 21 < 0 ne oprim, deoarece circuitul (x1, x2, x1) este negativt t Dac s-au determinat distanele minime d ij1 vom calcula d ij astfel:t t d it = min (d ij1 + a jt ), i = 1, t 1 j =1,t 1 t t 1 d ti = min1(d tj + d ji ), i = 1, t 1 j =1,t t t Pentru orice i = 1, t 1 verificm dac d it + d ti > 0 .t t Dac i a d it + d ti < 0 ne oprim pentru c am gsit un circuit negativ ce conine vf xi i xt. Dac nu exist un astfel de i calculm t t t t d ij = min(d ij , d it + d tj ) pentru i, j = 1, t 1, i i j.

u Algoritmul se sfrete cnd t= n iar d ij vor fi distanele minime cutate.

7

t Este clar c d ii = 0, i = 1, t i t = 1, u Observaie: Dac nu avem n graf arce (xi,xj) a.. l(xi,xj) c i i i i i i Elementele i 0 determin pentru vrful xi, cu ct capacitatea arcelor care

= (1 ,..., n ) i nc o

pleac din xi este mai mare dect cea a arcelor care intr n xi.. Elementele i 0 determin pentru vrful xi, cu ct capacitatea arcelor care intr n xi este mai mare dect cea a arcelor care pleac din xi..

li = cij = c ji =1 n i =1 j =1 n j =1

n

n

n

n

l j j = min(li , ci ) = c j j ,n n n j =1 j =1 j =1 j =1 j =1

deciFieo

j =1

n

j

= j .j =1o

n

i 0 primul element nenul, deci coloana . Pentru arcele ce din xi li se va

micora surplusul de capacitate prin diminuarea capacitii arcelor care intr n vrfurile adiacente cu xio , a cror capacitate pentru arcele care intr este mai mare dect a arcelor care ies din aceste vrfuri. Se face acest lucru pn cnd

i = 0 dup care se trece la urmtoareao

component nenul a vectorului pn cnd =(0,0,...,0). Dac un element ik 0 nu poate fi ................ se va ncerca acumularea valorii rmasek k

'i parcurgnd elementele nenule ai j 0 din linia ik n ordinea cresctoare a i'' va fi anulat astfel:k

lungimii drumurilor care leag vrful xik de vrful n care predomin capacitatea arcelor care intr n ele. ' Dac ik 0 nu a putut fi compensat, valoarea rmask1

se parcurg elementele Ci ' , j 0 din linia ck n ordinea cresctoare a indicelui j i se procedeaz ca mai sus. 3

Acest blocaj arat c fluxul care trece prin reea este prea mare. Compensarea n punctele de blocaj se realizeaz dezechilibrnd reeaua astfel: a) se compenseaz elementul ik 0 ct este posibil utiliznd surplusul de capacitate al arcelor care intr n vrfurile adiacente cu xik b) se compenseaz cantitatea pariale a lui notm C ik1' k1

'i rmas n .............. compensriik

i cu primul element diferit de 0 al liniei ik pe care-lk

,j

Dac 'ik Ci ' , j , atunci Ci ' , j := Ci ' , j 'ik iar ik := 0 . Dac 'ik > Ci ' j Ci ' j := 0 iar 'ik := 'ik Cik jo .k1

o

o

k1

o

k1

o

o

k1

Noua valoare a lui

'i se compar cu urmtoarele elemente nenule din linia ikkk1

o

1

deci matricea C. Pentru un astfel de element nenul Ci ' j se repet algoritmul ca n cazul

Ci

' k1

j

o

. Dac ik nu poate fi nici acum anulat, se reia algoritmul pn la anularea lui ik .n1

1

Anularea se va produce sigur ntr-un numr finit de pai deoarece ik Cik .j =1

c)

Se observ c mereu avem (u ) c (u ) . ntr-adevr, aceast metod compenseaz surplusul de capacitate a arcelor care pleac din vrfurile unde acest surplus exist prin diminuarea surplusului de capacitate a arcelor care intr n vrfurile adiacente cu vrfurile unde avem surplus, acest surplus provocnd dezechilibru reelei. Atunci cnd = 0 , se oprete algoritmul. Dac avem soluie nenul, adic se echilibreaz reeaua, elementele matricei C obinute n urma algoritmului reprezint valoarea fluxului pe fiecare arc. Dac nu avem soluie nenul, atunci C=0.

Se trece pa pasul urmtor calculndu-se din nou elementele vectorilor Ln+1 , Cn+1 , , i se repet algoritmul.

4

Curs nr. 8Algoritmul Ford-Fulkerson Flux maxim n reele de transportFie G = ( X ,U , c ) o reea de transport. Problema determinrii fluxului maxim cu componente raionale ntro reea cu capacitile numerelor raionale, se reduce la cazul cnd componentele fluxului i capacitile sunt numere naturale, deoarece putem amplifica componentele fluxului i capacitile arcelor cu o aceeai cantitate pozitiv. Deci, n cele ce urmeaz c (u ) 0, ( ) 0 . Fie un drum de la xo la xn. Dac nu exist arc saturat n acest drum, putem mri fluxul n cu respectarea condiiilor de mrginire i conservare a fluxului. Vom considera (u ) = c(u ) (u ) > 0 pentru orice u arc al drumului i fie m = min (C (u ) (u )) .u

Dac avem un lan de la xo la xn, vom nota cu + arcele din avnd acelai sens cu sensul de parcurgere de la xo la xn i cu - arcele orientate invers. Fie m = min (C (u ) (u )), m = min ( u ) si m = min ( m , m ) . + +u u

n + m > n , pstrndu-se condiiile (m) i (c).

Pe fiecare arc al drumului vom mri fluxul cu m. Obinem un flux mrit

Pentru m>0 mrim fluxul cu m pe fiecare arc u

+

i-l micorm cu m; pe

fiecare arc u obinem tot un flux pozitiv ce verific condiia (m) i (c) cu n + m > n . Definiie. Un drum pentru care m=0 se numete saturat, iar un lan pentru care m=0 se numete saturat. Algoritmul Ford-Fulkerson Fie G = ( X ,U , c ) reea det. pe care am definit un flux . Dac nu avem nici un lan nesaturat care pleac din xo i ajunge la xn, fluxul n este maxim n xn i este egal cu capacitatea minim a unei tieturi. Dem. Pasul 1. Se obine un flux complet pornind de la fluxul iniial compatibil cu capacitatea arcelor reelei. Se ia un drum nesaturat de la xo la xn, i se mrete fluxul pn la saturarea cu cel puin un arc. Se repet ............ pn cnd nu mai avem drumuri nesaturate, deci am obinut un flux complet.

1

Se consider toate lanurile elementare de la xo la xn. Parcurgnd un astfel de lan, cutm un arc u oarecare ................ din proprietile: u + i (u ) = 0 . Un astfel de lan este saturat i-l vom elimina. Vom parcurge doar lanurile nesaturate. Un astfel de lan nesaturat l vom satura mrind cu m + pentru u i micornd cu m pentru u pn cnd obinem m =0 . Un lan nesaturat de la xo la xn l determinm prin urmtorul procedeu de marcaj. Notm xo cu [+]. Dac vrful xi a fost marcat, vom nota cu [+xi] un vrf xj, dac (xixj)U i dac (xixj) este nesaturat. [-xi] este vrful xj nemarcat cu proprietatea c arcul (xixj) este traversat de un flux strict pozitiv. Dac vrful xn a fost marcat, atunci avem un lan de la xo la xn nesaturat pe care-l putem satura dup cum am descris mai sus. Dac vrful xn nu a fost marcat, atunci rezult c nuj avem lan nesaturat de la xo la xn. Fie A mulimea vrfurilor nemarcate. Este clar c xnA i x n A , deci A definete o tietur -(A). n aceast situaie avem ln =u ( A )

(u ) = c(u ) = c( ( A)) u ( A )

egalitatea pentru n flux maxim, deci obligatoriu tietura va fi de capacitate minim. Deci, dac nu avem lanuri nesaturate de la xo la xn n reea obinem un flux maxim. Algoritm. 1. Se obine un flux compatibil cu capacitile arcelor reelei, care poate fi iniial nul. 2. Se obine un flux complet: vom considera arcele nesaturate. Dac fluxul nu e complet, vom considera un drum format din arce nesaturate, se mrete fluxul pe arcele acestui drum pn la saturarea a cel puin un arc. Se repet pn cnd toate drumurile de la xo la xn sunt saturate. 3. Se obine un flux maxim prin procedeul de mai sus. 4. Algoritmul are un numr finit de pai deoarece capacitile i compoziia fluxului sunt numere pozitive, Folosind Maple 6 obtinem urmatorul program: > with(linalg): > > n:=10: > a:=matrix(n,n,[[[0,0],[0,12],[0,3],[0,20],[0,0],[0,0],[0,0] ,[0,0],[0,0],[0,0]],

n aceast situaie obinem valoarea maxim a fluxului. Deoarece u c ( A) pentru orice tietur i flux dat, n cazul nostru avem

(

)

2

> [[0,0],[0,0],[0,0],[0,0],[0,0],[0,6],[0,5],[0,0],[0,0],[0,0 ]], > [[0,0],[0,0],[0,0],[0,0],[0,4],[0,4],[0,0],[0,0],[0,0],[0,0 ]], > [[0,0],[0,0],[0,0],[0,0],[0,5],[0,0],[0,0],[0,0],[0,10],[0, 0]], > [[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,5],[0,3],[0,0 ]], > [[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,3],[0,3],[0,0],[0,0 ]],[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[ 0,13]],[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0, 0],[0,10]],[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0] ,[0,0],[0,12]],[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[ 0,0],[0,0],[0,0]]]): > > print(a): [ 0, 0 ] , [ 0, 12 ] , [ 0, 3 ] , [ 0, 20 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 6 ] , [ 0, 5 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 4 ] , [ 0, 4 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 5 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 10 ] , [ 0, 0 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 5 ] , [ 0, 3 ] , [ 0, 0 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 3 ] , [ 0, 3 ] , [ 0, 0 ] , [ 0, 0 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 13 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 10 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 12 ] [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] , [ 0, 0 ] > > for r from 1 to n do L:=array(1..n):for i from 1 to n do L[i]:=0:od:C:=array(1..n):for i from 1 to n do C[i]:=0:od: > for i from 1 to n do L[i]:=0:od:L[1]:=1: > i:=1:for j from 1 to n do if a[i,j][2]>0 then L[j]:=i:fi:od:print(L): > dif:={}:for i from 1 to n do if L[i]0 then dif:=dif union {i}:fi:od:print(q):print(dif): > for k from 1 to n do for i from 2 to n do if member(i,dif)=true then for j from 1 to n do if a[i,j][2]>0 then if L[j]=0 then L[j]:=i:fi:fi:od:for j from 1 to n do if a[j,i][1]>0 then if L[j]=0 then L[j]:=i:fi:fi:od:fi:od:for i from 1 to n do if L[i]0 then if

3

member(n,dif)=false then dif:=dif union {i}:fi:fi:od:od:print(L): > if L[n]0 then lnt:=table():var:=[n]:q:=1:t:=0:for j from 1 to n do for i from 1 to n do lnt[q]:=var[1]:od:t:=var[1]:if abs(var[1])>1 then var:=[L[abs(t)]]:q:=q+1:fi:od:print(lnt):m:=q:print(m): > lant:=array(1..m):for i from 1 to m do lant[i]:=lnt[mi+1]:od:print(lant): > v1:={}:v2:={}:q:=0:for i from 1 to m do if lant[i]>0 then if i+1 m1:=infinity:m2:=infinity:for i from 1 to n2 do m2:=min(m2,op(i,v2)):od:print(m2):for i from 1 to n1 do m1:=min(m1,op(i,v1)):od:print(m1): > for i from 1 to m do if lant[i]0 then if i+1 w1:={}:w2:={}:q1:=0:q2:=0:for i from 1 to n do if L[i]=0 then w1:=w1 union {i}:q1:=q1+1: else w2:=w2 union {i}:q2:=q2+1:fi:od:print(w1):print(w2):print(q1):print(q2): { 7, 8, 10 }

{ 1, 2, 3, 4, 5, 6, 9 } 3 7> flux:=0:for i from 1 to q2 do for j from 1 to n do if member(j,w1)=true and a[w2[i],j][1]>0 then flux:=flux+a[w2[i],j][1]:fi:od:od:print(`fluxul maxim este:`):print(flux): fluxul maxim este:

28

10

Curs nr. 9 ARBORI Numrul ciclomatic al unui grafFie G = (X,U) un graf simplu i mulimea nr. reale. Vom nota cu S 0 (G ) = { f : X | f funcie} i S1 (G ) = { f : U | f funcie }. S0(G) i S1(G) au structur de spaii vectoriale. Presupunem c X = {x1 ,..., x n }, U = {a1 , a 2 ,..., a n } . Atunci dmi S 0 (G ) = n i dmi S1 (G ) = m Funciile din S0(G) i S1(G) le vom reprezenta sub form vectorial. De exemplu dac f S 0 (G ) atunci f = (f1,...,fn) unde fi = f(xi), iar pentru g S1 (G ).,.g = ( g1 , g 2 ,..., g n ) cu g i = g (ai ) . 1, i = j , O baz n S0(G) este mulimea de funcii ( 1 , 2 ,..., n ) unde i ( x j ) = iar n 0, i j 1, i = j , S0(G) avem (1 , 2 ,..., m ) unde i (a j ) = 0, i j Aceste baze sunt baze canonice n C0(G) respectiv C1(G). Definiie. Fie G un graf. Spunem c am dat o orientare grafului G dac pentru orice muchie a U, a = ( xi , x j ) am dat un sens de parcurs (de la xi la xj sau de la xj la xi). Vom considera ca sens pozitiv sensul de rotaie dat de arcele de ceasornic. Rezultatele care urmeaz sunt independente de orientarea dat grafului. Definiie. Fie G = (X,U) un graf fie (matrice de inciden) B M uxm () B = (bij ) i , j =1, nj =1, m

1, dac vi d muchiei e j un sens de parcurs pozitiv bij 1, dac vi d muchieie j un sens de parcurs negativ 0, altfel

Matricea B este matricea unei aplicaii liniare B : S1 (G ) S 0 (G ) numit funcie de inciden. Fie g S1 (G) atunci B ( g ) = bij g (a j )j =1 m

Se observ c fiecare coloan din B conine doar 2 valori nenule , +1 i 1, care arat c muchia corespunztoare coloanei are un vrf care d orientare pozitiv i unul care d o orientare negativ. Vom nota cu p numrul componentelor conexe ale grafului G. Propozitia 1. Fie B : S1 (G ) S 0 (G ) , atunci dmiK Im B = u p dmiK KerB = m u + p Demonstraie. Este suficient s artm c dim K Im B = n p . Facem inducie dup p

1

Pentru p = 1, avem c G este graf conex cu n vrfuri. Fie r linii oarecare din matricea B. Suma lor va fi un vector care va avea cel puin o component nenul pentru r < n. n caz contrar, am avea c din mulimea de vrfuri corespunztoare celor r linii nu mai pleac (..) nici o muchie, deci G nu este conex. Rezult c orice r linii, cu r < n, deci B nu sunt liniar dependente. Suma celor n linii din B are toate componentele nule, deci rang B = n-1=dmiImB. Dac avem p componente conexe, vom considera subm. din B, B1,B2,...,Bp, corespunztoare componentelor conexe i aplicm pentru fiecare component conex pasul de inducie (pune Lema 1). Definiie. (G ) = dmi Im f , (G ) = dmiKerf . (G ) s.n. nr. ciclomatic al grafului G i (G ) - nr. co-ciclomatic Fie G = (X,U) i un circuit n graful G. Vom da acest circuit prin enumerarea muchiilor sale. Presupunem c sensul pozitiv de parcurgere a acestui circuit este cel dat de sensul acelor de ceasornic. Definim funcia g S1 (G ) astfel : g ( a ) = 1, daca i este orientat n sens pozitiv i g ( a ) = 1, dac a i este

orientat n sens invers. Dac a g ( a ) = 0 Propoziia 2 Dac este un ciclu n graful G = ( X , U ) g KerB Demonstaie. : Deoarece rang B = n p i dmiS1 (G ) = n dmiKerB = m u + p Presupunem c aplicaiei g i corespunde vectorul coloan V . Elementul ( BV ) i se abine nmulind rndul i din matricea B cu vectorul x . Dac vrful Vi nu este vrf pentru nici o muchie din , atunci ( BV ) i = 0 . Dac xi este vrf pentru o muchie din , atunci el va fi vrf pentru exact dou muchii i atunci din rezult c elementul modul cum am definit funcia g( Bv ) i = 0 Bv = 0 V KerB .

Deci numrul de cicluri dintr-un graf este egal cu m u + p. Arbori Un arbore este un graf conex i fr cicluri. O pdure este un graf pentru care fiecare component conex este un arbore. Obs. Noiunea de arbore se refer la 1 grafuri sau la grafuri neorientate, ambele fr muchii multiple. n studiul arborilor orientarea arcelor nu are importan. Prop. 3. Fie G = (X,U) un graf cu | X |= n 2 Sunt echivalente afirmaiile: i) G este arbore. ii) G este conex i minimal cu aceast proprietate. iii) G este fr cicluri i maximal cu aceast proprietate. Dac se adaug un arc ntre orice dou vrfuri neadiacente avem un ciclu unic. iv) G este fr cicluri i are n 1 arce. v) G este conex i are n 1 arce. vi) Pentru orice dou vrfuri distincte ale lui G exist un singur lan care le unete.

2

Demonstraie: i) ii) Fie e = ( x, y ) U o muchie din G. Din i) avem c G este conex. Fie graful G {e}. Dac acesta rmne conex rezult c avem drum ntre vrfurile x i y n G {e} ceea ce implic existena unui ciclu n graful G contradicii. ii) i) Artm c G nu are circuite. Presupunem c exist un circuit i e = uv o muchie din circuit . Fie d un drum arbitrar n G, dac e nu este muchie din acest drum, atunci d este din n G e. Dac e este muchie n d, atunci putem obine un drum n G e astfel: n loc de e n d punem drumul e , care determin n G e un drum cu aceleai extremiti ca i d n G, deci G e este conex, fab. i v) G fiind conex i fr cicluri p = 1 i m n +1 = 0 m = n 1 Analog i) iv). v) iii ) p = 1, m = n 1 (G ) = 0 i G este fr cicluri, dac se mai adaug o muchie, atunci avem un nou graf G i (G ' ) = 1 i deci ciclul este unic. iii) ii) Dac ar exista dou vrfuri nelegate prin nici un lan atunci nu am putea avea un ciclu prin adugarea unui arc ntre ele. Deci G este conex. Dac din G suprimm un arc, e = (x,y) iar graful G e este conex, atunci n G e exist, un lan de la x la y care mpreun cu e genereaz un ciclu n G, fab. ii) vi ) Dac avem vrfurile x i y legate prin dou lanuri distincte n graful G, atunci unul din ele conine o muchie e care nu o are cellalt i dac o suprimm graful G - e este conex, fab. vi) i) Rezult c G este conex i fr cicluri, pentru c existena unui ciclu ar nsemna c dou vrfuri din acel ciclu ar fi unite prin 2 lanuri distincte. Prop. 4. Orice graf conex G = (X,U) admite ca graf parial un arbore H = (X,V), numit arbore parial grafului G. Dem. Conform Prop.3. ii) acest arbore parial x obine suprimnd muchii din G cu condiia s se obin tot grafuri conexe. Det: i) Fie G un graf i v X a.. pentru orice alt vrf w X exist drum n graful de la V la W. Vrful v se numete rdcin ii) O arborescen este un arbore cu radcin. Fie G un graf neoriental i conex G = (X,U) cu |X| = n. Fie funcia l : U + a l (u ) - numit i costul muchiei u. Din prop.4 avem c G admite un arbore parial aceste este arbore minim (sau arbore de cost minim) dac sum lungimilor muchiilor sale este minim. Algoritmul lui KRUSKAL (1956) Se selecteaz muchia cea mai scurt muchie din graful G. Apoi dintre muchiile rmase se alege o muchie care nu formeaz cicluri cu cele deja alese i are lungimea cea mai mic pn se selecteaz n 1 muchiei. Algoritmul lui Kruskall se aplic pentru un graf neorientat arbitrar G = (X,U). Cnd G este conex tim c acest arbore exist. Cnd G nu este conex se descompune n componente conex e iar algoritmul va avea urmtoarea form: 3

1) Ordonm muchiile grafului n ordine cresctoare a costurilor sale. 2) O muchie va fi selectat daca are lungimea cea mai scurt dintre cele neselectate i care are capetele n componente conexe diferite (i se unete cu celelalte). Justificare: Fie 1 , 2 ,..., m muchiile grafului G (presupun a fi conex) ordonate a.. l ( 1 ) l ( 2 ) ... l ( m ) Vom demonstra prin reducere la absurd. Fie K arborele parial produs de acest algoritm i L arborele parial minim al grafului G. Vom arta c L = K Dac L K rezult c exist cel puin o muchie care se afl n unul dar nu este n cellalt. Fie i prima muchie cu aceast proprietate. Rezult c fiecare din muchiile 1 , 2 ,..., i 1 se gsesc fie toate n K i toate n L sau nici n R i nici n L. Cazul 1 i L dar i K . Dac prin aplicarea algoritmului muchia i nu este selectat, atunci i formeaz un ciclu cu muchiile din K deja selectate. Atunci muchiile din sunt din mulimea { 1 , 2 ,..., i 1 }. Dar cum aceste muchii se gsesc i n L i n K, dac {1 , 2 ,..., i 1 } K atunci se vor gsi i n L. Deoarece i L i i formeaz ciclul cu muchiile { 1 , 2 ,..., i 1 }, rezult c L contradicie. Cazul 2. i K dar i L. Presupunem c i = ( x, y ) U . Deoarece L este conex, exist n L un drum care unete pe x cu y, drum pe care-l vom nota cu . Deoarece nu utilizeaz muchia i , avem c { i ) formeaz un ciclu n graful G. i) Presupunem c i are cea mai mare lungime dintre toate muchiile din . Rezult c muchiile din se gsesc n mulimea { 1 , 2 ,..., i 1 }, deci K . Dar i K , deci K are un ciclu, fab. Deci i nu are cea mai mare lungime dintre muchiile drumului . ii) Fie e o muchie din drumul astfel nct l (e) > l ( i ) i presupunem c e = (z,w). Dac mutm muchia e din L i adugm muchia i nu vom forma un ciclu, deoarece a fost rupt prin eliminarea muchiei e. Va rezulta o mulime de muchii care au suma lungimilor mai mic dect lungimea lui L, deoarece l (e) > l ( i ) . Artm c aceste noduri sunt conectate cu altele i c nu pot forma un arbore. Vrfurile z i w rmn conectate n continuare. Vom avea un drum de la z la x, apoi urmeaz muchia i , apoi de la y la w. Deoarece (z,w) a fost singura muchie mutat, capetele sale rmn n continuare conectate. Deci noul set de vrfuri formeaz un arbore parial de lungime mai mic dect lungimea lui L, contradicie. Deci nu putem avea i K i i L, deci K = L. Algoritmul lui Prim (1957)

4

Algoritmul lui Kruskal selecteaz muchiile. Vom vedea n continuare un algoritm care selecteaz vrfurile dintr-un subgraf parial al lui G, Ki construit la pasul i al algoritmului. 1) Se alege un vrf oarecare x al grafului G i definim K1 = {x}. 2) Determinm cel mai apropiat vrf de x, notat y. Arborele K 2 = {X 2 , U 2 }, X 2 = {x, y},U 2 U ,U 2 = {( x, y )}. 3) Presupunem c la pasul i am obinut arborele Ki, atunci arborele Ki+1 se obine din Ki la care se mai adaug nodul yi, neselectat, cu proprietatea c este cel mai apropiat de Ki, ct i muchia de lungime minim care unete pe yi cu vrfurile din Ki Dup n pai arborele Kn va conine toate vrfurile grafului G, deci va fi un arbore parial al lui G. Algoritmul ia sfrit ca i n cazul alg. Kruskal se arat c arborele Kn este arbore parial minim. Aplicaii n informatic 1) Grmezi Vrfurile terminale ntr-un arbore se numesc pendante sau frunze. (Nici un drum de la rdcin la un alt vrf nu este mai mare ca [log 2 n] n cazul arborilor binari). Un arbore parial ordonat este un arbore binar n care vrfurile au primit cte o etichet. Aceste etichete pot reprezenta de exemplu valoarea unui element sau valoarea anumitor componente ale unui element. Etichetele sunt ordonate n funcie de prioriti. Eticheta unui vrf are prioritate mai mic dect cea a etichetelor ataate descendenilor acelui nod. Fie H = (X,U) un arbore a.. vrfurile sale au fost etichetate {1,2,...,n} cu 1 i rdcina, definit astfel: pentru orice i 2, n i U . Acest arbore este parial 2 ordonat. vrfurile lui sunt dispuse pe s+1 nivele, s = [log 2 n] , Nivelul i {0,....s} conine toate vrfurile aflate la distana i de radcina 1. Pe fiecare nivel i avem 2i vrfuri cu excepia ultimului nivel. H este un arbore parial ordonat. Def. O mulime total ordonat, ( H , ), H = {a1 , a 2 ,..., a n } formeaz o grmad binar dac pentru orice i {2,...., n} ai a i .2

Acesteia i putem ataa arborele H descris mai sus punnd n fiecare nod i elementul ai Deci valoarea fiecrui vrf este mai mic sau egal dect cea a descedenilor si. n general, descendentul stng al nodului ai este a2i i cel drept, dac exist, este a2i+1. Fie H = {a1 , a 2 ,..., a n } o mulime. Ne propunem s organizm aceast mulime ca o grmad. Acest lucru l facem insernd un element ntr-o gramada deja existent. Pornim de la o grmad cu un singur element i continum pn introducem toate cele n elemente. 2) Probleme de sortare-cutare. Fie H = (X,E) un arbore binar i ( A, ) o mulime total ordonat finit. H este arbore de binar de sortare-cutare pentru A dac avem 5

dat o etichetare a vrfurilor (aplicaia E : X A, e bijectiv ) astfel nct pentru orice x X , orice y din subarborele stng al lui x are E ( y ) E ( x ) i orice z din subarborele drept al lui x are E ( z ) > E ( x ) . PROBLEME DE SORTARE Ne propunem s ordonm cresctor mulimea A comparnd cte dou elemente, A = {a1 , a 2 ,..., a n } . Vom construi un arbore binar de sortare-cutare. Elementul a1 va fi eticheta rdcinii. Elementul a2 se compar cu a1, dac e mai mic sau egal va fi descendent stng, dac este strict mai mare va fi descendent drept. Fie elementul ai . Se compar cu a1, dac este a1 va face parte din subarborele su stng, dac > a1, va face parte din subarborele drept al lui a1. Presupunem c a i a1 . Se compar ai cu descendentul stng. Dac e este mai mic va face parte din subarborele stng, dac e mai mare va face parte din subarborele drept al acestuia s.a.m.d. pn cnd am ajuns la elementul n. Ordinea este dat de parcurgerea arborelui obinut n inordine (fiul stng, rdcin, apoi fiul drept). n felul acesta pot determina minimul ca fiind cea mai din stnga frunz i maximul mulimii A, ca fiind cea mai din dreapta frunz. Problema ordonrii cresctor este o problem de sortare. Cea a determinrii max i min ....probleme de cutare. Alte probleme de cutare a) Apartenena la o submulime B, a unui element x A, B A Fie x A, x B ? Se asociaz mulimii B arborele, de sortare- cutare. Acesta se parcurge din rdcin comparnd elementul x cu valoarea asociat nodului curent, pn ajungem la concluzia c x B Dac x B , atunci x devine o frunz pentru arborele ataat. b) Inseria unui element. Se parcurge arborele pornind de la rdcin (n inordine) pn se ajunge ntr-o frunz, atand acest element frunzei ca fiu drept sau stng. c) tergerea unui element a. Se determin nodul x etichetat cu a. dac este frunz atunci se terge x din arbore. Dac x are doar un descendent y se face legtura dintre printele lui x cu y i tergem apoi pe x. Dac x are doi descendeni, cutm n subarborele drept al lui x nodul y n care se afl cel mai mic element b care este de fapt succesorul imediat al lui a. Se nlocuiete n x valoarea a cu b i tergem nodul y. tergerea lui y se face uor deoarece el este frunz sau are doar descendent drept. 3) Parcurgerea arborilor Se poate face n inordine: se parcurge mai nti fiul stng, rdcina i la urm fiul drept. Aceast parcurgere este inordine.......... - postordine se parcurge nti descendentul stng, apoi cel drept i la urm rdcina 6

-

preordine se parcurge nti rdcina descendentul stng i apoi cel drept.

4) Evaluarea expresiilor algebrice Orice expresie algebric poate fi memorat sub forma unui arbore binar. Operatorii care apar {+,*, /,} au o anumit prioritate n efectuarea calculelor. De exemplu s considerm expresia (b + (c d ) * e) * a . Arborele binar asociat va fi : (Nodurile arborelui vor fi etichetate fie cu operatori fie cu operanzi) Dac parcurgem acest arbore n nordine obinem: b+c-d*e*a n postordine bcd-e*+a* n preordine *+b*-cdea

7

Curs nr. 10 PROBLEME DE COLORARE

Definitia 1: Fie G=(X,v) un graf oarecare (neorientat). Numrul cromatic al unui graf oarecare G, notat (G ) , este numrul minim de culori necesare pentru colorarea vrfurilor grafului, astfel nct dou vrfuri adiacente s nu fie colorate cu aceeai culoare. Definiia 2: Fie ( Ai ), i = 1, p o partiie a mulimii de vrfuri X. Spunem c partiia{ Ai}, i = 1, p este o colorare cu culori sau p-colorri a vrfurilor dac i numai dac orice dou vrfuri din Ai nu sunt adiacente. n aceast situaie graful se numete p-cromatic. Putem spune c (G ) este numrul minim p de culori pentru care avem o (G ) - colorare a grafului G. Vom nota cu N r (G ) nr. n r-colorrilor distincte a vrfurilor i eu t r = t (t 1) | (t 2)...(t r + 1), t C ()

Definiia 3. Polinomul P (G , t ) = N k (G )t k se numete polinomul .......asociat grafuluik =1

nt

G. El reprezint nr. t ....................... G , r t Fie q * atunci P(G,q) este numrul de colorri ale vrfurilor utiliznd q culori. Demonstraie: Orice K-colorare presupune utilizarea a k culori din cele maxim q culori k date, deci n total numrul lor este Aq = q(q 1)...(q k + 1) . Deci numrul total de culori al vrfurilor cu q culori este

Nk =1

n

k

(G )q k . Reciproc, orice colorare a vrfurilor grafului ag

n K q culori determin o partiie a lui n K- clase de colorare. Observaie 5: 1) Dac are n vrfuri, atunci N k (G ) = 0 pentru K > n i deci N n (G ) = 1, deci P(G, t ) este coeficientul termenului de grad maximum. 2) Dac G are 2 componente conexe C1 i C2 , putem avea pentru vrfurile din C1 i C2 colorri independente, deci Q(G, q) = Q(C1 , q) P(C2 , q). Propoziia 6: Fie G=(X1U) ..........S se arate c P(G, q ) =V U

(1)

|V |

q C (V ) , unde C(V)

reprezint numrul de componente co...........le are graful parial al lui G,(X,V). Demonstraie. Dac X este mulimea vrfurilor X cu |X|=n, V={u1,...,u} atunci o qcolorare a grafului G este o funcie k X {1,..., q} cu q 1, q cu proprietatea c dac ( xi , x j ) U K ( x ) K ( y ) .

1

Fie M i = {K : X {1,..., q} | K ( x) = K ( y ) , pentru ui = {x, y} U } . Si atunci, numrul funciilor care verific proprietatea de mai sus este : P (G , q ) = q n | M 1 U M 2 U ... U M n | Folosim principiul inducerii i al excluderii avem:

| M 1 U M 2 U ... U M m |= | M i |i =1

m

1i < j m

| M i I M j + ... + (1) m | I M i |i =1

m

| Mi =1

m

i

| reprezint numrul tuturor funciilor care au aceeai valoare n {1,2,...,q} pentru

fiecare component conex a unui graf parial al lui G cu o singur muchie n aceast situaie sunt n-1 comp. conexe, deci

| A |= qi =1 i

m

n 1

.

1i < j m

(M

i

I M j comp conex a unui

graf parial al lui G cu numai 2 muchii adiacente sau nu, deci avem n-2 comp. conexe. Rezult c

M i I M j = q n2 s.a.m.d., | I M i |= qi =1

n

pentru c o msur comp. conex. Deci P (G, q ) = (1)|V | q C (V ) unde C(V) sunt comp. conexe ale grafului parial (X,V).V U |V |

Exist algoritmi ce calculeaz polinomul cromatic al unui graf. Fie G=(X,U) un graf arbitrar l U , l = ( x, y ), x y o muchie a sa. Vom nota cu G-{l} graful obinut din G prin eliminarea muchiei: G {l} = ( X ,U {l}) i cu Gl graful obinut din G prin eliminarea a vrfurilor x i y i a muchiilor incidente cu aceste vrfuri i nlocuirea acestora cu un vrf unic n(x,y) care se va uni cu toate vrfurile din G sau erau adiacente fie cu x, fie cu y, fie cu ambele. Gl se numete contracia grafului G. Se observ G-{l} are o muchie mai puin dect G iar Gl are o muchie i un vrf mai puin dect graful G Propoziia 7. Cu notaiile mai sus, s se arate c P(G, q) = P(G {l}, q) P(Gl , q) Demonstraie. Dac funcia K X {l ,...q} este o q-colorare a grafului G, deoarece (*)1 Fie G = ( X ,U ), X = {x1 ...xn } un graf , A matricea sa de adiaceni. Vom nota cu m cea mai mic valoare proprie i cu M cea mai mare valoare proprie a sa. Propoziia 8. Dac G=(X,U) este graf B X , i GB este subgraful lui G generat de B, atunci a) M (G A ) M (G ) b) m (GB ) m (G ) c) d max (G ) M (G ) d min (G ) unde d max este cel mai mare grad al unui vrf din G i

d min este cel mai mic grad al unui vrf din G. Demonstraie. Presupunem c vrfurile din G au fost astfel numerotate a.. vrfurile din B s fie primele K vrfuri cu K M ( ) , Dar ( aij ) = < v, v > n i =1 j =1 deci M (G ) d min (G) Fie Z M n ,1 ( K ) vector ......corespunztor

valorii

proprii

M Z = ( Z1 ,...Z n ) t i

Z j = max | Z i |i =1,u

M Z j = a ji z i d j z j d max (G ) x j , deci M d max .Definiia 9. Graful G se numete q-critic dac (G ) = q i pentru orice subgraf GB, B X , B X generat de b avem (GB ) < (G ) . Propoziia 10. Presupunem c G este un graf cu numrul cromatic (G ) 2 . Atunci G are un subgraf (G ) - critic, GB, i orice vrf din GB are gradul n GB cel puin (G ) 1 . Demonstraie. Exist subgrafuri n G al cror nr. cromatic este (G ) (de exemplu el nsui) i alte subgrafuri care au nr. cromatic mai mic (de exemplu, din acel subgraf scoatem un vrf). Fie GB subgraful lui G al crui numr cromatic este (G ) i are cel mai mic nr. de vrfuri. Este clar c GB este (G ) - critic. ntr-adevr, fie x B , atunci G B {x} este un subgraf al grafului GB i este colorat cui =1

n

(G ) 1 culori. Dac gradul vrfului x n GB ,dx(GB), satisface inegalitatea d x (G B ) < (G ) 1 , atunci putem extinde aceast colorare cu (G ) 1 culori la graful GB, care avea (GB ) = (G ) , contradicie. Deci d x (G B ) (G ) 1 . Propoziia 11. (Wilt 1967) cu cu notaiile de mai sus pentru orice graf G avem relaia (G) 1 + M (G) . Demonstraie. Din propoziia 10. Fie GB un subgraf (G ) - critic al lui G. Avem atunci c (GB ) = (G ) i d min (GB ) (G ) 1 . Obinem: (G) d min (GB ) + 1 1 + M (GB ) 1 + M (G) K(x)K(y), pentru orice ................ e=(x,y), rezult c aceasta este o q-

colorare pentru graful G-{e} i reciproc, deci P(G-{e},q)-P(G,q) respectiv numrul colorrilor K din G-{e}, cu e=(x,y), i K(x)=K(y). Fie K o colorare a grafului G-{e} cu e=(x,y) i K(x)=K(y). Ea produce o qcolorare K a grafului Ge astfel definim K(z)=K(x)=K(y) i K(t)=kt pentru orice tz. Reciproc, orice q-colorare k a grafului Ge induce o q-colorare k a grafului G-

3

{e} cu K(x)=K(y), dac definim K(x)=K(y)=k(z) i k(G)=k(t) pentru orice tx,y. Rezult c: P(G-{e},q)-P(G,q)=P(Ge,q) pentru orice q numr natural. Ambii membri ai acestei egaliti sunt polinoame, deci egalitatea este valabil pentru orice q. Algoritmul lui Zykov (pentru determinarea numrului cromatic al unui graf). Mai nti facem urmtoarea observaie. Dac G este un graf i G un subgraf generat al su, orice q-colorare a vrfurilor lui G induce o q-colorare a vrfurilor lui G, deci (G) (G), deci (G)(G), unde prin (G) am notat cardinalul maxim al unei clici aa (graf simplu neorientat i complet). n general egalitatea nu este satisfcut. n [ ] se arat c pentru orice q,rN cu rq exist un graf, astfel nct (G)=q i (G)=r. Fie G=(X,U) graf, si x,y dou vrfuri neadiacente. Deci .... 7 avem c orice colorare, k, a grafului G-{e} este o q-colorare a grafului G i reciproc. Tot din aceeai propoziie avem c orice colorare a grafului G-{e} cu e=(x,y), k(x)=k(y) induce o colorare a grafului Ge i reciproc. Rezult c ................................................ pe de o parte i c (Ge)(G{e}). Cum G-{e} este subgraf n g, avem (G)(G-{e}), deci (G-{e})=min((Ge), (G-{e})). Pasul 1. Considerm graful G cu x,y dou vrfuri neadiacente. Fie G{e} graful obinut din G prin introducerea arcului e=(x,y) i Ge contracia grafului G, care este de fapt i contracia grafului G{e}. Din cele de mai sus, (dac lum n locul grafului G-{e}, graful G), obinem:

(G)=min((G{e}), V(Ge))Se consider separat grafurile G{e} sau Ge i se consider acest procedeu pn se obin grafuri care sunt clici. Pentru clici, numrul cromatic este egal cu

4

numrul de vrfuri. Atunci numrul cromatic va fi egal cu numrul maxim de vrfuri din G care pot forma o clic. Acest algoritm este destul de greu de utilizat practic, deoarece apar foarte multe grafuri care sunt analizate. Acest algoritm mai este cunoscut i sub numele de algoritmul legrilor i contraciilor. Un alt algoritm folosit n colorarea vrfurilor unui graf, este algoritmul greedy de colorare. Descrierea acestui algoritm este urmtoarea: 1) Se fixeaz o ordine de parcurgere a vrfurilor grafului. 2) Se atribuie primului vrf culoarea 1 i se parcurge mulimea vrfurilor astfel ordonat. Pentru un vrf se determin, cea mai mic culoare k, dintre cele date pn la momentul respectiv, care i se poate atribui, astfel nct acest vrf s nu poat fi adiacent cu nici un vrf care este colorat cu culoarea k. 3) Dac o astfel de culoare nu exist, se mrete mulimea culorilor cu o culoare distinct de cele deja existente, iar vrfului i se va atribui aceast culoare. Acest algoritm determin, n general, o q-colorare a grafului, care depinde de ordinea de parcurgere a vrfurilor grafului i nu numrului cromatic. Numrul cromatic va rezulta atunci cnd ordinea de parcurgere a vrfurilor grafului este dat de o permutare care are anumite proprieti, dup cum vom vedea n cele ce urmeaz. (Spunem c v od:od: > > print(`Matricea drumurilor este:`);

Matricea drumurilor este:

> print(A);

0 1 1 1 1 1

0 0 0 1 1 0

0 1 0 1 1 1

0 0 0 0 0 0

0 0 0 1 0 0

0 1 0 1 1 0

> C:=array(1..n):for i from 1 to n do C[i]:=0;od:ind:=0: > for j from 1 to n do for i from 1 to n do if A[i,j]=1 then ind:=ind+1:fi:C[j]:=ind:od:ind:=0:od:print(C):B:=convert(C, multiset):L:=[]:for i from 1 to n do for j from i+1 to n do if B[i][2]>B[j][2] then L:=B[i]:B[i]:=B[j]:B[j]:=L:fi:od:od:print(B):H:=array(1..n) :for i from 1 to n do H[i]:=B[i][1]:od:print(`Drumul hamiltonian este:`):print(H); > > > > > [ 5, 2, 4, 0, 1 , 3 ]

[ [ 4, 0 ], [ 5, 1 ], [ 2, 2 ], [ 6, 3 ], [ 3, 4 ], [ 1, 5 ] ]Drumul hamiltonian este:

[ 4, 5 , 2 , 6 , 3 , 1 ]9

> > > >

10