Anul I februarie – mai 2006 Seria 13 Cursul : ALGORITMCA GRAFURILOR CURSUL 1 marti 21 februarie 2006 , ora 18-20, Amf. II Concepte de baza. Definitii.Notatii.Exemple. 1. Multiset peste o multime R. Definitie. Notatii alternative. Apartenenta unui element la un multiset. Relatia de incluziune. Cardinalul unui multiset. 2. Puteri ale unei multimi S. Sp = multimea p-cuvintelor peste S. S(p) = multimea p-partilor lui S. S<p>= multimea p-multipartilor lui S. S* = multimea cuvintelor peste S. S(*) = multimea partilor lui S. S<*>= multimea multipartilor lui S. Exemple pentru cazul p=2. Expresia grafica asociata. 3. Grafuri. Grafuri orientate. Grafuri neorientate. Grafuri simple. 3.1. Adiacenta.Incidenta. 3.2. Grade. Grad interior. Grad exterior. Grad. Multisetul gradelor. Vectorul scor. Multisetul “victoriilor”. Multisetul “infrangerilor”. Exemple. CURSUL 2 marti 7 martie 2006 ,ora 18-20, Amf. II GRAFURI NEORIENTATE. GRADELE UNUI GRAF NEORIENTAT. 1. Multimea G(V) a grafurilor simple definite peste o multime V de varfuri. Transformarea t care conserva gradele in varfuri. Transformarea t* obtinuta prin iterarea transformarii t. Relatia de echivalenta ~ indusa de transformarea t* pe multimea G(V). TEOREMA.Clasele de echivalenta G(V)/~ coincid cu clasele de grafuri care au aceleasi grade in varfuri. (Lema 1,Lema 2 + exemple) 2. Multisetul (sirul) derivat s0

’ al unui multiset de numere s0.Exemple. Multiset grafic de numere. Conditii necesare ca un multiset de numere naturale sa fie grafic.Propozitia lui Euler.

TEOREMA lui Havel si Hakimi . Algoritmul de testare a caracterului grafic al unui multiset de numere . Algoritmul de constructie a unui graf cu multisetul gradelor cunoscut. Exemple. Complement. Extinderea transformarilor t si t* la cazul grafurilor neorientate. Exercitiu: Multisetul 11223344…nn este multiset graphic pentru n in N>1. CURSUL 3 marti 13 martie 2006,ora 18 – 20 ,Amf. II CONEXITATE. 1)Lanturi (elementare,simple,oarecare) Cicluri (elementare,simple,oarecare) Conexitate Relatia de echivalenta pe multimea varfurilor indusa de conectarea lanturi Multimea subgrafurilor unui graf simplu ordonata partial de relatia <= adica aceea de a fi subgraf Componenta conexa (doua variante de definitii : una privita drept clasa de echivalenta alta privita drept subgraf conex maximal) Descompunere in componente conexe EXEMPLE. ARBORI. 2)Arbori Definitia 1 T arbore T conex si acyclic Definitia 2 T arbore Exista o permutare a muchiilor lui T ,e1,e2,e3,…,em cu proprietatea: “pentru orice i , 2<= i <= m muchia ei are in comun cu muchiile e1,e2,e3,…,ei-1 exact un varf” PROPOZITIE: Definitia 1 Definitia 2 Enuntarea proprietatilor arborilor. (am demonstrat doua dintre ele iar restul le-am lasat exercitiu la seminar) APLICATII. 2.1)PROPOZITIE:In orice graf conex exista un arbore partial. (doua variante de argumentare: una pornind de la proprietatea arborilor de a fi “conexi muchie minimali” si alta constructiva bazata pe OBESRVATIA : “G conex intre orice doua parti nevide disjuncte care formeaza o partitie a multimii varfurilor exista o muchie “ ) 2.2)GRAFURI BIPARTITE Multime independenta de varfuri sau de muchii. p-colorari proprii a muchiilor unui graf (partile monocrome sunt independente). Definitia 1 pentru grafuri bipartite. Definitia 2 G bipartit G admite o bicolorare proprie

PROPOZITIE:Orice arbore este un graf bipartit. (doua variante de argumentare: una bazata pe constructia unei bicolorari; alta bazata pe notiunea de distanta in grafuri ) TEOREMA (KONIG) (doua variante de argumentare : una utilizand un arbore partial; alta pornind de la o parcurgere in adancime a grafului si utilizand notiunea de distanta). CURSUL 4 marti 27 martie 2006,ora 18-20.amf II APLICATII la capitolul ARBORI (continuare) 3 GRAFURI PLANARE 3.1 Definitie.. Reprezentare in plan.Harta.Fete. Grad al unei fete.Proiectie stereografica EXEMPLE. K5 nu este planar (demonstratie directa bazata pe unicitatea modulo un izomorfism a hartilor asociate ,succesiv,lui K1,K2,K3 si K4) K3,3 nu este planar (demonstratie directa) – exercitiu. 3.2 TEOREMA POLIEDRALA A LUI EULER. Demonstratia 1 (care utilizeaza un arbore partial). Demonstratia 2 (care calculeaza in doua moduri suma unghiurilor totale centrate in varfuri: * pe de o parte ea este 2 pi /V/; ** pe de alta parte ea este egala cu cu suma unghiurilor interne fetelor marginite - adica (d(f) – 2) pi (suma dupa f in F si f diferit de fata nemarginita ,f0) – la care se adauga suma unghiurilor din fata nemarginita ,f0, adica (d(f0) + 2) pi. APLICATIE: K5 este neplanar (se utilizeaza faptul ca cele mai mici fete ar avea gradul cel putin 3,formula lui Euler si formula care evalueaza suma gradelor fetelor) K3,3 este neplanar (aici gradul minim al unei fete ar trebui sa fie cel putin 4 – deoarece in K3,3 orice ciclu este par) – exercitiu. 3.3 Hamiltoneitate in grafuri planare. Definitia unui graf Hamiltonian. Harti hamiltoniene.Fete interioare.Fete exterioare. 3.3.1 TEOREMA Fie G graf simplu Hamiltonian.Avem: G este planar daca si numai daca graful intersectiilor corzilor ciclului Hamiltonian este bipartit. ALGORITM de testare a planaritatii unui graf Hamiltonian. APLICATIE: K5 este neplanar. (se utilizeaza faptul ca graful K5

este Hamiltonian) – exercitiu. K3,3 este neplanar (analog) - exercitiu. 3.3.2 Conditie necesara de hamiltoneitate a unui graf planar. TEOREMA LUI GRINBERG. CURSUL 5 marti 4 aprilie 2006,ora 18-20 , amf II ARBORI PARTIALI in GRAFURI CU MUCHIILE PONDERATE. 1) ARBORI PARTIALI. Arbore partial. Multimea arborilor partiali. Exemple. 2) GRAFURI CU MUCHIILE PONDERATE. Subgraf. Ponderea unui subgraf. Exemple. Ponderea unui lant. Lant optim. Distanta. OBSERVATII. * Orice sublant al unui lant optim este optim. ** Daca ponderea oricarei muchii este nenula atunci orice lant optim este elementar. 3) DEFINITII. SCOP. Arbori partiali optimi/economici. Arbori partiali ai distantelor unui varf x0. 4) DESCRIEREA ALGORITMILOR (in paralel). T=({x0},O) ALGORITMUL lui PRIM. Se repeta de n-1 ori operatiile urmatoare: <Se selecteaza o muchie e={x,y} cu x in Vi-1 si y in V-Vi-1 cu proprietatea w({x,y}) minim. T+e T> ALGORITMUL lui DIJKSTRA. Se repeta de n-1 ori operatiile urmatoare: <Se selecteaza o muchie e={x,y} cu x in Vi-1 si y in V-Vi-1 cu proprietatea dT(x0,x) + w({x,y}) minim. T+e T> OBSERVATIE: Cei doi algoritmi difera doar prin criteriul de selectie a muchiei e. 5) DEMONSTRATIA CORECTITUDINII ALGORITMILOR. Notatii commune necesare celor doua demonstratii. G=(V,E), E=V(2), w, x0. x0,x1,x2,x3,…..,xn-1, (indiciere in ordinea selectarii) e1,e2,e3,…..,en-1, (indiciere in ordinea selectarii) Vi={x0,x1,x2,x3,…,xi}, Ei={e1,e2,e3,…,en-1}. Ti=(Vi,Ei). LEMA In graful G exista arbori partiali optimi. TEOREMA 1. Un graf obtinut prin algoritmul lui PRIM este

un arbore optim. (demonstratia din cursul tiparit) LEMA In graful G exista arbori partiali ai distantelor varfului x0 la celelalte varfuri din G. TEOREMA 2. Un graf obtinut prin algoritmul lui DIJKSTRA este un arbore partial al distantelor vafului x0 la celelalte varfuri ale grafului. (o demonstratie noua,pornind de la ideea demonstratiei teoremei 1) CURSUL 6 marti 11 aprilie 2006, ora 18-20, amf. II ARBORI PARTIALI (continuare) 1. Comentarii.Completari. 1.2.Observatie. Un arbore partial economic poate sa nu fie un arbore al distantelor relative la un varf si reciproc. 1.3. O a doua demonstratie a teoremei 2 din cursul 5 privind algoritmul lui DIJKSTRA. 1.4. O alta descriere a algoritmului lui PRIM. T=(V,O) Se repeta de n-1 ori urmatoarele operatii: <Se selecteaza o muchie e de pondere minima cu un capat in componenta conexa care contine x0 iar celalalt capat intr-o alta componenta conexa. T+e T >. 1.5. ALGORITMUL lui KRUSKAL. T=(V,O) Se repeta de n -1 ori urmatoarele operatii: <Se selecteaza o muchie e de pondere minima cu capetele in componente conexe diferite. T+e T>. TEOREMA 3. Un graf obtinut prin algoritmul lui KRUSKAL este un arbore economic. Demonstratia 1. Se selecteaza un arbore economic care are in comun cu arborele KRUSKAL o secventa initiala de muchii de cardinal maxim. (exercitiu) Demonstratia 2. Se selecteaza un arbore economic care are in comun cu arborele KRUSKAL o multime de muchii de cardinal maxim. (exercitiu) 1.6. ALGORITMUL lui BORUVKA. T=(V,O) Algoritmul se desfasoara in etape. Intr-o etapa, pentru fiecare componenta conexa , se selecteaza o muchie de pondere minima un capat in ea iar celalalt capat intr-o alta componenta conexa. Se adauga apoi muchiile selectate la graful T. Algoritmul se sfarseste atunci cand T are o singura componenta conexa. Demonstratie:

1)Un graf obtinut prin algoritmul lui BORUVKA este un arbore partial. 2)Un graf obtinut prin algoritmul lui BORUVKA este un arbore partial economic.(exercitiu) EXERCITIU. Fie (G ,w) un graf simplu cu muchiile ponderate. Se pot mari ponderile muchiilor lui G cu cate o cantitate astfel incat graful ponderat (G ,w’) obtinut sa aiba urmatoarele proprietati: 1)Ponderea w’ este injectiva; 2)Un arbore partial economic din (G ,w’) este arbore partial economic in (G ,w) . marti 18 aprilie 2006 ora 18-20 amf II (inaintea PASTELUI) Nu a venit decat un student si cursul nu s-a tinut. marti 25 aprilie 2006 ora18-20 amf II = a 3-a zi de PASTE CURSUL 7 marti 2 mai 2006 ora 18-20 amf II CUPLAJE 1. Definitii. Notatii. Exemple. Comentarii. G=(V,E) graf simplu M inclus in E M cuplaj :< == > M este multime independenta :< == > orice e,f din M sunt neadiacente. Varf M – saturat Varf M – nesaturat Partititionarea multimii V in varfuri saturate si varfuri nesaturate. M* := cuplaj de cardinal maxim in G Exemple. G = Pn G = Cn G = Cn1 + Cn2 + Cn3 + … + Cnk . Exercitii. Care este cardinalul maxim al unui din G ? Cate cuplaje de cardinal maxim are G ? Cate cuplaje are G ? 2. SCOP : M*

Care este cardinalul lui M* ? Algoritmi pentru constructia unui M*

Lant M – alternant ; tipuri. Ciclu M – alternant Lant M – alternant deschis. Exemple. 3. Operatia “delta” diferenta simetrica. Diagrama Euler – Venn. Exemple. Operatia de constructie a negativului unui lant P , M – alternant deschis si obtinerea unui cuplaj de cardinal cu 1 mai mare, numita operatia de transfer de-a lungul lantului P : M’ = M delta E(P) Descrierea celor patru tipuri de componente conexe ale grafului [M1delta M2] indus de diferenta simetrica a doua cuplaje diferite M1 si M2 : ciclu M1,M2 – alternant; lant M1,M2 – alternant tip (M1,M2);

lant M1,M2 – alternant tip (M1,M1); lant M1,M2 – alternant tip (M2,M2). Compararea numarului de muchii din M1 cu numarul de muchii din M2 din fiecare componenta conexa: In primele doua tipuri numarul muchiilor din M1 si M2 este egal. In al treilea tip numarul muchiilor din M1 este mai mare cu 1 decat numarul muchiilor din M2. In al patrulea tip numarul muchiilor din M2 este mai mare cu 1 decat numarul muchiilor din M1. 4. TEOREMA (CLAUDE BERGE) M este cuplaj de cardinal maxim < == > <==> Orice lant M – alternant din G nu este deschis. 5. CUPLAJE IN GRAFURI BIPARTITE. 5,1. Amintim: definitia grafului bipartit teorema lui KONIG orice arbore este un graf bipartit 5.2. Definim “cuplaj al lui A in B”. TEOREMA lui HALL. Fie G = (A U B,E) un graf bipartit. Avem: G contine un cuplaj al lui A in B < == > < == > Orice lant M – alternant nu este deschis. CURSUL 8 marti 9 mai 2006 ora 16-18 amf. II CUPLAJE (continuare) ALGORITMUL UNGAR. ALGORITMUL KUHN_MUNKRES. 1. Amintim: definitia cuplajului M* cuplaj de cardinal maxim varf M-saturat lant M-alternant lant M-alternant deschis (crescator) transfer de-a lungul unui lant crescator graf bipartit cuplaj al lui A in B : G = (A U B,E) TEOREMA lui BERGE M este cuplaj de cardinal maxim < == > <==> Orice lant M – alternant din G nu este deschis. TEOREMA lui HALL Fie G = (A U B,E) un graf bipartit. Avem: G contine un cuplaj al lui A in B < == > < == > Orice lant M – alternant nu este deschis. 2. PROBLEMA PRACTICA. PROBLEMA PRACTICA 1. A = o multime de n oameni; B = o multime de n locuri de munca; Fiecare om din multimea A este calificat pentru o parte a multimii locurilor de munca B; Este posibil ca fiecare din cei n oameni din multimea A sa fie repartizat la cate un loc de munca din multimea B corespunzator calificarii sale ?

PROBLEMA PRACTICA 2. A = o multime de n oameni; B = o multime de n locuri de munca; Fiecare om din multimea A are pentru fiecare loc de munca din B o calificare cu o anumita pondere; Se cere sa se repartizeze oamenii din multimea A pe locurile de munca din B ,cate unul pe un loc, astfel incat suma ponderilor calificarilor lor sa fie maxima. 3. REZOLVAREA CELOR DOUA PROBLEME. 3.1. PROBLEMA 1. ALGORITMUL UNGAR. Amintim problema: A = o multime de n oameni; B = o multime de n locuri de munca; Fiecare om din multimea A este calificat pentru o parte a multimii locurilor de munca B; Este posibil ca fiecare din cei n oameni din multimea A sa fie repartizat la cate un loc de munca din multimea B corespunzator calificarii sale ? MODELARE. Se considera : G = (A U B,E) graf bipartit; /A/ = /B/ = n; E = {{a,b}/ a in A, b in B, a este calificat pentru locul de munca b}. SCOP: Determinarea unui cuplaj perfect in graful G , daca exista.. ALGORITMUL: Se selecteaza un cuplaj oarecare M (poate fi o muchie oarecare) in G. 1. Daca M satureaza A atunci M este cuplaj perfect STOP. Daca M nu satureaza A atunci : se selecteaza un varf a in A M - nesaturat X := {a}, Y := O , E(T) := O. T := ({a},O). 2. Daca NG(X) = Y atunci nu exista cuplaj perfect STOP. Daca NG(X) diferit Y atunci : se selecteaza b in NG(X) – Y; fie a’ in X cu {a’,b} in E. 3. Daca b este M – saturat atunci : fie a” in B – X cu {a”,b} in M ; X := X U {a”}, Y := Y U {b}, E(T) := E(T) U {{a’,b},{b,a”}}; T := (X UY, E(T)) ; REPETA 2. Daca b este M – nesaturat atunci: fie P a,a’ – lantul M – alternant din T; P’ := P + [a’,b]; se efectueaza un transfer de-a lungul lantului P’ : M := M delta E(P’); REPETA 1.

3.2. PROBLEMA 2. ALGORITMUL KUHN-MUNKRES. Amintim problema: A = o multime de n oameni; B = o multime de n locuri de munca; Fiecare om din multimea A are pentru fiecare loc de munca din B o calificare cu o anumita pondere; Se cere sa se repartizeze oamenii din multimea A pe locurile de munca din B ,cate unul pe un loc, astfel incat suma ponderilor calificarilor lor sa fie maxima. MODELARE. Se considera : G = (A U B,E) graf bipartit; /A/ = /B/ = n; E = {{a,b}/ a in A, b in B, a este calificat pentru locul de munca b}; w : E --> R>=0 Se defineste ponderea unui cuplaj M: w(M) = Suma w(e) pentru e in M. SCOP: Determinarea unui cuplaj perfect in graful G cu ponderea maxima. PREGATIRI. Se defineste o pondere majoranta in varfuri , l : A U B ---> R cu proprietatea l(a) + l(b) >= w({a,b}), orice a in A si orice b in B. EXEMPLU. l(a) = max {w({a,b})/ b in B} orice a in A; l(b) = 0 orice b in B. Se defineste graful egalitatii Gl asociat ponderii majorante l a varfurilor in raport cu ponderea w a muchiilor astfel: V(Gl) = A U B; E(Gl) = {{a,b}/ a in A; b in B; l(a) + l(b) >= w({a,b})}. TEOREMA . Un cuplaj perfect in Gl este cuplaj perfect de cardinal maxim in G. METODA. Se defineste o pondere majoranta, l. Se repeta pana se determina un cuplaj perfect M urmatoarele operatii: <<Se cauta un cuplaj perfect M in graful egalitatii Gl cu algoritmul ungar. In cazul in care un astfel de cuplaj nu exista NGl(X) = Y se imbunateste ponderea l astfel incat NGl(X) diferit Y si muchiile arborelui M – alternant T , construit in algoritm ,sa se conserve in noul graf al egalitatii Gl. >> ALGORITMUL. Se construieste o pondere majoranta in varfuri, l. Se construieste graful egalitatii Gl. Se selecteaza un cuplaj oarecare M (poate fi o muchie oarecare) in Gl. 1. Daca M satureaza A atunci M este cuplaj perfect STOP. Daca M nu satureaza A atunci : se selecteaza un varf a in A M - nesaturat

X := {a}, Y := O , E(T) := O. T := ({a},O). 2. Daca NGl(X) = Y atunci nu exista cuplaj perfect in Gl. Se redefineste ponderea l . dl := min { l(a) + l(b) - w({a,b}/a in X; b in B – Y}; l’: A U B ---> R astfel: l’(a) = l(a) – dl pentru a in X; l’(b) = l(b) + dl pentru b in Y; l’(v) = l(v) in rest. Se construieste graful egalitatii Gl’. l := l’; Gl := Gl’. se selecteaza b in NGl(X) – Y; fie a’ in X cu {a’,b} in E. REPETA 3. Daca NGl(X) diferit Y atunci : se selecteaza b in NGl(X) – Y; fie a’ in X cu {a’,b} in E. REPETA 3. 3. Daca b este M – saturat atunci : fie a” in B – X cu {a”,b} in M ; X := X U {a”}, Y := Y U {b}, E(T) := E(T) U {{a’,b},{b,a”}}; T := (X UY, E(T)) ; REPETA 2. Daca b este M – nesaturat atunci: fie P a,a’ – lantul M – alternant din T; P’ := P + [a’,b]; se efectueaza un transfer de-a lungul lantului P’ : M := M delta E(P’); REPETA 1. CURSUL 9 marti 16 mai 2006 ora 18-20 amfiteatrul II RETELE DE TRANSPORT. CURSUL 10 marti 23 mai 2006 ora 18-20 amfiteatrul II RETELE DE TRANSPORT (continuare). REZUMATUL CURSURILOR 9 si 10. 1. DEFINITII. NOTATII. REZULTATE DE BAZA. 1.1. Chestiuni generale. Fie G = (V , E) un graf orientat si r : E N>=0 o functie pondere definite pe multimea arcelor sale. Notam : * pentru e in E e - = extremitatea initiala a arcului e (varful origine),

e + = extremitatea finala a arcului e (varful terminus); * pentru S , T parti disjuncte ale lui V (S , T) = multimea arcelor e cu e- in S si e+ in T; [S , T] = (S , T) U (T , S), in particular vom considera multimi de arce de tipul urmator (S , V-S) si (V-S , S); * pentru S parte a lui V r +(S) = suma ponderilor arcelor e cu e- in S si e+ in V-S, r - (S) = suma ponderilor arcelor e cu e- inV-S si e+ in S; * pentru K parte a lui E r(K) = suma ponderilor arcelor din K. Observatie. r +(S) = r ((S , V-S)) si r -(S) = r((V-S , S)). PROPOZITIA 1. Pentru S parte nevida a lui V avem : Suma r(uv) pentru uv in E cu u,v in S = Suma r(vu) pentru vu in E cu v,u in S = = r (E (G [S] )) PROPOZITIA 2. Pentru S parte nevida a lui V avem : r +(S) – r -(S) = Suma (r +G (u) – r

–G (u)) pentru u in S.

1.2. Retea de transport. N = (G,X,I,Y,c) unde : G = (V,E) este graf orientat si V = X U I U Y; X = multimea intrarilor; I = multimea varfurilor intermediare; Y = multimea iesirilor; X , Y si E sunt nevide; X, I si Y sunt multimi disjuncte; c : E N>=0 functia capacitate. 1.3. Flux f in reteaua N. f : E N>=0 cu proprietatile : (1) Conditiile de marginire: 0 <= f(e) <= c(e) orice e in E; (2) Conditiile de conservare a fluxului: f +(v) = f -(v) orice v in I. Notam : F(N) = {f / f flux in reteaua N}. PROPOZITIA 3. Pentru o retea N = (G , X , I , Y , c), un flux f in N si o parte S cu

X inclus in S inclus in X U I avem f +(S) – f -(S) = f +(X) – f – (X) . CONSECINTA 4. Pentru S = X U I avem : f - (Y) – f +(Y) = f +(X) – f - (X) . Notam : val (f) := f +(X) – f –(X); Numarul val (f) se numeste valoarea fluxului f. Notam cu f * un flux de valoare maxima : val(f *) = max {val(f) / f in F } si F *(N) = {f * / f * in F (N) , val(f *) maxim}. 2. SCOP. Determinarea unui flux de valoare maxima. 3. Vom considera cazul in care avem: X = {x} , Y = {y} ; d –(x) = 0 si d +(y) = 0 . 3.1. PREGATIRI 3.1.1. TAIETURI INTR-O RETEA. O taietura K este o multime de tipul (S , V – S) unde S este parte a lui V cu x in S si y in V – S. Notam K(N) = {K / K taietura in reteaua N} Pentru K in K (N) , numarul c(K) se numeste capacitatea taieturii K. Notam cu K~ o taietura de capacitate minima: c(K~) = min {c(K) / K in K} si K ~ (N) = {K ~ / K ~ in K (N) , c(K ~ ) minim}. Fie o parte S a multimii varfurilor V cu x in S si y in V – S . Pentru un arc e din (S , V – S) U (V – S , S) definim c(e) – f(e) daca e este in (S , V – S), i S (e) = 0 daca e este in (V – S , S). De asemenea , notam i (S) = min{i S (e) / e in (S , V – S) U (V – S , S) }. Vom spune ca taietura K = (S , V – S) este f – saturata daca si numai daca, prin definitie, avem: i (S) = 0. 3.1.2. LANTURI INTR-O RETEA. Fie u,v doua varfuri diferite din reteaua N si P un u,v – lant.

Pentru un arc e din E(P) definim c(e) – f(e) daca e este un “arc inainte in P”, i P (e) = f(e) daca e este un “arc inapoi in P”. De asemenea , notam i (P) = min {i P (e) / e in E(P)}. Vom spune ca a,b – lantul P este f – saturat daca si numai daca, prin definitie, avem: i (P) = 0. 3.1.3. REVIZUIREA UNUI FLUX DE-A LUNGUL UNUI x,y-LANT NESATURAT. Fie P un x,y-lant nesaturat. Se defineste un flux f ’ : E ---> N>=0 astfel : f(e) + i(P) daca e este arc inainte in P; f ‘(e) = f(e) – i(P) daca e este arc inapoi in P; f(e) in rest. f ‘ este flux. Vom spune ca fluxul f ‘ este obtinut prin revizuirea fluxului f de-a lungul x.y-lantului nesaturat P. Observatie. (1) val(f ‘) = val(f) + i(P) > val(f). (2) x,y- lantul P este f ‘ – saturat. (3) Existenta unui x,y – lant f – nesaturat P intr-o retea N este semnificativa deoarece de aici rezulta ca fluxul f nu este flux maxim. De asemenea, prin revizuirea lui f de-a lungul lui P f poate fi transformat intr-un flux f ’ de valoare mai mare. 3.1.4. DEFINIREA UNEI TAIETURI f-SATURATE INTR-O RETEA IN CARE ORICE x , y – LANT ESTE f - SATURAT. Consideram situatia in care orice x ,y – lant este f – saturat, adica i(P) = 0. Se defineste o taietura K = (S , V - S) din K(N) selectand multimea S astfel : S = {u / u in V(G) si exista un x , u – lant f - saturat } K este o taietura f – saturata. 3.2. PROPOZITIA 5. Fie N = (G , X , I , Y , c) o retea de transport. (1) Pentru orice flux f din F (N) si orice taietura K din K(N) avem: val (f) <= c (K); (2) Sunt adevarate implicatiile : (2.1) val (f) = c (K) <==> Taietura K este f - saturata. (2.2) val (f) = c (K) ==> f este in F * (N) si K este in K ~ (N). (2.3) Taietura K este f - saturata ==> f este in F * (N) si K este in K ~ (N).

PROPOZITIA 6. Fie N = (G , X , I , Y , c) o retea de transport. Este adevarata echivalenta : f este in F * (N) < == > Orice x,y – lant din N este f-saturat. TEOREMA 7. (FORD – FULKERSON) Fie N = (G , X , I , Y , c) o retea de transport. Avem: val (f *) = c (K ~). 3.3. ALGORITMUL FORD – FULKERSON 0. Se considera un flux initial f definit prin f(e) = 0 pentru e in E(G). 1. t(x)=infinit T = ({x},O) 2. Se cauta o muchie e in [V(T),V(G)-V(T)] , e = uv cu u in V(T) , v in V(G) – V(T), i V(T) (e) > 0. 2.1. Daca muchia e nu exista atunci : f este in F * (N), STOP. 2.2. Daca muchia e exista atunci : t(v) = min {t(u), i V(T) (e)}, T = T + [e]. 2.2.1. Daca y este in V(T) atunci: Se revizuieste fluxul f de-a lungul unicului x,y-lant din T, REPETA 1. 2.2.2. Daca y nu este in V(T) atunci: REPETA 2. Obesrvatie. Algoritmul are un numar finit de pasi deoarece vectorul (val(f) , /V(T)/) ia valori in multimea {0 , 1 , 2 , … , c + (x)} x {1 ,2,3, … ,/V(G)/} si la repetarea pasilor 1 sau 2 , vectorul (val(f) , /V(T)/) creste strict in raport cu ordinea lexicografica . Algoritmul nu se sfarseste daca /V(T)/ = /V(G)/ deoarece in acest caz avem V(T) = V(G) si atunci y fiind in V(T) fluxul f este revizuibil. Deci algoritmul nu poate sfarsi decat in cazul in care se ajunge la val(f) maxim.