Alg_graf

ALGORITMICA GRAFURILOR

Conf. univ. dr. COSTEL BALCAU

2011

Tematica

1 Aranjamente, combinari, permutari 41.1 Preliminarii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Produs cartezian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Submultimi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Aranjamente cu repetitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5 Aranjamente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.6 Permutari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.7 Combinari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.8 Combinari cu repetitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.9 Permutari cu repetitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Partitii 172.1 Compuneri ale unui numar natural . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2 Partitii ale unui numar natural . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3 Partitii ale unei multimi finite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Grafuri 243.1 Definitii generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.2 Reprezentarea grafurilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3 Grade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.4 Conexitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.5 Parcurgerea grafurilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.6 Algoritmul Roy-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4 Arbori 424.1 Numarul ciclomatic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2 Teorema de caracterizare a arborilor . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.3 Numararea arborilor partiali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.4 Arbori partiali de cost minim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5 Arborescente 535.1 Teorema de caracterizare a arborescentelor . . . . . . . . . . . . . . . . . . . . . . . . 535.2 Arborescente partiale de cost minim . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

6 Clase particulare de grafuri 616.1 Grafuri euleriene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.2 Grafuri hamiltoniene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.3 Grafuri bipartite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

1

TEMATICA 2

7 Distante si drumuri minime 737.1 Expunerea problemei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737.2 Algoritmul Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757.3 Algoritmul Roy-Floyd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

8 Fluxuri ın retele de transport 818.1 Problema fluxului maxim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818.2 Algoritmul Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

Bibliografie

[1] Gh. Barbu, I. Vaduva, M. Bolosteanu, Bazele informaticii, Editura Tehnica, Bucuresti, 1997.

[2] Gh. Barbu, V. Paun, Calculatoare personale si programare ın C/C++, Editura Didactica si Pedagogica, Bu-curesti, 2005.

[3] C. Balcau, Combinatorica si teoria grafurilor, Editura Universitatii din Pitesti, Pitesti, 2007.

[4] E. Ciurea, Algoritmi. Introducere ın algoritmica grafurilor, Editura Tehnica, Bucuresti, 2001.

[5] E. Ciurea, L. Ciupala, Algoritmi. Introducere ın algoritmica fluxurilor ın retele, Editura Matrix Rom, Bucuresti,2006.

[6] C. Croitoru, Tehnici de baza ın optimizarea combinatorie, Editura Universitatii ”Al. I. Cuza”, Iasi, 1992.

[7] L. Livovschi, H. Georgescu, Sinteza si analiza algoritmilor, Editura Stiintifica si Enciclopedica, Bucuresti, 1986.

[8] D.R. Popescu, Combinatorica si teoria grafurilor, Societatea de Stiinte Matematice din Romania, Bucuresti,2005.

[9] C.P. Popovici, H. Georgescu, L. State, Bazele informaticii. Vol. I si II, Editura Universitatii din Bucuresti,Bucuresti, 1990-1991.

[10] L. State, Elemente de logica matematica si demonstrarea automata a teoremelor, Tipografia Universitatii dinBucuresti, Bucuresti, 1989.

[11] T. Toadere, Grafe. Teorie, algoritmi si aplicatii, Editura Albastra, Cluj-Napoca, 2002.

[12] I. Tomescu, Combinatorica si teoria grafurilor, Tipografia Universitatii din Bucuresti, Bucuresti, 1978.

[13] I. Tomescu, Probleme de combinatorica si teoria grafurilor, Editura Didactica si Pedagogica, Bucuresti, 1981.

[14] I. Tomescu, Data structures, Editura Universitatii din Bucuresti, Bucuresti, 2004.

3

Tema 1

Aranjamente, combinari, permutari

1.1 Preliminarii

In aceasta lectie vom prezenta formule de numarare si algoritmi de generare (enumerare) pentrucele mai cunoscute familii de obiecte combinatoriale: produs cartezian, submultimi, aranjamente(fara repetitie, cu repetitie sau ordonate), combinari (fara repetitie sau cu repetitie), permutari (fararepetitie sau cu repetitie). Reamintim ın continuare cateva notiuni uzuale.

Definitia 1.1.1. Fie A o multime finita. Numarul de elemente ale lui A, notat cu card (A), senumeste cardinalul multimii A.

Definitia 1.1.2. Fie A un alfabet (adica o multime finita) si n ∈ N�. O secventa de forma

a = a1a2 . . . an, cu a1, a2, . . . , an ∈ A,

se numeste cuvant de lungime n peste alfabetul A. Lungimea cuvantului a se noteaza cu |a|.Observatia 1.1.1. Evident, cuvantul a1a2 . . . an poate fi identificat cu vectorul (a1, a2, . . . , an).

Definitia 1.1.3. Fie A o multime (alfabet) total ordonata si x = (x1, . . . , xn), y = (y1, . . . , ym)doi vectori (cuvinte) cu elemente (litere) din A. Spunem ca x este mai mic decat y ın ordinelexicografica si notam x ≺ y daca

(x1, . . . , xn) = (y1, . . . , yn) si m > n

sau daca exista un indice i, i ≤ min{m,n}, astfel ıncat

(x1, . . . , xi−1) = (y1, . . . , yi−1) si xi < yi.

Definitia 1.1.4. Fie x ∈ R si n ∈ N. Notam

[x]n =

⎧⎨⎩

1, daca n = 0,x(x− 1) . . . (x− n+ 1)︸︷︷︸

n factori

, daca n ≥ 1, [x]n =

⎧⎨⎩

1, daca n = 0,x(x+ 1) . . . (x+ n− 1)︸︷︷︸

n factori

, daca n ≥ 1.

[x]n se numeste polinomul factorial descrescator de gradul n, iar [x]n se numeste polinomulfactorial crescator de gradul n.

4

TEMA 1. ARANJAMENTE, COMBINARI, PERMUTARI 5

1.2 Produs cartezian

Definitia 1.2.1. Produsul cartezian al multimilor A1, A2, . . . , An (n ∈ N�) este multimea

A1 × A2 × . . .× An = {(a1, a2, . . . , an)|a1 ∈ A1, a2 ∈ A2, . . . , an ∈ An}.

Exemplul 1.2.1. {a, b} × {+,−} × {c} = {(a,+, c), (a,−, c), (b,+, c), (b,−, c)}.Propozitia 1.2.1 (de numarare a produsului cartezian). Fie n ∈ N

� si A1, A2, . . . , An multimifinite. Atunci card (A1 × A2 × . . .× An) = card (A1) · card (A2) · . . . · card (An).

Demonstratie. Se utilizeaza metoda inductiei matematice dupa n.

Algoritmul 1.2.1 (de generare a produsului cartezian). Fie multimile standard

A1 = {1, 2, . . . ,m1}, A2 = {1, 2, . . . ,m2}, . . . , An = {1, 2, . . . ,mn}.

Vom utiliza ”regula urmatorului”.

• Primul element al produsului cartezian A1 × A2 × . . .× An, ın ordine lexicografica, este

(c1, c2, . . . , cn) = (1, 1, . . . , 1).

• Un element arbitrar (curent)

(c1, . . . , ck−1, ck, ck+1, . . . , cn)

are un element urmator daca si numai daca exista un indice k ∈ {n, . . . , 1} astfel ıncat ck < mk.In acest caz, luand cel mai mare indice k cu aceasta proprietate, elementul urmator, ın ordinelexicografica, este

(c1, . . . , ck−1, ck + 1, 1, . . . , 1).

In pseudocod, algoritmul poate fi descris sub formaprodus cartezian(n,m) :{ pentru i = 1, n ci ← 1;

afisare(c, n);repeta{ k ← n;

cat timp (ck = mk) si (k > 0) k ← k − 1;daca (k > 0){ ck ← ck + 1;pentru i = k + 1, n ci ← 1;afisare(c, n);}

}cat timp (k > 0);

},unde functia de afisare esteafisare(c, n) :{ pentru i = 1, n afiseaza ci;}.

Programul C++ corespunzator este:


#include<iostream.h> // Generarea ITERATIVA - ordine LEXICOGRAFICA -#include<conio.h> // a PRODUSULUI CARTEZIANint n,m[50],nr=0; // nr=variabila pt. numerotarevoid afisare(int x[50],int nx){ int i;

cout<<++nr<<") ";for(i=1;i<=nx;i++) cout<<x[i]<<’ ’;cout<<endl;if(wherey()==25){ cout<<" <enter> pt. continuare";getch();clrscr();

}}void produs_cartezian(int n,int m[50]){ int c[50],i,k;

for(i=1;i<=n;i++) c[i]=1;afisare(c,n);do{ k=n;while ((c[k]==m[k]) && (k>0)) k--;if (k>0){ c[k]++;

for(i=k+1;i<=n;i++) c[i]=1;afisare(c,n);

}}while (k>0);

}void main(void){ int i;

clrscr();cout<<"Dati numarul de multimi: n=";cin>>n;for(i=1;i<=n;i++){ cout<<"Dati numarul de elemente ale multimii A"<<i<<": m["<<i<<"]=";cin>>m[i];

}cout<<"Elementele produsului cartezian sunt:\n";produs_cartezian(n,m);getch();

}

Observatia 1.2.1. Pentru generarea produsului cartezian A1 × A2 × . . . × An al unor multimi finitearbitrare

A1 = {a11, a12, . . . , a1m1}, A2 = {a21, a22, . . . , a2m2}, . . . , An = {an1, an2, . . . , anmn}se poate folosi algoritmul anterior, bazat pe generarea indicilor, ınlocuind afisarea indicilor ci cuafisarea elementelor corespunzatoare aici

din multimile Ai, adica ınlocuind functia afisare(c, n) cufunctiaafisare(c, a, n) :{ pentru i = 1, n afiseaza aici

;}.

1.3 Submultimi

Propozitia 1.3.1 (de numarare a submultimilor). Fie A o multime finita si P(A) multimeatuturor submultimilor (partilor) lui A. Atunci card (P(A)) = 2card (A).


Demonstratie. Fie A = {a1, a2, . . . , an}, n ∈ N�. Notam {1, 2}n = {1, 2} × . . .× {1, 2}︸︷︷︸

de n ori

.

Definim functiile α : P(A)→ {1, 2}n si β : {1, 2}n → P(A) prin:

• ∀B ∈ P(A), α(B) = (c1, c2, . . . , cn), unde ci =

{1, daca ai ∈ B,2, daca ai ∈ B;

• ∀ (c1, c2, . . . , cn) ∈ {1, 2}n, β(c1, c2, . . . , cn) = {ai|ci = 1, i ∈ {1, . . . , n}}.Functiile α si β sunt inverse una celeilalte, deci sunt bijective si card (P(A)) = card ({1, 2}n) = 2n.

Exemplul 1.3.1. PentruA = {a, b, c}, corespondenta submultimi ↔ produs cartezian din demonstratiaanterioara este redata ın urmatorul tabel:

(c1, c2, c3) ∈ {1, 2}3 B ∈ P(A)

(1,1,1) {a, b, c}(1,1,2) {a, b}(1,2,1) {a, c}(1,2,2) {a}(2,1,1) {b, c}(2,1,2) {b}(2,2,1) {c}(2,2,2) ∅

Deci A are 23 = 8 submultimi.

Algoritmul 1.3.1 (de generare a submultimilor). Fie multimea A = {a1, a2, . . . , an}. Conformdemonstratiei anterioare, putem genera produsul cartezian {1, 2}n cu Algoritmul 1.2.1 ınlocuindafisarea elementelor (c1, . . . , cn) cu afisarea submultimilor corespunzatoare

B = {ai|ci = 1, i ∈ {1, . . . , n}}.

Obtinem urmatorul algoritm descris ın pseudocod.submultimi(a, n) :{ pentru i = 1, n ci ← 1;

afisare(c, a, n);repeta{ k ← n;

cat timp (ck = 2) si (k > 0) k ← k − 1;daca (k > 0){ ck ← 2;pentru i = k + 1, n ci ← 1;afisare(c, a, n);}

}cat timp (k > 0);

},unde functia de afisare esteafisare(c, a, n) :{ pentru i = 1, n daca (ci = 1) afiseaza ai;}.


1.4 Aranjamente cu repetitie

Propozitia 1.4.1 (de numarare a aranjamentelor cu repetitie). Fie m,n ∈ N. Atunci numarulde cuvinte de lungime n peste un alfabet cu m litere este egal cu mn.

Demonstratie. Fie B = {1, 2, . . . ,m} si C = {(c1, c2, . . . , cn)|ci ∈ B ∀ i}. Cum C = Bn, conformPropozitiei 1.2.1 avem card (C) = mn.

Definitia 1.4.1. Cuvintele numarate ın propozitia anterioara se numesc aranjamente cu repetitiede m luate cate n. Prin abuz de limbaj, si numarul lor, adica mn, se numeste tot aranjamente curepetitie de m luate cate n.

Exemplul 1.4.1. Pentru m = 2 si n = 3, aranjamente cu repetitie sunt, ın ordine lexicografica:

(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2).

Deci avem 23 = 8 aranjamente cu repetitie.

Algoritmul 1.4.1 (de generare a aranjamentelor cu repetitie, sub forma de cuvinte). Pentrumultimea standard B = {1, 2, . . . ,m}, conform demonstratiei anterioare putem genera produsulcartezian Bn, cu Algoritmul 1.2.1, luand m1 = m2 = · · · = mn = m.

Observatia 1.4.1. Pentru o multime A = {a1, a2, . . . , an} oarecare putem genera indicii (c1, . . . , cn)cu algoritmul anterior si afisa elementele corespunzatoare acestor indici (ac1 , . . . , acn).

1.5 Aranjamente

Propozitia 1.5.1 (de numarare a aranjamentelor). Fie m,n ∈ N. Atunci numarul de cuvinte delungime n cu litere distincte peste un alfabet cu m litere este egal cu [m]n.

Demonstratie. Fie B = {1, 2, . . . ,m} si C1 = {(c1, c2, . . . , cn)|ci ∈ B ∀ i, ci = cj ∀ i = j}. AvemC1 = {(c1, c2, . . . , cn)|c1 ∈ {1, . . . ,m}, c2 ∈ {1, . . . ,m} \ {c1}, c3 ∈ {1, . . . ,m} \ {c1, c2}, . . . , cn ∈{1, . . . ,m} \ {c1, . . . , cn−1}}, deci card (C1) = m(m− 1)(m− 2) . . . (m− n+ 1) = [m]n.

Definitia 1.5.1. Cuvintele numarate ın propozitia anterioara se numesc aranjamente (fara repetitie)de m luate cate n. De asemenea si numarul lor, adica [m]n, se numeste tot aranjamente (fararepetitie) de m luate cate n si se mai noteaza cu An

m.

Observatia 1.5.1. Pentru n > m avem [m]n = m. . . (m−m) . . . (m− n+ 1) = 0.

Exemplul 1.5.1. Pentru m = 4 si n = 2, aranjamentele sunt, ın ordine lexicografica:

(1, 2), (1, 3), (1, 4), (2, 1), (2, 3)(2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3).

Deci avem [4]2 = 4 · 3 = 12 aranjamente.

Un algoritm pentru generarea aranjamentelor va fi prezentat ın Sectiunea 1.7.

1.6 Permutari

Propozitia 1.6.1 (de numarare a permutarilor). Fie n ∈ N. Atunci numarul de cuvinte cecontin exact o data fiecare litera a unui alfabet cu n litere este egal cu n!, unde

n! = 1 · 2 · 3 · · · · · n (n factorial), 0! = 1.


Demonstratie. Luam m = n ın Propozitia 1.5.1 si folosim egalitatea [n]n = n(n− 1) . . . 1 = n!.

Definitia 1.6.1. Cuvintele numarate ın propozitia anterioara se numesc permutari (fara repetitie)de ordinul n. De asemenea si numarul lor, adica n!, se numeste tot permutari (fara repetitie)de n.

Exemplul 1.6.1. Pentru n = 3, permutarile multimii standard {1, 2, 3} sunt, ın ordine lexicografica:

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Deci avem 3! = 1 · 2 · 3 = 6 permutari.

Algoritmul 1.6.1 (de generare a permutarilor). Fie multimea standard A = {1, 2, . . . , n}. Vomutiliza din nou ”regula urmatorului”.

• Prima permutare, ın ordine lexicografica, este

(p1, p2, . . . , pn) = (1, 2, . . . , n).

• O permutare arbitrara (curenta)

(p1, p2, . . . , pk−1, pk, pk+1, . . . , pn)

are o permutare urmatoare daca si numai daca exista un indice k ∈ {n− 1, . . . , 1} astfel ıncatpk < pk+1. In acest caz, luand cel mai mare indice k cu aceasta proprietate si cel mai mare indicej din {n, . . . , k + 1} astfel ıncat pj > pk (exista, deoarece pk+1 > pk), permutarea urmatoare,ın ordine lexicografica, este

(p1, p2, . . . , pk−1, pj, p′k+1, . . . , p

′j, . . . , p

′n),

unde vectorul (p′k+1, . . . , p′j, . . . , p

′n) este obtinut prin ordonarea crescatoare a elementelor ramase

(pk, pk+1, . . . , pj−1, pj+1, . . . , pn). Cum aceste elemente formeaza vectorul ordonat descrescator

(pk+1, . . . , pj−1, pk, pj+1, . . . , pn),

rezulta ca vectorul (p′k+1, . . . , p′j, . . . , p

′n) este rasturnatul acestuia si deci poate fi obtinut din

acesta, de exemplu, prin interschimbari ıntre termenii situati la egala distanta fata de mijloc.

De exemplu, pentru permutarea curenta

(2, 7, 4, 8, 6, 5, 3, 1)

avem k = 3 (p3 = 4 < p4 = 8), j = 6 (pj = 5 > pk = 4), deci permutarea urmatoare se obtineinterschimband ıntai pk = p3 = 4 cu pj = p6 = 5, apoi rasturnand subvectorul (8, 6, 4, 3, 1) dintrepozitiile k + 1 si n (de exemplu prin interschimbarile 8 ↔ 1, 6 ↔ 3), adica aceasta permutareurmatoare este

(2, 7, 5, 1, 3, 4, 6, 8).

In pseudocod, algoritmul poate fi descris sub formapermutari(n) :{ pentru i = 1, n pi ← i;

afisare(p, n);repeta{ k ← n− 1;

cat timp (pk ≥ pk+1) si (k > 0) k ← k − 1;


daca (k > 0){ j ← n;cat timp (pj ≤ pk) j ← j − 1;pk ↔ pj;

pentru i = 1, �n−k2 pk+i ↔ pn−i+1;

afisare(p, n);}

}cat timp (k > 0);

},unde ↔ reprezinta instructiunea de interschimbare, iar �x reprezinta partea ıntreaga (inferioara) anumarului x ∈ R.

Observatia 1.6.1. Pentru generarea permutarilor unei multimi arbitrare A = {a1, a2, . . . , an} ınlocuimafisarea indicilor (p1, . . . , pn) cu afisarea elementelor corespunzatoare (ap1 , . . . , apn).

1.7 Combinari

Propozitia 1.7.1 (de numarare a combinarilor). Fie m,n ∈ N. Atuncinumarul de cuvinte strict crescatoare de lungime n peste un alfabet (ordonat) cu m litere= numarul de submultimi cu n elemente ale unei multimi cu m elemente

=[m]nn!

def=

(m

n

).

Demonstratie. Fie B = {1, 2, . . . ,m}. Notam multimile din enunt astfel:

C3 = {(c1, c2, . . . , cn)|ci ∈ B ∀ i, ci < ci+1 ∀ i}, S3 = {S|S ⊆ B, card (S) = n}.

Intre aceste multimi definim functiile μ : C3 → S3, ν : S3 → C3 prin:

• ∀ (c1, c2, . . . , cn) ∈ C3, μ(c1, c2, . . . , cn) = {c1, c2, . . . , cn};• ∀ {c1, c2, . . . , cn} ∈ S3 cu c1 < c2 < . . . < cn, ν({c1, c2, . . . , cn}) = (c1, c2, . . . , cn).

Aceste functii sunt inverse una celeilalte, deci sunt bijective si astfel card (C3) = card (S3).Permutand fiecare combinare (c1, c2, . . . , cn) ∈ C3 ın toate cele n! moduri posibile, obtinem fararepetare toate aranjamentele din multimea C1 = {(a1, a2, . . . , an)|ai ∈ B ∀ i, ai = aj ∀i = j}.Deci card (C3)·n! = card (C1). Conform Propozitiei 1.5.1, card (C1) = [m]n, deci card (C3) =

[m]nn!

.

Definitia 1.7.1. Oricare obiecte din cele 2 tipuri numarate ın propozitia anterioara se numesc com-

binari (fara repetitie) de m luate cate n. De asemenea si numarul lor, adica

(m

n

), se numeste

tot combinari (fara repetitie) de m luate cate n si se mai noteaza cu Cnm.

Observatia 1.7.1. Pentru n > m avem

(m

n

)= 0, deoarece [m]n = 0.

Pentru n ≤ m, deoarece [m]n = m(m− 1) . . . (m− n+ 1) =m!

(m− n)!avem

(m

n

)=

m!

n!(m− n)!.

Exemplul 1.7.1. Pentru m = 5 si n = 3, corespondentele din demonstratia anterioara sunt redate ınurmatorul tabel:


(c1, c2, c3) ∈ C3 S ∈ S3

(1,2,3) {1, 2, 3}(1,2,4) {1, 2, 4}(1,2,5) {1, 2, 5}(1,3,4) {1, 3, 4}(1,3,5) {1, 3, 5}(1,4,5) {1, 4, 5}(2,3,4) {2, 3, 4}(2,3,5) {2, 3, 5}(2,4,5) {2, 4, 5}(3,4,5) {3, 4, 5}.

Deci avem

(5

3

)=

[5]33!

=5 · 4 · 31 · 2 · 3 = 10 combinari.

Algoritmul 1.7.1 (de generare a combinarilor). Fie multimea standard B = {1, 2, . . . ,m} sin ≤ m. Vom utiliza din nou ”regula urmatorului”.

• Prima combinare (de m luate cate n), ın ordine lexicografica, este

(c1, c2, . . . , cn) = (1, 2, . . . , n).

• O combinare arbitrara (curenta)

(c1, c2, . . . , ck−1, ck, ck+1, . . . , cn)

are o combinare urmatoare daca si numai daca exista un indice k ∈ {n, . . . , 1} astfel ıncatck < m− n+ k. In acest caz, luand cel mai mare indice k cu aceasta proprietate, combinareaurmatoare, ın ordine lexicografica, este

(c1, c2, . . . , ck−1, ck + 1, ck + 2, . . . , ck + 1 + n− k).

De exemplu, pentru m = 8, n = 6 si combinarea curenta (1, 2, 5, 6, 7, 8) avem k = 2 (c2 = 2 <m− n+ k = 8− 6 + 2), deci combinarea urmatoare este (1, 3, 4, 5, 6, 7).

In pseudocod, algoritmul poate fi descris sub formacombinari(m,n) :{ pentru i = 1, n ci ← i;


cat timp (ck = m− n+ k) si (k > 0) k ← k − 1;daca (k > 0){ ck ← ck + 1;pentru i = k + 1, n ci ← ci−1 + 1;afisare(c, n);}

}cat timp (k > 0);

}.


Algoritmul 1.7.2 (de generare a aranjamentelor). Fie multimea standard B = {1, 2, . . . ,m} sin ≤ m. Conform demonstratiei anterioare, putem genera aranjamentele de m luate cate n pringenerarea combinarilor si permutarea fiecarei combinari. Folosind Algoritmii 1.7.1 si 1.6.1 obtinemurmatoarea descriere ın pseudocod.aranjamente(m,n) :{ pentru i = 1, n ci ← i;

permutari(n);repeta{ k ← n;

cat timp (ck = m− n+ k) si (k > 0) k ← k − 1;daca (k > 0){ ck ← ck + 1;pentru i = k + 1, n ci ← ci−1 + 1;permutari(n);}

}cat timp (k > 0);

}, unde permutari(n) este functia din Algoritmul 1.6.1 ınlocuind functia de afisare cuafisare(c, p, n) :{ pentru i = 1, n afiseaza cpi

;}.

Exemplul 1.7.2. Pentru m = 4 si n = 3, corespondenta aranjamente ↔ permutarile combinarilor dindemonstratia anterioara si din algoritmul anterior este redata ın urmatorul tabel:

Combinare Permutare Aranjament(1,2,3) (1,2,3) (1,2,3)

(1,3,2) (1,3,2)(2,1,3) (2,1,3)(2,3,1) (2,3,1)(3,1,2) (3,1,2)(3,2,1) (3,2,1)

(1,2,4) (1,2,3) (1,2,4)(1,3,2) (1,4,2)(2,1,3) (2,1,4)(2,3,1) (2,4,1)(3,1,2) (4,1,2)(3,2,1) (4,2,1)

Combinare Permutare Aranjament(1,3,4) (1,2,3) (1,3,4)

(1,3,2) (1,4,3)(2,1,3) (3,1,4)(2,3,1) (3,4,1)(3,1,2) (4,1,3)(3,2,1) (4,3,1)

(2,3,4) (1,2,3) (2,3,4)(1,3,2) (2,4,3)(2,1,3) (3,2,4)(2,3,1) (3,4,2)(3,1,2) (4,2,3)(3,2,1) (4,3,2)

Deci avem

(4

3

)· 3! = [4]3 = 4 · 3 · 2 = 24 aranjamente.

Observatia 1.7.2. Analog Observatiei 1.6.1, algoritmii anteriori pot fi adaptati pentru generareacombinarilor si aranjamentelor pentru multimi oarecare.

1.8 Combinari cu repetitie

Propozitia 1.8.1 (de numarare a combinarilor cu repetitie). Fie m,n ∈ N. Atunci numarul de

cuvinte crescatoare de lungime n peste un alfabet (ordonat) cu m litere este egal cu[m]n

n!

def=

((m

n

)).


Demonstratie. Fie B = {1, 2, . . . ,m}, A = {1, 2, . . . ,m+ n− 1},

C4 = {(c1, c2, . . . , cn)|ci ∈ B ∀ i, ci ≤ ci+1 ∀ i}, C3 = {(d1, d2, . . . , dn)|di ∈ A ∀ i, di < di+1 ∀ i}.

Definim corespondentele ρ : C4 → C3, σ : C3 → C4 astfel:

• ρ(c1, c2, c3, . . . , cn) = (c1, c2 + 1, c3 + 2, . . . , cn + n− 1);

• σ(d1, d2, d3, . . . , dn) = (d1, d2 − 1, d3 − 2, . . . , dn − n+ 1).

Acestea sunt functii inverse, deci utilizand Propozitia 1.7.1 avem

card (C4) = card (C3) =

(m+ n− 1

n

)=

[m+ n− 1]nn!

=[m]n

n!=

((mn

)).

Definitia 1.8.1. Cuvintele numarate ın propozitia anterioara se numesc combinari cu repetitie

de m luate cate n. De asemenea si numarul lor, adica

((mn

)), se numeste tot combinari cu

repetitie de m luate cate n.

Exemplul 1.8.1. Pentru m = 3 si n = 4, combinarile cu repetitie sunt, ın ordine lexicografica:

(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 3), (1, 1, 2, 2), (1, 1, 2, 3), (1, 1, 3, 3), (1, 2, 2, 2), (1, 2, 2, 3),

(1, 2, 3, 3), (1, 3, 3, 3), (2, 2, 2, 2), (2, 2, 2, 3), (2, 2, 3, 3), (2, 3, 3, 3), (3, 3, 3, 3).

Deci avem

((34

))=

[3]4

4!=

3 · 4 · 5 · 61 · 2 · 3 · 4 = 15 combinari cu repetitie.

Algoritmul 1.8.1 (de generare a combinarilor cu repetitie). Fie multimea standardB = {1, 2, . . . ,m}.Vom utiliza din nou ”regula urmatorului”.

• Prima combinare cu repetitie (de m luate cate n), ın ordine lexicografica, este

(c1, c2, . . . , cn) = (1, 1, . . . , 1).

• O combinare cu repetitie arbitrara (curenta)

(c1, c2, . . . , ck−1, ck, ck+1, . . . , cn)

are o combinare cu repetitie urmatoare daca si numai daca exista un indice k ∈ {n, . . . , 1} astfelıncat ck < m. In acest caz, luand cel mai mare indice k cu aceasta proprietate, combinarea curepetitie urmatoare, ın ordine lexicografica, este

(c1, c2, . . . , ck−1, ck + 1, ck + 1, . . . , ck + 1).

De exemplu, pentru m = 8, n = 6 si combinarea cu repetitie curenta (2, 4, 5, 8, 8, 8) avem k = 3(c3 = 5 < m = 8) deci combinarea cu repetitie urmatoare este (2, 4, 6, 6, 6, 6).

In pseudocod, algoritmul poate fi descris sub formacombinari cu repetitie(m,n) :{ pentru i = 1, n ci ← 1;


cat timp (ck = m) si (k > 0) k ← k − 1;daca (k > 0)


{ ck ← ck + 1;pentru i = k + 1, n ci ← ck;afisare(c, n);}

}cat timp (k > 0);

}.Observatia 1.8.1. Analog Observatiei 1.6.1, algoritmul anterior poate fi adaptat pentru generareacombinarilor cu repetitie pentru multimi oarecare.

1.9 Permutari cu repetitie

Propozitia 1.9.1 (de numarare a permutarilor cu repetitie). Fiem,n1, n2, . . . , nm ∈ N si n = n1 + n2 + · · · + nm. Atunci numarul de cuvinte de lungime n ce potfi formate peste un alfabet cu m litere astfel ıncat litera numarul i sa apara de exact ni ori pentru

orice i ∈ {1, . . . ,m} este egal cun!

n1!n2! . . . nm!

def=

(n

n1, n2, . . . , nm

).

Demonstratie. Fie B = {1, 2, . . . ,m} si

C5 = {(c1, c2, . . . , cn)|ci ∈ B ∀ i, card ({i|ci = j}) = nj ∀ j}.

Numaram cuvintele din C5 astfel:

• alegem cei n1 indici (din totalul de n) ai literelor egale cu 1, rezulta

(n

n1

)moduri posibile;

• pentru fiecare alegere de mai sus, alegem cei n2 indici (din restul de n−n1) ai literelor egale cu

2, rezulta

(n− n1

n2

)moduri posibile, deci obtinem

(n

n1

)(n− n1

n2

)moduri posibile de alegere

a indicilor literelor 1 si 2;

• . . .• pentru fiecare alegere de mai sus, alegem cei nm indici (din restul de n − n1 − . . . − nm−1) ai

literelor egale cu m; rezulta

(n− n1 − . . .− nm−1

nm

)moduri posibile, deci obtinem

(n

n1

)(n− n1

n2

). . .

(n− n1 − . . .− nm−1

nm

)

moduri posibile de alegere a tuturor indicilor literelor 1, 2, . . . ,m. Astfel

card (C5) =

(n

n1

)(n− n1

n2

). . .

(n− n1 − . . .− nm−1

nm

)=

n!

n1!(n− n1)!· (n− n1)!

n2!(n− n1 − n2)!· . . . ·

· (n− n1 − . . .− nm−1)!

nm!(n− n1 − . . .− nm)!=

n!

n1!n2! . . . nm!(deoarece (n− n1 − . . .− nm)! = 0! = 1).

Definitia 1.9.1. Cuvintele numarate ın propozitia anterioara se numesc permutari cu repetitie

(anagrame) de n luate cate n1, n2, . . . , nm. De asemenea si numarul lor, adica

(n

n1, n2, . . . , nm

),

se numeste tot permutari cu repetitie de n luate cate n1, n2, . . . , nm.


Observatia 1.9.1. Luand n1 = n2 = · · · = nm = 1 obtinem n = m si

(n

1, 1, . . . , 1

)= n!, deci

permutarile (fara repetitie) sunt un caz particular al permutarilor cu repetitie. Pe de alta parte,

luand m = 2 obtinem

(n

n1, n2

)=

n!

n1!n2!, deci si combinarile (fara repetitie) sunt un caz particular

al permutarilor cu repetitie.

Exemplul 1.9.1. Pentru m = 3 si n1 = 2, n2 = n3 = 1, deci n = 4, permutarile cu repetitie sunt, ınordine lexicografica:

(1, 1, 2, 3), (1, 1, 3, 2), (1, 2, 1, 3), (1, 2, 3, 1), (1, 3, 1, 2), (1, 3, 2, 1),

(2, 1, 1, 3), (2, 1, 3, 1), (2, 3, 1, 1), (3, 1, 1, 2), (3, 1, 2, 1), (3, 2, 1, 1).

Deci avem

(4

2, 1, 1

)=

4!

2!1!1!= 12 permutari cu repetitie.

Algoritmul 1.9.1 (de generare a permutarilor cu repetitie). Fie multimea standard B ={1, 2, . . . ,m} si n1, n2, . . . , nm ∈ N, n = n1+n2+ · · ·+nm. Vom utiliza din nou ”regula urmatorului”.

• Prima permutare cu repetitie (de n luate cate n1, n2, . . . , nm), ın ordine lexicografica, este

(p1, p2, . . . , pn) = (1, 1, . . . , 1︸︷︷︸de n1 ori

, 2, 2, . . . , 2︸︷︷︸de n2 ori

, . . . ,m,m, . . . ,m︸︷︷︸de nm ori

).

• Existenta si forma permutarii cu repetitie urmatoare ın ordine lexicografica pentru o permutarecu repetitie curenta arbitrara se determina exact ca la permutarile fara repetitie (Algoritmul1.6.1).

De exemplu, pentru permutarea cu repetitie curenta

(4, 4, 1, 3, 6, 5, 5, 3, 2, 1)

avem k = 4 (p4 = 3 < p5 = 6), j = 7 (pj = 5 > pk = 3), deci permutarea cu repetitie urmatoare seobtine interschimband ıntai pk = p4 = 3 cu pj = p7 = 5, apoi rasturnand subvectorul (6, 5, 3, 3, 2, 1)dintre pozitiile k + 1 si n (de exemplu prin interschimbarile 6 ↔ 1, 5 ↔ 2, 3 ↔ 3), adica aceatapermutare cu repetitie urmatoare este

(4, 4, 1, 5, 1, 2, 3, 3, 5, 6).

In pseudocod, algoritmul poate fi descris sub formapermutari cu repetitie(m,n) :{ n← 0; pentru i = 1,m n← n+ ni;

i← 0;pentru j = 1,m

pentru k = 1, nj

{ i← i+ 1; pi ← j;}

afisare(p, n);repeta{ k ← n− 1;

cat timp (pk ≥ pk+1) si (k > 0) k ← k − 1;daca (k > 0){ j ← n;


cat timp (pj ≤ pk) j ← j − 1;pk ↔ pj;

pentru i = 1, �n−k2 pk+i ↔ pn−i+1;

afisare(p, n);}

}cat timp (k > 0);

},unde functia de afisare este cea din Algoritmul 1.6.1.

Observatia 1.9.2. Analog Observatiei 1.6.1, algoritmul anterior poate fi usor adaptat pentru generareapermutarilor cu repetitie pentru multimi arbitrare.

Tema 2

Partitii

2.1 Compuneri ale unui numar natural

Definitia 2.1.1. Fie n,m ∈ N. O compunere a lui n este o scriere de forma

n = n1 + n2 + · · ·+ nm,

unde n1, n2, . . . , nm ∈ N si conteaza ordinea dintre termenii n1, n2, . . . , nm.

Propozitia 2.1.1 (de numarare a compunerilor unui numar natural). Fie n,m ∈ N. Atunci:

a) numarul de compuneri ale lui n cu m termeni este egal cu

((m

n

));

b) numarul de compuneri ale lui n cu m termeni nenuli este egal cu

(n− 1

m− 1

).

Demonstratie. a) Fie multimile

N = {(n1, n2, . . . , nm)|ni ∈ N ∀ i, n1 + n2 + · · ·+ nm = n},

C4 = {(c1, c2, . . . , cn)|ci ∈ {1, 2, . . . ,m} ∀ i, ci ≤ ci+1 ∀ i}.Definim corespondentele α : N → C4, β : C4 → N prin:

• α(n1, . . . , nm) = (c1, . . . , cn), unde

⎧⎪⎪⎪⎨⎪⎪⎪⎩c1 = · · · = cn1 = 1 (n1 litere),

cn1+1 = · · · = cn1+n2 = 2 (n2 litere),

. . .

cn1+···+nm−1+1 = · · · = cn1+···+nm−1+nm = m (nm litere);

• β(c1, . . . , cn) = (n1, . . . , nm), unde ni = numarul de litere i ale cuvantului (c1, . . . , cn), ∀ i.

Acestea sunt functii inverse, deci conform Propozitiei 1.8.1 avem card (N ) = card (C4) =

((mn

)).

b) Fie multimile N1 = {(n1, n2, . . . , nm)|ni ∈ N� ∀ i, n1 + n2 + · · ·+ nm = n},

N2 = {(t1, t2, . . . , tm)|ti ∈ N ∀ i, t1 + t2 + · · ·+ tm = n−m}.

Definim corespondentele ϕ : N1 → N2, ψ : N2 → N1 prin:

• ∀(n1, . . . , nm) ∈ N1, ϕ(n1, . . . , nm) = (n1 − 1, . . . , nm − 1);

• ∀(t1, . . . , tm) ∈ N2, ψ(t1, . . . , tm) = (t1 + 1, . . . , tm + 1).

17

TEMA 2. PARTITII 18

Acestea sunt functii inverse, deci conform punctului a) avem card (N1) = card (N2) =

((m

n−m))

=

[m]n−m

(n−m)!=m(m+ 1) . . . (n− 1)

(n−m)!=

(n− 1)!

(m− 1)!(n−m)!=

(n− 1m− 1

).

Exemplul 2.1.1. Pentru n = 4 si m = 3 compunerile sunt

4 = 0 + 0 + 4 = 0 + 1 + 3 = 0 + 2 + 2 = 0 + 3 + 1 = 0 + 4 + 0

= 1 + 0 + 3 = 1 + 1 + 2 = 1 + 2 + 1 = 1 + 3 + 0 = 2 + 0 + 2

= 2 + 1 + 1 = 2 + 2 + 0 = 3 + 0 + 1 = 3 + 1 + 0 = 4 + 0 + 0.

Deci avem

((34

))=

3 · 4 · 5 · 61 · 2 · 3 · 4 = 15 compuneri, dintre care

(4− 1

3− 1

)=

(3

2

)= 3 compuneri cu

termenii nenuli.

Algoritmul 2.1.1 (de generare a compunerilor unui numar natural). Fie n,m ∈ N�. Vom

utiliza din nou ”regula urmatorului”.

• Prima compunere a lui n cu m termeni, ın ordine lexicografica, este

n = 0 + 0 + · · ·+ 0 + n.

• O compunere curenta arbitrara

n = t1 + t2 + · · ·+ tk−1 + tk + tk+1 + · · ·+ tm

are o compunere urmatoare daca si numai daca exista un indice k ∈ {m, . . . , 2} astfel ıncattk > 0. In acest caz, luand cel mai mare indice k cu aceasta proprietate, compunerea urmatoare,ın ordine lexicografica, este

n = t1 + t2 + · · ·+ tk−2 + (tk−1 + 1) + 0 + · · ·+ 0 + (tk − 1).

De exemplu, urmatoarea compunere dupa

10 = 2 + 0 + 5 + 3 + 0 + 0

este 10 = 2 + 0 + 6 + 0 + 0 + 2 (deoarece tk = t4 = 3).In pseudocod, algoritmul poate fi descris sub forma

compuneri(n,m) :{ pentru i = 1,m− 1 ti ← 0;

tm ← n;afisare(t,m);repeta{ k ← m;

cat timp (tk = 0) si (k > 1) k ← k − 1;daca (k > 1){ tk−1 ← tk−1 + 1; tm ← tk − 1;

daca (k < m) tk ← 0;afisare(t,m);}

}cat timp (k > 1);

},unde functia de afisare esteafisare(t,m) :{ pentru i = 1,m afiseaza ti;}.

TEMA 2. PARTITII 19

Algoritmul 2.1.2 (de generare a compunerilor cu termeni nenuli). Analog algoritmului anteriorse obtine urmatorul algoritm pentru generarea compunerilor lui n cu m termeni nenuli, m ≤ n.compuneri termeni nenuli(n,m) :{ pentru i = 1,m− 1 ti ← 1;

tm ← n−m+ 1;afisare(t,m);repeta{ k ← m;

cat timp (tk = 1) si (k > 1) k ← k − 1;daca (k > 1){ tk−1 ← tk−1 + 1; tm ← tk − 1;

daca (k < m) tk ← 1;afisare(t,m);}

}cat timp (k > 1);

}.

2.2 Partitii ale unui numar natural

Definitia 2.2.1. O partitie (descompunere) a numarului n ∈ N� este o scriere de forma

n = n1 + n2 + · · ·+ nk,

unde n1, n2, . . . , nk ∈ N� (k ∈ N

�) si nu conteaza ordinea dintre termenii n1, n2, . . . , nk.

Observatia 2.2.1. Deoarece ıntr-o partitie ca mai sus nu conteaza ordinea dintre termeni, putempresupune ca acestia sunt scrisi ın ordine crescatoare.

Definitia 2.2.2. Fie n, k ∈ N�. Notam cu P (n, k) numarul de partitii ale lui n cu k termeni, iar cu

P (n) numarul tuturor partitiilor lui n.

Exemplul 2.2.1. Numarul n = 6 are partitiile

6 = 6 = 1 + 5 = 2 + 4 = 3 + 3 = 1 + 1 + 4 = 1 + 2 + 3 = 2 + 2 + 2

= 1 + 1 + 1 + 3 = 1 + 1 + 2 + 2 = 1 + 1 + 1 + 1 + 2 = 1 + 1 + 1 + 1 + 1 + 1,

deci P (6, 1) = 1, P (6, 2) = 3, P (6, 3) = 3, P (6, 4) = 2, P (6, 5) = 1, P (6, 6) = 1 si P (6) = 11.

Observatia 2.2.2. Avem P (n) = P (n, 1) + P (n, 2) + · · ·+ P (n, n), ∀ n ∈ N�.

Propozitia 2.2.1 (relatia de recurenta a numerelor P (n, k)). Pentru orice n ∈ N� si orice k ∈

{1, . . . , n− 1} avem

P (n, k) = P (n− k, 1) + P (n− k, 2) + · · ·+ P (n− k, k).

Demonstratie. Pentru orice n ∈ N� si orice k ∈ {1, . . . , n− 1} notam

P(n, k) = {(n1, . . . , nk)|ni ∈ N� ∀ i, n1 ≤ · · · ≤ nk, n1 + · · ·+ nk = n}.

Definim corespondentele α : P(n, k)→k⋃

i=1

P(n− k, i) si β :k⋃

i=1

P(n− k, i)→ P(n, k) prin:

TEMA 2. PARTITII 20

• ∀ (n1, . . . , nk) ∈ P(n, k), α(n1, . . . , nk) = (nj − 1, . . . , nk − 1), unde j = min{i|ni ≥ 2, i ∈{1, . . . , k}} (exista j, deoarece k ≤ n− 1);

• ∀ i ∈ {1, . . . , k}, ∀ (n1, . . . , ni) ∈ P(n− k, i), β(n1, . . . , ni) = (1, . . . , 1︸︷︷︸de k−i ori

, n1 + 1, . . . , ni + 1).

Interpretarea acestor functii este urmatoarea: aplicarea functiei α unei partitii a lui n cu k termeniconsta ın micsorarea cu 1 a fiecarui termen si eliminarea termenilor care astfel devin egali cu zero,obtinandu-se o partitie a lui n− k cu cel mult k termeni. Reciproc, aplicarea functiei β unei partitiia lui n − k cu cel mult k termeni consta ın marirea cu 1 a fiecarui termen si adaugarea de termeniegali cu 1 pentru a obtine k termeni, astfel obtinandu-se o partitie a lui n cu k termeni.

Functiile α si β sunt bine definite si inverse una celeilalte, deci card (P(n, k)) = card

(k⋃

i=1

P(n− k, i)).

Cum multimile P(n − k, 1), . . . ,P(n − k, k) sunt evident disjuncte doua cate doua, rezulta ca

P (n, k) =k∑

i=1

P (n− k, i).

Observatia 2.2.3. Relatia de recurenta din Propozitia 2.2.1, ımpreuna cu conditiile initiale evidenteP (n, 1) = P (n, n) = 1, P (n, k) = 0 ∀ k > n permit calculul tuturor numerelor P (n, k), deci si alnumerelor P (n), conform Corolarului 2.2.2. De exemplu, tabelul numerelor P (n, k) si P (n) pentrun ≤ 7 (si k ≤ 7) este:

P (n, k) k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 P (n)n = 1 1 0 0 0 0 0 0 1n = 2 1 1 0 0 0 0 0 2n = 3 1 1 1 0 0 0 0 3n = 4 1 2 1 1 0 0 0 5n = 5 1 2 2 1 1 0 0 7n = 6 1 3 3 2 1 1 0 11n = 7 1 3 4 3 2 1 1 15

Numerele P (n, k) nenule, aflate doar pe diagonala principala si sub aceasta diagonala (adica 1 ≤ k ≤n) formeaza triunghiul numerelor P (n, k).

Algoritmul 2.2.1 (de generare a partitiilor lui n cu k termeni). Fie n, k ∈ N�, k ≤ n. Pentru

generarea ın ordine lexicografica a celor P (n, k) partitii ale lui n cu k termeni

(t1, t2, . . . , tk), n = t1 + t2 + · · ·+ tk, ti ∈ N� ∀i, t1 ≤ t2 ≤ · · · ≤ tk

folosim din nou ”regula urmatorului”.

• Prima partitie este (1, . . . , 1︸︷︷︸de k−1 ori

, n− k + 1).

• O partitie curenta arbitrara

(t1, t2, . . . , tj−1, tj, tj+1, . . . , tk)

are o partitie urmatoare daca si numai daca exista un indice j ∈ {k − 1, . . . , 1} astfel ıncattj ≤ tk − 2. In acest caz, luand cel mai mare indice j cu aceasta proprietate, urmatoareapartitie este

(t1, t2, . . . , tj−1, tj + 1, tj + 1, . . . , tj + 1, n− r),unde r = t1 + t2 + · · ·+ tj−1 + (tj + 1) + (tj + 1) + · · ·+ (tj + 1).

TEMA 2. PARTITII 21

De exemplu, urmatoarea partitie dupa

22 = 1 + 1 + 2 + 4 + 4 + 5 + 5

este22 = 1 + 1 + 3 + 3 + 3 + 3 + 8

(deoarece tj = t3 = 2 ≤ tk − 2 = 5− 2).Descrierea ın pseudocod a algoritmului are forma

generare P(n, k) :{ pentru i = 1, k − 1 ti ← 1; tk ← n− k + 1;

afisare(t, k);repeta{ j ← k − 1;

cat timp (tj > tk − 2) si (j > 0) j ← j − 1;daca (j > 0){ tj ← tj + 1;

pentru i = j + 1, k − 1 ti ← tj;r ← 0;pentru i = 1, k − 1 r ← r + ti;tk ← n− r;afisare(t, k);

}}cat timp (j > 0);

},unde functia de afisare este aceeasi ca ın Algoritmul 2.1.1.

2.3 Partitii ale unei multimi finite

Definitia 2.3.1. O partitie a unei multimi nevide A este o scriere de forma

A = A1 ∪ A2 ∪ · · · ∪ Ak,

unde submultimile (partile, clasele) A1, A2, . . . , Ak (k ∈ N�) sunt nevide si disjuncte doua cate doua,

si nu conteaza ordinea dintre aceste submultimi. Consideram ca singura partitie a multimii vide estepartitia cu zero submultimi.

Definitia 2.3.2. Fie n, k ∈ N.a) Numarul lui Stirling de speta a doua, notat cu S(n, k), reprezinta numarul de partitii aleunei multimi cu n elemente ın k parti.b) Numarul lui Bell, notat cu Bn, reprezinta numarul tuturor partitiilor unei multimi cu n ele-mente.

Exemplul 2.3.1. Multimea A = {a, b, c} are partitiile

A = {a, b, c} = {a, b} ∪ {c} = {a, c} ∪ {b} = {a} ∪ {b, c} = {a} ∪ {b} ∪ {c},

deci S(3, 1) = 1, S(3, 2) = 3, S(3, 3) = 1 si B3 = 5.

Observatia 2.3.1. Evident, avem B0 = 1 si Bn = S(n, 1) + S(n, 2) + · · ·+ S(n, n), ∀ n ∈ N�.

TEMA 2. PARTITII 22

Propozitia 2.3.1 (relatia de recurenta a numerelor S(n, k)).

S(n, k) = S(n− 1, k − 1) + kS(n− 1, k), ∀ n, k ∈ N�.

Demonstratie. Notam

S(n, k) = {{A1, . . . , Ak}|Ai = ∅ ∀ i, Ai ∩ Aj = ∅ ∀ i = j, A = A1 ∪ · · · ∪ Ak},

pentru orice n, k ∈ N�. Definim corespondentele

α : S(n, k)→ S(n− 1, k − 1) ∪ {1, . . . , k} × S(n− 1, k),

β : S(n− 1, k − 1) ∪ {1, . . . , k} × S(n− 1, k)→ S(n, k),

prin:

• ∀ {A1, . . . , Ak} ∈ S(n, k), α({A1, . . . , Ak}) =

=

{ {A1, . . . , Ak} \ {Ai}, daca n ∈ Ai si Ai = {n},(i, {A1, . . . , Ai \ {n}, . . . , Ak}), daca n ∈ Ai si Ai = {n};

• ∀ {A1, . . . , Ak−1} ∈ S(n− 1, k − 1), β({A1, . . . , Ak−1}) = {A1, . . . , Ak−1, {n}},• ∀ (i, {A1, . . . , Ak}) ∈ {1, . . . , k} × S(n− 1, k), β(i, {A1, . . . , Ak}) = {A1, . . . , Ai ∪ {n}, . . . , Ak}.

Interpretarea acestor definitii este urmatoarea: aplicarea functiei α unei partitii a multimii {1, . . . , n}ın k parti consta ın eliminarea elementului n, astfel obtinandu-se o partitie a multimii {1, . . . , n− 1}ın k − 1 sau ın k parti, dupa cum n este sau nu singur ıntr-o parte. Reciproc, aplicarea functiei βconsta ın adaugarea elementului n, fie singur ıntr-o parte, fie la oricare din cele k parti.

Functiile α si β sunt bine definite si inverse una celeilalte, deci

card (S(n, k)) = card (S(n− 1, k − 1) ∪ {1, . . . , k} × S(n− 1, k)) ,

adica S(n, k) = S(n− 1, k − 1) + kS(n− 1, k).

Observatia 2.3.2. Relatia de recurenta de mai sus ımpreuna cu conditiile initiale evidente S(0, 0) = 1,S(0, k) = 0 ∀ k ≥ 1, S(n, 0) = 0 ∀n ≥ 1 permit calculul tuturor numerelor S(n, k), deci si al numerelorBn, conform Corolarului 2.3.1. De exemplu, tabelul numerelor S(n, k) si Bn pentru n ≤ 6 (si k ≤ 6)este:

S(n, k) k = 0 k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 Bn

n = 0 1 0 0 0 0 0 0 1n = 1 0 1 0 0 0 0 0 1n = 2 0 1 1 0 0 0 0 2n = 3 0 1 3 1 0 0 0 5n = 4 0 1 7 6 1 0 0 15n = 5 0 1 15 25 10 1 0 52n = 6 0 1 31 90 65 15 1 203

Numerele S(n, k) nenule, aflate doar pe diagonala principala si sub aceasta diagonala (1 ≤ k ≤ n)formeaza triunghiul numerelor lui Stirling de speta a doua.

TEMA 2. PARTITII 23

Algoritmul 2.3.1 (de generare a partitiilor unei multimi ıntr-un numar fixat de parti). FieA = {1, 2, . . . , n} si 1 ≤ k ≤ n. Pentru scrierea unei partitii

A = A1 ∪ · · · ∪ Ak

vom folosi conventia ca ın fiecare parte Ai elementele sunt ordonate crescator, iar ordinea dintrepartile A1, . . . , Ak este data de ordinea dintre cele mai mici elemente ale acestor multimi.

De exemplu, partitia{1, 2, 3, 4, 5} = {3, 2} ∪ {5} ∪ {4, 1}

va fi scrisa sub forma{1, 2, 3, 4, 5} = {1, 4} ∪ {2, 3} ∪ {5}. (2.3.1)

Pentru reprezentarea unei partitii A = A1 ∪ · · · ∪Ak scrise conform conventiei de mai sus, vom folosivectorul caracteristic v = (v1, . . . , vn), unde

vi = j daca i ∈ Aj, ∀ i ∈ {1, 2, . . . , n}, ∀ j ∈ {1, 2, . . . , k}.

De exemplu, vectorul caracteristic al partitiei (2.3.1) este v = (1, 2, 2, 1, 3).Cu aceasta reprezentare, conform demonstratiei relatiei de recurenta a numerelor S(n, k) (Propozitia

2.3.1) obtinem un algoritm recursiv de generare a partitiilor multimii {1, 2, . . . , n} ın k parti. In pseu-docod, acest algoritm poate fi descris sub formagenerare S(n, k) :{ daca (k = 1) //conditie initiala

{ pentru i = 1, n vi ← 1; //partitia cu o parteafisare(v);}

altfel{ daca (k = n) //conditie initiala

{ pentru i = 1, n vi ← i; //partitia cu n partiafisare(v);

}altfel //relatia de recurenta{ vn ← k; generare S(n− 1, k − 1); //n singur ın parte

pentru i = 1, k //n nesingur ın parte{ vn ← i; generare S(n− 1, k);}}

}},unde functia de afisare, ce transforma vectorul caracteristic v ın partitia corespunzatoare, esteafisare(v) :{ pentru j = 1, k //afisam partea Aj

{ afiseaza ”{”;pentru i = 1, n daca (vi = j) afiseaza i;afiseaza ”}”;

}}.

Tema 3

Grafuri

Grafurile sunt modele matematice cu o gama larga de aplicatii. Aceasta aplicabilitate a condusla dezvoltarea accelerata a teoriei grafurilor, atat din punct de vedere al rezultatelor teoretice catsi al algoritmicii, grafurile impunandu-se drept modele de baza ın informatica, ın special ın teoriastructurilor de date si a analizei algoritmilor.

3.1 Definitii generale

Definitia 3.1.1. Un graf neorientat (graf, pseudograf, graf general) este o pereche G = (V,E)unde:

• V este o multime finita si nevida, elementele sale numindu-se nodurile (varfurile, punctele)grafului G;

• E este o colectie (multime multipla, multiset) finita de perechi neordonate, posibil egale, denoduri, elementele sale numindu-se muchiile (legaturile directe, liniile) grafului G.

Observatia 3.1.1. Intr-o pereche neordonata, notata [x, y], nu conteaza ordinea dintre elemente, adica[x, y] = [y, x].

Definitia 3.1.2. Un graf orientat (digraf, pseudodigraf) este o pereche G = (V,E) unde:

• V este o multime finita si nevida, elementele sale numindu-se varfurile (nodurile, punctele)grafului G;

• E este o colectie (multime multipla, multiset) finita de perechi ordonate de varfuri, elementelesale numindu-se arcele (legaturile directe ale) grafului G.

Observatia 3.1.2. Intr-o pereche ordonata, notata (x, y), conteaza ordinea dintre elemente, adica(x, y) = (y, x) pentru x = y.

Definitia 3.1.3. Numarul de noduri ale unui graf (neorientat sau orientat) se numeste ordinulgrafului, iar numarul de muchii sau arce se numeste dimensiunea grafului.

Definitia 3.1.4. a) Daca e = [x, y] este o muchie a unui graf neorientat, atunci nodurile x si yse numesc extremitatile muchiei e si spunem ca muchia e este incidenta cu nodurile x siy.

b) Daca e = (x, y) este un arc al unui graf orientat, atunci nodul x se numeste extremitateainitiala iar nodul y se numeste extremitatea finala a arcului e si spunem ca arcul e esteincident cu x spre exterior si cu y spre interior.

24

TEMA 3. GRAFURI 25

c) O bucla a unui graf (neorientat sau orientat) este o muchie sau un arc avand extremitatileegale (adica o muchie de forma [x, x], respectiv un arc de forma (x, x)).

d) Doua noduri x si y ale unui graf (neorientat sau orientat) se numesc adiacente (vecine) dacaexista o muchie sau un arc incident cu x si cu y (adica o muchie de forma [x, y], respectiv unarc de forma (x, y) sau de forma (y, x)).

Definitia 3.1.5. Daca ın colectia (multimea multipla) de muchii sau arce a unui graf (neorientatsau orientat) exista doua sau mai multe elemente egale (si aflate pe pozitii diferite), atunci acestease numesc muchii sau arce multiple.

Definitia 3.1.6. Un graf (neorientat sau orientat) fara bucle se numeste multigraf (neorientat,respectiv orientat).

Definitia 3.1.7. Un graf (neorientat sau orientat) se numeste simplu (sau strict) daca nu continenici bucle si nici muchii sau arce multiple.

Observatia 3.1.3. a) Un graf neorientat simplu este o pereche G = (V,E), unde V este o multimefinita si nevida (de elemente numite noduri) iar E ⊆ P2(V ) este o multime finita (de elemente numitemuchii), unde

P2(V ) = {{x, y}|x, y ∈ V, x = y}(multimea tuturor submultimilor cu doua elemente ale lui V ).b) Un graf orientat simplu este o pereche G = (V,E), unde V este o multime finita si nevida (deelemente numite noduri) iar E ⊆ V × V \ {(x, x)|x ∈ V } este o multime finita (de elemente numitearce).

Definitia 3.1.8. Fie G = (V,E) un graf (orientat sau neorientat). O reprezentare grafica a luiG se obtine reprezentand nodurile sale prin puncte distincte (ın plan sau pe o alta suprafata data),iar muchiile [x, y] sau arcele (x, y) prin segmente (de curba continua) distincte neorientate, respectivorientate, de la punctul ce reprezinta nodul x pana la punctul ce reprezinta nodul y.

Exemplul 3.1.1. Graful neorientatG = (V,E), cu V = {1, 2, 3, 4, 5, 6} si E = {e1, e2, e3, e4, e5, e6, e7, e8, e9},unde e1 = [1, 2], e2 = [1, 4], e3 = [2, 2], e4 = [2, 5], e5 = [3, 6], e6 = [3, 6], e7 = [4, 5], e8 = [4, 5], e9 =[4, 5] (E este o multime multipla!) are reprezentarea grafica din Figura 3.1.1.

9e

1

4

2

5

1e

4e

3e

8e

7e

5e

6e2

e

3

6

Figura 3.1.1:

1 2

3 4

5

Figura 3.1.2:

Acest graf are ordinul 6 si dimensiunea 9. El contine bucla e3, muchiile multiple e5, e6 si muchiilemultiple e7, e8, e9, deci nu este nici multigraf, nici simplu. Nodurile 1 si 2 sunt adiacente, iar nodurile1 si 5 nu sunt adiacente.

Exemplul 3.1.2. Graful orientat G = (V,E), cu V = {1, 2, 3, 4, 5} si

E = {(1, 2), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (5, 4)}este un graf simplu avand reprezentarea grafica din Figura 3.1.2. Arcul (3, 1) are extremitatea initiala3 si extremitatea finala 1.

TEMA 3. GRAFURI 26

Definitia 3.1.9. Fie G1 = (V1, E1) si G2 = (V2, E2) doua grafuri (ambele orientate sau ambeleneorientate).

a) Spunem ca G1 este un subgraf al lui G2 si notam G1 ⊆ G2 daca V1 ⊆ V2 si E1 ⊆ E2.

b) Spunem ca G1 este un graf partial al lui G2 daca V1 = V2 si E1 ⊆ E2.

Definitia 3.1.10. Fie G = (V,E) un graf (neorientat sau orientat) si U ⊆ V o submultime nevidade noduri. Subgraful indus (generat) de U ın G este subgraful G[U ] = (U, F ), unde F estecolectia tuturor muchiilor sau arcelor din E ce au ambele extremitati ın U .

Definitia 3.1.11. Fie G = (V,E) un graf (orientat sau neorientat) si F ⊆ E o colectie de muchiisau de arce.

a) Subgraful indus (generat) de F ın G este subgraful G[F ] = (U, F ), unde U este multimeatuturor nodurilor din V ce sunt extremitati pentru cel putin o muchie sau un arc din F .

b) Graful partial indus (generat) de F ın G este graful partial (V, F ).

Exemplul 3.1.3. Pentru graful neorientat din Exemplul 3.1.1, subgraful generat de submultimea denoduri {1, 3, 4, 5} are reprezentarea din Figura 3.1.3.

1

4 5

3

Figura 3.1.3:

Pentru graful orientat din Exemplul 3.1.2, subgraful generat de submultimea de arce {(2, 3), (5, 4)}are reprezentarea din Figura 3.1.4, iar graful partial generat de aceeasi submultime de arce arereprezentarea din Figura 3.1.5.

5

4

2

3

Figura 3.1.4:

15

4

2

3

Figura 3.1.5:

3.2 Reprezentarea grafurilor

In continuare descriem cateva forme de reprezentare (memorare) a grafurilor ın informatica. Dintreaceste forme, cea mai utilizata este matricea de adiacenta.

Definitia 3.2.1. Fie G = (V,E) un graf (neorientat sau orientat) unde V = {v1, . . . , vn} si E ={e1, . . . , em}. Matricea de adiacenta asociata grafului G este matricea A = (aij)i,j=1,n definitaprin

aij = numarul de muchii sau de arce ek ∈ E de la nodul vi la nodul vj (adica muchii de formaek = [vi, vj], respectiv arce de forma ek = (vi, vj)), ∀i, j ∈ {1, . . . , n}.

TEMA 3. GRAFURI 27

Observatia 3.2.1. a) Daca graful neorientat G = (V,E) este simplu, atunci

aij =

{1, daca vi si vj sunt adiacente (adica [vi, vj] ∈ E),0, ın caz contrar.

b) Daca graful orientat G = (V,E) este simplu, atunci

aij =

{1, daca (vi, vj) ∈ E,0, ın caz contrar.

Exemplul 3.2.1. Matricea de adiacenta asociata grafului neorientat din Exemplul 3.1.1 este

A =

⎛⎜⎜⎜⎜⎜⎜⎝

0 1 0 1 0 01 1 0 0 1 00 0 0 0 0 21 0 0 0 3 00 1 0 3 0 00 0 2 0 0 0

⎞⎟⎟⎟⎟⎟⎟⎠,

iar matricea de adiacenta asociata grafului orientat din Exemplul 3.1.2 este

A =

⎛⎜⎜⎜⎜⎝

0 1 0 0 00 0 1 1 11 1 0 0 00 0 0 0 00 0 0 1 0

⎞⎟⎟⎟⎟⎠ .

Observatia 3.2.2. Evident, orice graf neorientat are matricea de adiacenta simetrica (aij = aji ∀ i, j).Definitia 3.2.2. Fie G = (V,E) un graf, unde V = {v1, . . . , vn} si E = {e1, . . . , em}, E = ∅.

a) Daca G este neorientat, atunci matricea de incidenta asociata grafului G este matriceaB = (bij) i = 1, n

j = 1,m

definita prin

bij =

⎧⎨⎩

0, daca ej nu este incidenta cu vi,1, daca ej nu este bucla si este incidenta cu vi,2, daca ej este o bucla incidenta cu vi,

∀ i ∈ {1, . . . , n}, ∀ j ∈ {1, . . . ,m}.b) Daca G este orientat si fara bucle, atunci matricea de incidenta asociata grafului G este

matricea B = (bij) i = 1, nj = 1,m

definita prin

bij =

⎧⎨⎩

0, daca ej nu este incidenta cu vi,1, daca ej este incidenta cu vi spre exterior,−1, daca ej este incidenta cu vi spre interior,

∀ i ∈ {1, . . . , n}, ∀ j ∈ {1, . . . ,m}.

TEMA 3. GRAFURI 28

Exemplul 3.2.2. Matricea de incidenta a grafului neorientat din Exemplul 3.1.1 este

B =

⎛⎜⎜⎜⎜⎜⎜⎝

1 1 0 0 0 0 0 0 01 0 2 1 0 0 0 0 00 0 0 0 1 1 0 0 00 1 0 0 0 0 1 1 10 0 0 1 0 0 1 1 10 0 0 0 1 1 0 0 0

⎞⎟⎟⎟⎟⎟⎟⎠,

iar matricea de incidenta a grafului orientat din Exemplul 3.1.2 este

B =

⎛⎜⎜⎜⎜⎝

1 0 0 0 −1 0 0−1 1 1 1 0 −1 00 −1 0 0 1 1 00 0 −1 0 0 0 −10 0 0 −1 0 0 1

⎞⎟⎟⎟⎟⎠ .

Observatia 3.2.3. Fie G = (V,E) un graf (neorientat sau orientat), unde V = {v1, . . . , vn} si E ={e1, . . . , em}, E = ∅. O alta reprezentare a grafului G este matricea T ce retine ın fiecare coloanaextremitatile unei muchii sau arc, adica T = (tkj) k = 1, 2

j = 1,m

definita prin t1j = x, t2j = y, unde

ej = [x, y] (pentru muchii) sau ej = (x, y) (pentru arce), ∀ j ∈ {1, . . . ,m}. Pentru graful dinExemplul 3.1.1 matricea T este

T =

(1 1 2 2 3 3 4 4 42 4 2 5 6 6 5 5 5

),

iar pentru graful din Exemplul 3.1.2 matricea T este

T =

(1 2 2 2 3 3 52 3 4 5 1 2 4

).

Observatia 3.2.4. O alta forma frecvent utilizata ın reprezentarea grafurilor simple este data delistele de adiacenta (memorate static sau dinamic). Lista de adiacenta a unui nod x este formatadin toate nodurile y pentru care exista muchie sau arc de la x la y (y se numeste succesor directal lui x). Pentru graful orientat din Exemplul 3.1.2, listele de adiacenta sunt

L(1) = {2}, L(2) = {3, 4, 5}, L(3) = {1, 2}, L(4) = ∅, L(5) = {4},

unde L(i) reprezinta lista de adiacenta a nodului i. Pentru grafurile orientate simple, deseori sememoreaza si listele de predecesori directi. Lista de predecesori directi a unui nod x este formatadin toate nodurile y pentru care exista arc de la y la x (y se numeste predecesor direct al lui x).Pentru graful din Exemplul 3.1.2, aceste liste sunt

L(1) = {3}, L(2) = {1, 3}, L(3) = {2}, L(4) = {2, 5}, L(5) = {2}.

Evident, pentru grafurile neorientate notiunile de succesor direct si predecesor direct coincid, fiind sisinonime cu notiunile de vecin sau adiacent.

Observatia 3.2.5. Alegerea uneia sau alteia dintre formele de reprezentare a grafurilor descrise maisus depinde de eficienta si de usurinta implementarii operatiilor necesare de prelucrare a acestorforme, deci de tipul problemei modelate prin grafuri si de algoritmul de rezolvare utilizat.

TEMA 3. GRAFURI 29

3.3 Grade

Definitia 3.3.1. Fie G = (V,E) un graf si x ∈ V un nod arbitrar fixat.

a) Daca G este neorientat, atunci gradul lui x, notat dG(x) = d(x), este definit prin

d(x) = a(x) + 2 · b(x),

unde a(x) reprezinta numarul de muchii e ∈ E ce nu sunt bucle si sunt incidente cu x, iar b(x)este numarul de bucle e ∈ E ce sunt incidente cu x.

b) Daca G este orientat, atunci:

• gradul de iesire (semigradul exterior) al lui x, notat d+G(x) = d+(x), reprezinta

numarul de arce e ∈ E incidente cu x spre exterior;

• gradul de intrare (semigradul interior) al lui x, notat d−G(x) = d−(x), reprezintanumarul de arce e ∈ E incidente cu x spre interior;

• gradul (total al) lui x, notat dG(x) = d(x), este

d(x) = d+(x) + d−(x).

Exemplul 3.3.1. Pentru graful neorientat din Exemplul 3.1.1, gradele nodurilor sunt: d(1) = 2,d(2) = 4, d(3) = 2, d(4) = 4, d(5) = 4, d(6) = 2.

Pentru graful orientat din Exemplul 3.1.2, gradele nodurilor sunt:

d+(1) = 1, d−(1) = 1, d(1) = 2,

d+(2) = 3, d−(2) = 2, d(2) = 5,

d+(3) = 2, d−(3) = 1, d(3) = 3,

d+(4) = 0, d−(4) = 2, d(4) = 2,

d+(5) = 1, d−(5) = 1, d(5) = 2.

Propozitia 3.3.1. Fie G = (V,E) un graf, V = {v1, . . . , vn}, si fie A = (aij)i,j=1,n matricea deadiacenta a grafului G.

a) Daca G este neorientat, atunci d(vi) = aii +n∑

j=1

aij, ∀ i ∈ {1, . . . , n}.

b) Daca G este orientat, atunci d+(vi) =n∑

j=1

aij, d−(vi) =

n∑j=1

aji, ∀ i ∈ {1, . . . , n}.

Observatia 3.3.1. Daca graful G este simplu, atunci aii = 0 ∀ i si egalitatea de la punctul a) al

propozitiei anterioare devine d(vi) =n∑

j=1

aij.

Propozitia 3.3.2. Fie G = (V,E) un graf avand dimensiunea m. Atunci∑x∈V

d(x) = 2m.

In plus, daca G este orientat atunci∑x∈V

d+(x) =∑x∈V

d−(x) = m.

Definitia 3.3.2. Fie G = (V,E) un graf. Un nod x ∈ V cu dG(x) = 0 se numeste nod izolat, iarun nod y ∈ V cu dG(y) = 1 se numeste nod terminal.

TEMA 3. GRAFURI 30

3.4 Conexitate

Definitia 3.4.1. Fie G = (V,E) un graf.

a) Un lant ın graful G este o succesiune alternanta

[v1, e1, v2, e2, . . . , vk, ek, vk+1],

unde v1, v2, . . . , vk+1 ∈ V (noduri), e1, e2, . . . , ek ∈ E (muchii sau arce), k ∈ N, cu proprietateaca pentru orice i ∈ {1, . . . , k} ei este o muchie sau un arc avand extremitatile vi si vi+1 (adicaei = [vi, vi+1] pentru un graf neorientat, respectiv ei = (vi, vi+1) sau ei = (vi+1, vi) pentru ungraf orientat). Nodurile v1 si vk+1 se numesc extremitatile lantului, iar nodurile v2, . . . , vk

se numesc noduri intermediare. Numarul k de muchii sau arce (nu neaparat distincte) alelantului se numeste lungimea lantului.

b) Un lant se numeste ınchis daca are extremitatile egale, respectiv deschis ın caz contrar.

c) Un lant se numeste simplu daca muchiile sau arcele sale sunt diferite doua cate doua (con-siderand diferite si muchiile sau arcele multiple aflate pe pozitii diferite ın E).

d) Un lant deschis se numeste elementar daca nodurile sale sunt diferite doua cate doua. Unlant ınchis se numeste elementar daca este simplu si, cu exceptia extremitatilor, nodurilesale sunt diferite doua cate doua.

e) Un ciclu este un lant ınchis si simplu de lungime nenula (adica cu cel putin o muchie sau unarc).

f) Un drum este un lant [v1, e1, v2, e2, . . . , vk, ek, vk+1] cu proprietatea ca pentru orice i ∈ {1, . . . , k}muchia sau arcul ei are extremitatea initiala vi si extremitatea finala vi+1 (adica ei = (vi, vi+1)pentru graf orientat).

Un astfel de drum se noteaza si cu

(v1, e1, v2, e2, . . . , vk, ek, vk+1),

nodurile v1 si vk+1 numindu-se extremitatea initiala, respectiv extremitatea finala a dru-mului.

g) Un circuit este un drum ınchis si simplu de lungime nenula (adica un drum ce este si ciclu).

Observatia 3.4.1. Pentru grafurile neorientate notiunile de lant si de drum coincid; deci si notiunilede ciclu si de circuit coincid.

Observatia 3.4.2. Orice lant elementar este si simplu.

Observatia 3.4.3. Pentru grafurile neorientate sau orientate simple orice lant [v1, e1, v2, e2, . . . , vk, ek, vk+1]sau drum (v1, e1, v2, e2, . . . , vk, ek, vk+1) este bine determinat de nodurile sale (deoarece muchia sauarcul ei nu poate fi decat singura muchie sau singurul arc de la vi la vi+1, ∀ i), deci poate fi notat,pe scurt, doar prin nodurile succesive

[v1, v2, . . . , vk, vk+1], respectiv (v1, v2, . . . , vk, vk+1).

Exemplul 3.4.1. Pentru graful neorientat din Exemplul 3.1.1,

[1, e2, 4, e9, 5, e4, 2, e1, 1, e2, 4]

TEMA 3. GRAFURI 31

este un lant (drum) deschis, nesimplu (contine de doua ori e2), neelementar (contine de doua ori 1),de lungime 5.

In acelasi graf, [1, e1, 2, e3, 2, e4, 5, e7, 4, e9, 5, e8, 4, e2, 1] este un ciclu (circuit) simplu si neelementar(contine de doua ori 2), de lungime 7.

Pentru graful orientat simplu din Exemplul 3.1.2, [3, 1, 2, 4, 5] este un lant ce nu este drum(deoarece (4, 5) nu este arc, ci (5, 4)), iar (3, 1, 2, 5, 4) este un drum (si lant) deschis elementar(si simplu) de lungime 4. In acelasi graf, (1, 2, 3, 1) este un circuit (si ciclu) elementar, iar [2, 5, 4, 2]este un ciclu elementar ce nu este circuit (deoarece (4, 2) nu este arc, ci (2, 4)).

Definitia 3.4.2. a) Un graf (neorientat sau orientat) se numeste conex daca pentru orice douanoduri distincte x, y exista cel putin un lant de la x la y.

b) Un graf orientat se numeste tare-conex daca pentru orice doua noduri distincte x, y exista celputin un drum de la x la y (deci, schimband ordinea lui x si y, exista cel putin un drum si dela y la x).

Observatia 3.4.4. Orice graf tare-conex este si conex (deoarece orice drum este si lant). Orice grafcu un singur nod verifica definitia anterioara, deci este si conex si tare-conex.

Observatia 3.4.5. Deoarece pentru orice nod x exista lantul [x] si drumul (x) de lungimi zero, rezultaca ın definitia anterioara putem renunta la conditiile ca nodurile x si y sa fie distincte.

De asemenea, deoarece prin eliminarea tuturor portiunilor dintre noduri egale dintr-un lant saudrum se obtine un lant sau un drum elementar avand aceleasi extremitati, rezulta ca ın definitiaanterioara putem ınlocui termenii de ”lant” si ”drum” cu ”lant elementar”, respectiv ”drum elemen-tar”.

Exemplul 3.4.2. Graful neorientat din Exemplul 3.1.1 nu este conex, deoarece nu exista lanturi ıntrenodurile 1 si 3. Graful orientat din Exemplul 3.1.2 este conex, dar nu este tare-conex, deoarece nuexista drum de la nodul 4 la nodul 1 (desi exista drum de la nodul 1 la nodul 4!).

Definitia 3.4.3. a) O componenta conexa a unui graf (orientat sau neorientat) G = (V,E)este un subgraf G[U ] generat de o submultime U ⊆ V de noduri cu proprietatea ca G[U ] esteconex si maximal cu aceasta proprietate (ın raport cu incluziunea), adica pentru orice nodx ∈ V \ U subgraful G[U ∪ {x}] nu mai este conex.

b) O componenta tare-conexa a unui graf orientat G = (V,E) este un subgraf G[U ] generatde o multime U ⊆ V de noduri cu proprietatea ca G[U ] este tare-conex si maximal cu aceastaproprietate (ın raport cu incluziunea), adica pentru orice noduri x1, x2, . . . , xp ∈ V \U subgrafulG[U ∪ {x1, x2, . . . , xp}] nu mai este tare-conex.

Observatia 3.4.6. Un graf este conex daca si numai daca are o singura componenta conexa. Un graforientat este tare-conex daca si numai daca are o singura componenta tare-conexa. Numarul decomponente tare-conexe ale unui graf orientat este mai mare sau egal decat numarul de componenteconexe ale acelui graf, deoarece orice componenta tare-conexa este inclusa ıntr-o componenta conexa(conform definitiei anterioare si Observatiei 3.4.4).

Observatia 3.4.7. Orice nod izolat x genereaza o componenta conexa si o componenta tare-conexa,ambele avand forma G[{x}] = ({x}, ∅).Propozitia 3.4.1. a) Fie G[V1], . . . , G[Vk] componentele conexe (diferite) ale unui graf G = (V,E).

Atunci {V1, . . . , Vk} este o partitie a multimii V (adica Vi = ∅ ∀ i, Vi ∩ Vj = ∅ ∀ i = j,V1 ∪ · · · ∪ Vk = V ).

b) Fie G[V ′1 ], . . . , G[V ′

r ] componentele tare-conexe (diferite) ale unui graf orientat G = (V,E).Atunci {V ′

1 , . . . , V′r} este de asemenea o partitie a multimii V .

TEMA 3. GRAFURI 32

Exemplul 3.4.3. Componentele conexe ale grafului neorientat din Exemplul 3.1.1 sunt generate desubmultimile de noduri V1 = {1, 2, 4, 5} si V2 = {3, 6}, deci acel graf are 2 componente conexe.Componentele tare-conexe ale grafului orientat din Exemplul 3.1.2 sunt generate de submultimile denoduri V1 = {1, 2, 3}, V2 = {4} si V3 = {5}, deci acel graf are 3 componente tare-conexe.

Observatia 3.4.8. Submultimile de muchii sau arce ale componentelor conexe ale unui graf formeaza deasemenea o partitie a multimii de muchii sau arce a grafului (deoarece pentru orice muchie e = [x, y]sau arc e = (x, y) nodurile x si y se afla ıntr-o aceeasi componenta conexa si aceasta componentava contine si pe e). Afirmatia nu mai este valabila pentru componentele tare-conexe. De exemplu,pentru graful din Exemplul 3.1.2 arcul (5, 4) nu apartine nici-unei componente tare-conexe.

Algoritmi pentru testarea conexitatii si tare-conexitatii unui graf, precum si pentru determinareacomponentelor conexe si tare-conexe ale unui graf, vor fi prezentati ın sectiunile urmatoare.

Definitia 3.4.4. a) Un arbore este un graf conex si fara cicluri.

b) O padure este un graf fara cicluri.

c) Un arbore partial al unui graf G = (V,E) este un graf partial al lui G ce este arbore (adicaun arbore T = (V, F ) cu F ⊆ E).

Observatia 3.4.9. Arborii si padurile sunt grafuri simple (deoarece orice bucla este un ciclu si oricedoua muchii sau arce multiple formeaza un ciclu).

Observatia 3.4.10. Componentele conexe ale unei paduri sunt arbori.

Exemplul 3.4.4. Graful neorientat din Exemplul 3.1.1 nu este padure (deoarece are cicluri), deci niciarbore. Graful sau partial reprezentat ın Figura 3.4.1 este o padure (avand doua componente conexearbori). Graful orientat din Exemplul 3.1.2 nu este arbore (deoarece are cicluri). Doi arbori partialiai sai sunt reprezentati ın Figura 3.4.2.

2e

1

4

2

5

1e

4e

5e

3

6

Figura 3.4.1:1 1

2 2

3 34 4

5 5

Figura 3.4.2:

Proprietatile teoretice si algoritmice de baza ale arborilor vor fi evidentiate ın capitolul urmator.

3.5 Parcurgerea grafurilor

Prin parcurgerea unui graf se ıntelege o metoda sistematica de vizitare succesiva a nodurilor sale (ınvederea prelucrarii informatiilor atasate ın structura de date modelata prin graful dat).

TEMA 3. GRAFURI 33

Definitia 3.5.1. Fie G = (V,E) un graf si x ∈ V un nod arbitrar fixat. Parcurgerea ın adancime(DF, ”depth first”) a grafului G pornind din nodul x, numit si radacina a acestei parcurgeri, constaın:

• se viziteza nodul x, acesta devine nod curent;

• daca nodul curent vi are succesori directi (adica noduri vj pentru care exista muchie sau arc dela vi la vj) nevizitati, atunci se viziteaza primul astfel de nod vj; nodul vj devine nod curent sise continua procedeul de parcurgere pornind din acest nod;

• daca nodul curent vj nu mai are succesori directi nevizitati, atunci se revine la nodul predecesordirect vi (cel din care a fost vizitat); nodul vi redevine nod curent si se continua procedeul deparcurgere pornind din acest nod;

• daca nodul curent nu mai are nici succesori directi nevizitati, nici predecesor direct (deci estechiar radacina x), atunci parcurgerea se ıncheie.

Observatia 3.5.1. Pentru parcurgerea DF, considerand cate o muchie sau un arc de la fiecare nodcurent vi la primul sau succesor direct nevizitat vj (care va deveni urmatorul nod curent) se obtineun arbore, numit arbore DF.

Exemplul 3.5.1. Pentru graful din Exemplul 3.1.2, parcurgerea ın adancime pornind din nodul 2 este

DF (2) : 2, 3, 1, 4, 5

(considerand ca ordinea dintre succesorii directi ai fiecarui nod este ordinea crescatoare). ArboreleDF corespunzator acestei parcurgeri este reprezentat ın Figura 3.5.1. Pentru acelasi graf, parcurgerea

1

3

2

4 5

Figura 3.5.1:

1

3

2

4 5

Figura 3.5.2:

DF pornind din nodul 3 esteDF (3) : 3, 1, 2, 4, 5,

iar arborele DF corespunzator este reprezentat ın Figura 3.5.2.

Prezentam ın continuare doi algoritmi, unul recursiv si altul nerecursiv, pentru implementareaparcurgerii ın adancime.

TEMA 3. GRAFURI 34

Algoritmul 3.5.1 (parcurgerea DF, recursiv). Fie graful G = (V,E) avand multimea de noduriV = {1, . . . , n} si matricea de adiacenta A = (aij)i,j=1,n. Fie x ∈ V un nod arbitrar fixat. Pentruimplementarea parcurgerii DF (x) vom utiliza un vector V IZ avand semnificatia

V IZ[i] =

{1, daca nodul i a fost vizitat,0, ın caz contrar,

∀ i ∈ {1, . . . , n}.

Pentru memorarea arborelui DF (x) vom utiliza un vector TATA avand semnificatia

TATA[i] =

{0, daca i = x (radacina),predecesorul direct al lui i, daca i = x,

pentru orice nod i din parcurgereaDF . Descrierea ın pseudocod a algoritmului recursiv de parcurgereın adancime pornind din nodul x are formaDF recursiv(x) :{ viziteaza(x); //se viziteaza x, de exemplu se afiseaza x

V IZ[x]← 1; //x a fost vizitat

pentru y = 1, n

{ daca (axy ≥ 1) si (V IZ[y] = 0) //y este primul succesor direct// nevizitat al lui x

{ TATA[y]← x;DF recursiv(y);//se continua parcurgerea DF din nodul y}

}}.

Programul C++ corespunzator, cu citirea grafului dintr-un fisier (avand pe prima linie numerelen de noduri si m de muchii sau arce ale grafului si pe liniile urmatoare perechile de noduri ce formeazaaceste muchii sau arce) si afisarea parcurgerii DF (x) si a vectorului TATA (ce memoreaza arboreleDF (x)) este:

#include<iostream.h> //parcurgerea DF a unui graf, recursiv#include<conio.h>#include<fstream.h>#define nmax 50 // nr. maxim de noduriint n,m,A[nmax][nmax],VIZ[nmax],TATA[nmax];void citire_graf() // citirea grafului din fisierul "graf2.dat"{ int i,j,k;

ifstream f("graf2.dat");f>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=n;j++) A[i][j]=0;for(k=1;k<=m;k++){ f>>i>>j;A[i][j]++;

// if (j!=i) A[j][i]++; // doar pt. grafuri NEORIENTATE}f.close();

}void viziteaza(int x) // vizitarea nodului x{ cout<<x<<" ";}void DF_recursiv(int x) // parcurgerea DF pornind din nodul x{ int y;

viziteaza(x);VIZ[x]=1;for(y=1;y<=n;y++)

TEMA 3. GRAFURI 35

if ((A[x][y]>=1)&&(VIZ[y]==0)){ TATA[y]=x;

DF_recursiv(y);}

}void main(){ int x,i;

clrscr();citire_graf();for(i=1;i<=n;i++){ VIZ[i]=0; TATA[i]=0;}cout<<"Nodul de pornire: x=";cin>>x;cout<<"Parcurgerea DF: ";DF_recursiv(x);cout<<"\nArborele DF este dat de vectorul TATA: ";for (i=1;i<=n;i++) cout<<TATA[i]<<" ";getch();

}

Exemplul 3.5.2. Pentru graful din Exemplul 3.1.2, fisierul de intrare ”graf2.dat” folosit la citireagrafului ın programul anterior contine datele:5 7 //5 noduri si 7 arce1 2 //arcul (1, 2)2 3 //arcul (2, 3)2 4 //arcul (2, 4)2 5 //arcul (2, 5)3 1 //arcul (3, 1)3 2 //arcul (3, 2)5 4 //arcul (5, 4).

Algoritmul 3.5.2 (parcurgerea DF, nerecursiv). Fie din nou G = (V,E) un graf avand multimeade noduri V = {1, . . . , n} si matricea de adiacenta A = (aij)i,j=1,n. Fie x ∈ V un nod arbitrarfixat. Pentru implementarea nerecursiva a parcurgerii DF (x) vom utiliza vectorii V IZ si TATA cuaceleasi semnificatii ca ın algoritmul anterior, un vector URM cu semnificatia

URM [i] = urmatorul succesor direct al nodului i,

si o structura de tip stiva S, memorata ca un vector, ce contine nodurile vizitate si ın curs deprelucrare, adica de vizitare a tuturor succesorilor.

Descrierea ın pseudocod a algoritmului are formaDF(x) :{ viziteaza(x);//se viziteaza x, de exemplu se afiseaza x

V IZ[x]← 1;//x a fost vizitatTATA[x]← 0;varf ← 1; S[varf ]← x;//nodul x se introduce ın varful stiveicat timp (varf > 0)//stiva este nevida{ i← S[varf ];//i este nodul din varful stivei

j ← URM [i] + 1;//j va fi urmatorul succesor direct nevizitat//al lui i, daca exista

cat timp (aij = 0) si (j ≤ n) j ← j + 1;daca (j > n) //nodul i nu mai are succesori directi nevizitati{ varf ← varf − 1; //s-a ıncheiat prelucrarea lui i si

//ıl eliminam din stiva}

TEMA 3. GRAFURI 36

altfel{ URM [i]← j;//j este urmatorul succesor direct al lui i

daca (V IZ[j] = 0) //j nu a fost vizitat{ viziteaza(j);//se viziteaza j

V IZ[j]← 1;//j a fost vizitatTATA[j]← i;varf ← varf + 1;S[varf ]← j; //se introduce j ın varful stivei

}}

}//stiva este vida, nu mai exista noduri neprelucrate,//parcurgerea este ıncheiata.

}.Observatia 3.5.2. DacaG = (V,E) este un graf neorientat, atunci pentru orice nod x ∈ V componentaconexa a nodului x este (indusa de) chiar multimea nodurilor vizitate prin parcurgerea DF (x).

Pe baza acestei observatii obtinem urmatorul algoritm.

Algoritmul 3.5.3 (determinarea componentelor conexe). Fie din nou G = (V,E) un graf neori-entat, V = {1, . . . , n} si fie A = (aij)i,j=1,n matricea de adiacenta a grafului G. Pentru determinareacomponentelor conexe ale grafului G vom utiliza un vector CC cu semnificatia

CC[i] = numarul componentei conexe ın care se afla nodul i,

∀ i ∈ {1, . . . , n} si o variabila nrc ce reprezinta numarul de componente conexe. Evident, graful Geste conex daca si numai daca valoarea finala a variabilei nrc este egala cu 1.

Descrierea ın pseudocod a algoritmului are formacomponente conexe :{ nrc← 0;

pentru i = 1, n CC[i]← 0;pentru i = 1, n{ daca (CC[i] = 0) //nodul i nu a fost vizitat

{ nrc← nrc + 1; //nodurile din parcurgerea DF (i)// vor forma o noua componenta conexa

DF (i);}

}},unde functia DF(i) este cea din Algoritmul 3.5.1 sau cea din Algoritmul 3.5.2, adaugand instructiuneaCC[i]← nrc ın functia viziteaza(i).

Observatia 3.5.3. Algoritmul anterior poate fi utilizat si pentru determinarea componentelor conexeale unui graf orientat, ınlocuind conditia ”axy ≥ 1” din functia DF recursiv(x) cu ”axy ≥ 1 sauayx ≥ 1”, respectiv conditia ”aij = 0” din functia DF(x) cu ”aij = 0 si aji = 0” (deoarece ındeterminarea componentelor conexe nu se tine cont de orientarea arcelor).

Observatia 3.5.4. Daca G = (V,E) este un graf orientat, atunci pentru orice nod x ∈ V componentatare-conexa a nodului x este (indusa de) multimea nodurilor y vizitate prin parcurgerea DF (x) agrafului G cu proprietatea ca y este vizitat si ın parcurgerea DF (x) a grafului

G = (V,E), unde E = {(j, i)|(i, j) ∈ E},

numit transpusul (simetricul) lui G. Evident, orice drum (y, v1, . . . , vk, x) ın graful G corespundedrumului (x, vk, . . . , v1, y) ın graful G, deci x si y sunt ın aceeasi componenta tare-conexa a lui G

TEMA 3. GRAFURI 37

daca si numai daca exista un drum de la x la y ın G si un drum de la x la y ın G, adica y este vizitatprin parcurgerea DF (x) atat ın G cat si ın G.

Matricea de adiacenta a grafului G este transpusa matricei de adiacenta a grafului G, deci pentruparcurgerea DF (x) a grafului G putem utiliza tot matricea de adiacenta A a grafului dat G, ınlocuindconditia ”aij = 0” cu ”aji = 0”, iar conditia ”axy ≥ 1” cu ”ayx ≥ 1” ın functiile DF(x), respectivDF recursiv(x). Astfel, algoritmul DF poate fi utilizat si pentru determinarea componentelortare-conexe, deci si pentru verificarea tare-conexitatii grafului.

Definitia 3.5.2. Fie G = (V,E) un graf si x ∈ V un nod arbitrar fixat. Parcurgerea ın latime(BF,”breadth first”, parcurgerea pe nivele) a grafului G pornind din nodul x, numit si radacinaa acestei parcurgeri, consta ın:

• se viziteza nodul x, considerat nod de nivelul zero;

• se viziteaza apoi succesorii directi nevizitati ai acestuia (diferiti de x), considerati noduri denivelul 1;

• se viziteaza apoi, pe rand, succesorii directi nevizitati ai acestora, considerati noduri de nivelul2;s.a.m.d.;

• parcurgerea se ıncheie cand nici-un nod de pe un nivel nu mai are succesori directi nevizitati.

Observatia 3.5.5. Analog parcurgerii DF, considerand cate o muchie sau un arc de la fiecare nodcurent v al parcurgerii BF la fiecare din nodurile nevizitate (de pe urmatorul nivel) pentru care veste predecesorul direct, se obtine un arbore, numit arbore BF.

Exemplul 3.5.3. Pentru graful din Exemplul 3.1.2, parcurgerea ın latime pornind din nodul 2 este

BF (2) : 2, 3, 4, 5, 1

(considerand din nou ordinea dintre succesorii directi ai fiecarui nod ca fiind ordinea crescatoare).Arborele BF corespunzator acestei parcurgeri este reprezentat ın Figura 3.5.3. Pentru acelasi graf,

1

3

2

4 5

Figura 3.5.3:

1

3

2

4 5

Figura 3.5.4:

parcurgerea BF pornind din nodul 3 este

BF (3) : 3, 1, 2, 4, 5,

iar arborele BF corespunzator este reprezentat ın Figura 3.5.4.

TEMA 3. GRAFURI 38

Algoritmul 3.5.4 (parcurgerea BF). Fie graful G = (V,E) avand multimea de noduri V ={1, . . . , n} si matricea de adiacenta A = (aij)i,j=1,n. Fie x ∈ V un nod arbitrar fixat. Pentru imple-mentarea parcurgerii BF (x) vom utiliza vectorii V IZ, TATA, URM si S avand aceleasi semnificatiica la parcurgerea DF (x) (Algoritmul 3.5.2), cu deosebirea ca vectorul S al nodurilor vizitate si ıncurs de prelucrare este organizat si utilizat acum ca o structura de tip coada.

Aceasta fiind singura modificare fata de Algoritmul 3.5.2, obtinem urmatoarea descriere ın pseu-docod a algoritmului de parcurgere ın latimeBF(x) :{ viziteaza(x);

V IZ[x]← 1; TATA[x]← 0;varf ← 1; coada← 1;//nodurile se adauga la S pe pozitia ”coada”

//si se elimina de pe pozitia ”varf ”S[coada]← x;cat timp (varf ≤ coada){ i← S[varf ];

j ← URM [i] + 1;cat timp (aij = 0) si (j ≤ n) j ← j + 1;daca (j > n){ varf ← varf + 1;}altfel{ URM [i]← j;

daca (V IZ[j] = 0){ viziteaza (j);

V IZ[j]← 1; TATA[j]← i;coada← coada + 1; S[coada]← j;

}}

}}.Observatia 3.5.6. Observatiile 3.5.2, 3.5.3 si 3.5.4 si algoritmii corespunzatori raman valabile dacaınlocuim parcurgerea DF cu parcurgerea BF.

3.6 Algoritmul Roy-Warshall

Definitia 3.6.1. Fie G = (V,E) un graf (neorientat sau orientat), unde V = {v1, . . . , vn}. Ma-tricea drumurilor asociata grafului G este matricea D = (dij)i,j=1,n definita prin

dij =

{1, daca ∃ μ = (vi, . . . , vj) drum cu l(μ) > 0,0, ın caz contrar,

unde l(μ) reprezinta lungimea drumului μ.

Exemplul 3.6.1. Matricea drumurilor asociata grafului neorientat din Exemplul 3.1.1 este

D =

⎛⎜⎜⎜⎜⎜⎜⎝

1 1 0 1 1 01 1 0 1 1 00 0 1 0 0 11 1 0 1 1 01 1 0 1 1 00 0 1 0 0 1

⎞⎟⎟⎟⎟⎟⎟⎠,

TEMA 3. GRAFURI 39

iar matricea drumurilor asociata grafului orientat din Exemplul 3.1.2 este

D =

⎛⎜⎜⎜⎜⎝

1 1 1 1 11 1 1 1 11 1 1 1 10 0 0 0 00 0 0 1 0

⎞⎟⎟⎟⎟⎠ .

Observatia 3.6.1. Evident, orice graf neorientat are matricea drumurilor simetrica.

Observatia 3.6.2. Conform Observatiei 3.4.5, pentru i = j putem ınlocui termenul de ”drum” cu”drum elementar” ın definitia matricei drumurilor.

Urmatorul algoritm determina matricea drumurilor unui graf pornind de la matricea de adiacenta.

Algoritmul 3.6.1 (Roy-Warshall). Fie G = (V,E) un graf simplu cu V = {v1, . . . , vn} si fie A =(aij)i,j=1,n matricea sa de adiacenta (avand toate elementele 0 sau 1). Se calculeaza matricele

D(k) = (d(k)ij )i,j=1,n, k ∈ {0, 1, . . . , n},

definite prin

D(0) = A, (3.6.1)

d(k)ij = d

(k−1)ij ∨ d(k−1)

ik d(k−1)kj , ∀k, i, j ∈ {1, . . . , n}, (3.6.2)

unde 0 ∨ 0 = 0, 0 ∨ 1 = 1 ∨ 0 = 1 ∨ 1 = 1 (operatia de disjunctie, ”sau”).

Teorema 3.6.1 (de corectitudine a Algoritmului Roy-Warshall). In contextul AlgoritmuluiRoy-Warshall, ultima matrice calculata este chiar matricea drumurilor asociata grafului G, adica

D(n) = D.

Demonstratie. Vom demonstra prin inductie dupa k ∈ {0, 1, . . . , n} ca pentru orice i, j ∈ {1, . . . , n}avem

d(k)ij =

{1, daca ∃ μ = (vi, . . . , vj) drum cu l(μ) > 0 si I(μ) ⊆ {v1, . . . , vk},0, ın caz contrar,

(3.6.3)

unde l(μ) reprezinta lungimea drumului μ, I(μ) reprezinta multimea nodurilor intermediare ale dru-mului μ, iar {v1, . . . , vk} reprezinta multimea {vi|, 1 ≤ i ≤ k}, deci pentru k = 0 aceasta multimeeste ∅.

Pentru k = 0 avem

d(0)ij = aij (conform (3.6.1)) si aij =

{1, daca (vi, vj) ∈ E,0, ın caz contrar

(din definitia matricei de adiacenta), iar (vi, vj) ∈ E daca si numai daca ∃ μ = (vi, . . . , vj) drum cul(μ) > 0 si I(μ) = ∅, deci obtinem egalitatea (3.6.3).

Presupunem acum egalitatea (3.6.3) adevarata pentru k− 1 (1 ≤ k ≤ n) si o demonstram pentruk. Folosind (3.6.2), definitia operatiilor ∨ si · si ipoteza de inductie avem echivalentele:

d(k)ij = 1⇔ d

(k−1)ij = 1 sau d

(k−1)ik = d

(k−1)kj = 1⇔ ∃ μ = (vi, . . . , vj) drum cu

l(μ) > 0, I(μ) ⊆ {v1, . . . , vk−1} sau ∃ μ1 = (vi, . . . , vk), μ2 = (vk, . . . , vj)

drumuri cu l(μ1), l(μ2) > 0, I(μ1), I(μ2) ⊆ {v1, . . . , vk−1}⇔ ∃ μ = (vi, . . . , vj) cu l(μ) > 0, I(μ) ⊆ {v1, . . . , vk}, vk ∈ I(μ) sau

∃ μ′ = (vi, . . . , vk, . . . , vj) cu l(μ′) > 0, I(μ′) ⊆ {v1, . . . , vk}, vk ∈ I(μ′)

TEMA 3. GRAFURI 40

(μ′ se obtine parcurgand ıntai μ1 apoi μ2 si, reciproc, μ1, μ2 sunt portiunile din μ′ dintre vi si primaaparitie a lui vk ın I(μ′), respectiv dintre ultima aparitie a lui vk ın I(μ′) si vj)

⇔ ∃ μ = (vi, . . . , vj) drum cu l(μ) > 0 si I(μ) ⊆ {v1, . . . , vk}.Demonstratia prin inductie a egalitatii (3.6.3) este astfel ıncheiata.

Pentru k = n conditia I(μ) ⊆ {v1, . . . , vn} poate fi eliminata, fiind ıntotdeauna adevarata, decidin (3.6.3) si Definitia 3.6.1 obtinem ca

d(n)ij = dij, ∀ i, j ∈ {1, . . . , n},

adica egalitatea din enunt.

Observatia 3.6.3. Pentru n fixat, Algoritmul Roy-Warshall necesita 2n3 operatii (cate o operatie · si∨ pentru fiecare (k, i, j) ∈ {1, . . . , n}×{1, . . . , n}×{1, . . . , n}), deci acest algoritm are complexitateaO(n3). Reamintim notatia utilizata, pentru orice functie f : N→ N,

O(f) = {g|g : N→ N, ∃r > 0, ∃n0 ∈ N a.ı. g(n) ≤ rf(n) ∀n ≥ n0}.Observatia 3.6.4. Algoritmul Roy-Warshall ramane evident valabil si pentru grafuri nesimple, cumodificarea

d(0)ij =

{1, daca aij > 0,0, daca aij = 0,

∀ i, j ∈ {1, . . . , n}.

Exemplul 3.6.2. Pentru graful din Exemplul 3.1.2, prin aplicarea Algoritmului Roy-Warshall obtinemmatricele:

D(0) = A =

⎛⎜⎜⎜⎜⎝

0 1 0 0 00 0 1 1 11 1 0 0 00 0 0 0 00 0 0 1 0

⎞⎟⎟⎟⎟⎠ (matricea de adiacenta);

D(1) =

⎛⎜⎜⎜⎜⎝

0 1 0 0 00 0 1 1 11 1 0 0 00 0 0 0 00 0 0 1 0

⎞⎟⎟⎟⎟⎠ ; D(2) =

⎛⎜⎜⎜⎜⎝

0 1 1 1 10 0 1 1 11 1 1 1 10 0 0 0 00 0 0 1 0

⎞⎟⎟⎟⎟⎠

(deoarece, de exemplu, d(2)13 = d

(1)13 ∨ d(1)

12 d(1)23 = 0 ∨ 1 · 1 = 0 ∨ 1 = 1);

D(3) =

⎛⎜⎜⎜⎜⎝

1 1 1 1 11 1 1 1 11 1 1 1 10 0 0 0 00 0 0 1 0

⎞⎟⎟⎟⎟⎠ ; D(4) =

⎛⎜⎜⎜⎜⎝

1 1 1 1 11 1 1 1 11 1 1 1 10 0 0 0 00 0 0 1 0

⎞⎟⎟⎟⎟⎠ ;

D(5) =

⎛⎜⎜⎜⎜⎝

1 1 1 1 11 1 1 1 11 1 1 1 10 0 0 0 00 0 0 1 0

⎞⎟⎟⎟⎟⎠ = D (matricea drumurilor).

TEMA 3. GRAFURI 41

Observatia 3.6.5. Conform ecuatiilor (3.6.3), Algoritmul Roy-Warshall este un algoritm specificmetodei programarii dinamice.

Conform ecuatiilor (3.6.2) si definitiei operatiei ∨ avem d(k)ik = d

(k−1)ik si d

(k)kj = d

(k−1)kj , ∀ k, i, j ∈

{1, . . . , n}, deci pentru implementarea algoritmului putem utiliza o singura matriceD. Astfel obtinemurmatoarea descriere ın pseudocod a algoritmuluiRoy Warshall :{ pentru i = 1, n

pentru j = 1, n dij ← aij;//initializarepentru k = 1, n

pentru i = 1, npentru j = 1, n dij ← dij ∨ dikdkj;

},iar pentru grafuri oarecare (simple sau nesimple) initializarea are formapentru i = 1, n

pentru j = 1, ndaca (aij > 0) dij ← 1;altfel dij ← 0.

Observatia 3.6.6. Daca G = (V,E) este un graf neorientat si V = {1, . . . , n}, atunci pentru orice nodx ∈ V componenta conexa a nodului x este (indusa de) multimea

{x} ∪ {y|y ∈ V \ {x}, dxy = 1}.

Astfel Algoritmul Roy-Warshall poate fi utilizat pentru determinarea componentelor conexe sipentru verificarea conexitatii grafului.

Algoritmul 3.6.2 (determinarea componentelor tare-conexe). Daca G = (V,E) este un graforientat si V = {1, . . . , n}, atunci pentru orice nod x ∈ V componenta tare-conexa a nodului x este(indusa de) multimea

{x} ∪ {y|y ∈ V \ {x}, dxy = dyx = 1},deci Algoritmul Roy-Warshall poate fi utilizat pentru determinarea componentelor tare-conexe sipentru verificarea tare-conexitatii grafului.

Descrierea ın pseudocod a algoritmului are formacomponente tare conexe :{ nrc← 0;//numarul de componente tare-conexe

pentru i = 1, n CC[i]← 0;//vectorul componentelor tare-conexeRoy Warshall;pentru i = 1, n{ daca (CC[i] = 0){ nrc← nrc + 1; CC[i]← nrc;

pentru j = i + 1, ndaca (CC[j] = 0) si (dij = 1) si (dji = 1)

CC[j]← nrc;}

}},unde CC[i] reprezinta numarul componentei tare-conexe ın care se afla nodul i, ∀ i ∈ {1, . . . , n}.

Tema 4

Arbori

4.1 Numarul ciclomatic

Propozitia 4.1.1 (Dirac). Fie G = (V,E) un graf neorientat simplu si

δ(G) = minx∈V

d(x)

gradul minim al nodurilor din G.

a) G contine un lant deschis elementar μ astfel ıncat

l(μ) ≥ δ(G),

unde l(μ) reprezinta lungimea lantului μ.

b) Daca δ(G) ≥ 2, atunci G contine un ciclu elementar C astfel ıncat

l(C) ≥ δ(G) + 1.

Definitia 4.1.1. Un graf se numeste par daca toate nodurile sale au gradele pare.

Propozitia 4.1.2 (Veblen). Fie G = (V,E) un graf cu E = ∅. Atunci graful G este par daca sinumai daca exista C1, . . . , Ck cicluri elementare muchie-disjuncte (doua cate doua) astfel ıncat

E = E(C1) ∪ · · · ∪ E(Ck) (k ∈ N�), (4.1.1)

unde E(Ci) reprezinta multimea muchiilor ciclului Ci, ∀ i ∈ {1, . . . , k}.Propozitia 4.1.3. Fie G = (V,E) un graf. Atunci (P(E),Δ, ·) este un spatiu vectorial peste corpulfinit cu doua elemente (Z2,+, ·), unde

P(E) = {F |F ⊆ E}, AΔB = (A \B) ∪ (B \ A) (diferenta simetrica),

0 · A = ∅, 1 · A = A, ∀ A ∈ P(E).

Definitia 4.1.2. Spatiul vectorial (P(E),Δ, ·) din propozitia anterioara se numeste spatiul muchi-ilor grafului G.

Propozitia 4.1.4. Fie G = (V,E) un graf si

C(E) = {F ⊆ E|(V, F ) = graf par}.Atunci C(E) este un subspatiu vectorial al spatiului muchiilor grafului G.

42

TEMA 4. ARBORI 43

Propozitia 4.1.5. Fie G = (V,E) un graf si

C0(E) = {F ⊆ E|∃ C = ciclu elementar ın G a.ı. F = E(C)},unde E(C) este multimea muchiilor ciclului C. Atunci subspatiul vectorial al spatiului muchiilor luiG generat de C0(E) este subspatiul C(E) din propozitia anterioara.

Demonstratie. Evident, C0(E) ⊆ C(E). Conform Propozitiei 4.1.2, pentru orice F ∈ C(E), F = ∅,exista F1, . . . , Fk ∈ C0(E) disjuncte doua cate doua a.ı. F = F1 ∪ · · · ∪ Fk, deci F = F1Δ . . .ΔFk =1 · F1Δ . . .Δ1 · Fk.

Definitia 4.1.3. Subspatiul C(E) din Propozitia 4.1.4 se numeste spatiul ciclurilor grafului G.Dimensiunea acestui subspatiu se numeste numarul ciclomatic al grafului G si se noteaza cu ν(G).

Propozitia 4.1.6 (Listing). Fie G = (V,E) o padure cu n noduri, m muchii si k componenteconexe. Atunci

m− n+ k = 0.

Demonstratie. Demonstram egalitatea din enunt prin inductie dupa m.Pentru m = 0 rezulta ca toate nodurile sunt izolate, deci fiecare nod formeaza o componenta

conexa, adica k = n si egalitatea m− n+ k = 0 este verificata.Presupunem adevarata egalitatea din enunt pentru orice padure cu m − 1 muchii (m ≥ 1) si o

demonstram pentru padurea G cu m muchii. Fie

G′ = (V,E ′), unde E ′ = E \ {e}, cu e ∈ E, e = [x, y].

Evident G′ este o padure cu n noduri, m − 1 muchii si k + 1 componente conexe (deoarececomponentele conexe din G ce nu contin x si y raman componente conexe si ın G′, iar componentaconexa din G ce contine x si y se partitioneaza ın doua componente conexe ın G′, una continand pex si cealalta pe y). Aplicand ipoteza de inductie pentru graful G′ avem

(m− 1)− n+ (k + 1) = 0, deci m− n+ k = 0.

Corolarul 4.1.1. Orice arbore cu n noduri are m = n− 1 muchii.

Demonstratie. Se aplica propozitia anterioara, cu k = 1.

Propozitia 4.1.7. Un graf este conex daca si numai daca are arbori partiali.

Demonstratie. Daca graful G = (V,E) are un arbore partial T , atunci pentru orice x, y ∈ V , x = y,exista un lant [x, . . . , y] ın T (fiind conex), deci si ın G, si astfel G este conex.

Reciproc, demonstram ca orice graf conex G = (V,E) are arbori partiali prin inductie dupanumarul p de cicluri elementare ale lui G.

Pentru p = 0 rezulta ca ınsusi G este un arbore, deci arbore partial ın G.Presupunem adevarata afirmatia pentru orice graf conex cu cel mult p − 1 cicluri elementare

(p ≥ 1) si o demonstram pentru graful conex G = (V,E) cu p cicluri elementare. Fie e = [x, y] omuchie a lui G aflata pe un ciclu elementar C si fie G′ = (V,E \ {e}). Graful G′ ramane conex (ıntrex si y exista lantul [x, v1, . . . , vk, y], unde [x, v1, . . . , vk, y, x] este ciclul C) si are cel mult p− 1 ciclurielementare. Conform ipotezei de inductie, exista un arbore partial T ın G′, deci si ın G.

Propozitia 4.1.8. Fie G = (V,E) un graf, T = (V, F ) un arbore partial al lui G si e ∈ E \ F .Atunci graful partial

T + e = (V, F ∪ {e})are un unic ciclu elementar si acest ciclu contine muchia e.

TEMA 4. ARBORI 44

Demonstratie. Fie e = [x, y]. T fiind arbore partial, exista un lant elementar μ = [x, v1, . . . , vk, y] ınT , deci μ+ e = [x, v1, . . . , vk, y, x] este un ciclu elementar ın T + e.

Unicitatea acestui ciclu rezulta din unicitatea lantului elementar μ (daca ar exista doua lanturielementare distincte μ1 = [x, . . . , y] si μ2 = [x, . . . , y] ın T , portiunile lor muchie-disjuncte ar produceun ciclu, contradictie cu T = arbore).

Teorema 4.1.1 (Teorema numarului ciclomatic). Orice graf G = (V,E) cu n noduri, m muchiisi k componente conexe are numarul ciclomatic

ν(G) = m− n+ k.

Demonstratie. Demonstram egalitatea din enunt ın doua etape.Etapa 1) Presupunem ca graful G este conex, deci k = 1. Fie T = (V, F ) un arbore partial al lui

G (exista, conform Propozitiei 4.1.7). Conform Corolarului 4.1.1, card (F ) = n− 1. Fie

E \ F = {e1, . . . , em−n+1}.

Pentru orice i ∈ {1, . . . ,m− n+ 1}, fie Ci multimea muchiilor ciclului elementar unic din T + ei

(conform Propozitiei 4.1.8). Atunci

B = {C1, . . . , Cm−n+1}

este o baza a spatiului ciclurilor C(E) (numita baza de cicluri a grafului G). Rezulta ca

ν(G) = card (B) = m− n+ 1 = m− n+ k.

Etapa 2) Fie acum G un graf oarecare si G1, . . . , Gk componentele sale conexe. Fie ni si mi

numerele de noduri, respectiv muchii ale componentei Gi. Evident, n = n1 + · · · + nk si m =m1 + · · ·+mk.

Deoarece subspatiile ciclurilor componentelor G1, . . . , Gk sunt liniar independente, avem

ν(G) = ν(G1) + · · ·+ ν(Gk).

Dar, conform etapei 1), ν(Gi) = mi − ni + 1 ∀ i ∈ {1, . . . , k}, si astfel prin adunare rezulta caν(G) = m− n+ k.

Observatia 4.1.1. Demonstratia teoremei anterioare este constructiva, indicand urmatorul algoritmde determinare a unei baze de cicluri pentru graful G:

• se determina componentele conexe G1, . . . , Gk;

• pentru fiecare componenta Gi, se determina un arbore partial T (de exemplu arborele DF sauBF ) si ciclurile elementare C1, . . . , Cmi−ni+1 din grafurile T + ei, pentru fiecare muchie ei dinGi ce nu apartine lui T ;

• ciclurile astfel determinate formeaza ımpreuna o baza de cicluri pentru graful G.

Exemplul 4.1.1. Fie graful G reprezentat ın Figura 4.1.1.Numarul sau ciclomatic este ν(G) = m− n+ k = 9− 7 + 1 = 3.Considerand arborele partial T reprezentat ın Figura 4.1.2 si aplicand algoritmul din observatia

anterioara se obtine baza de cicluri {C1, C2, C3} unde C1 = {[1, 4], [4, 2], [2, 1]}, C2 = {[4, 5], [5, 2], [2, 4]}si C3 = {[5, 6], [6, 3], [3, 2], [2, 5]}.

TEMA 4. ARBORI 45

1 2 3

7

4 5 6

Figura 4.1.1:

1 2 3

7

4 5 6

Figura 4.1.2:

4.2 Teorema de caracterizare a arborilor

Teorema 4.2.1 (de caracterizare a arborilor). Fie G = (V,E) un graf cu n noduri. Urmatoareleafirmatii sunt echivalente:

1) G este un arbore (adica este conex si fara cicluri);

2) G este fara cicluri si are m = n− 1 muchii;

3) G este conex si are m = n− 1 muchii;

4) G este fara cicluri si maximal cu aceasta proprietate, adica daca se adauga o muchie ıntreoricare doua noduri graful obtinut contine cicluri;

5) G este conex si minimal cu aceasta proprietate, adica daca se elimina o muchie oarecare grafulobtinut devine neconex;

6) ıntre oricare doua noduri ale lui G exista un unic lant elementar.

Demonstratie. 1)⇒ 2) Fie G un arbore, adica si conex si fara cicluri. Deci 0 = ν(G) = m− n+ 1 siastfel m = n− 1.

2) ⇒ 3) Fie G fara cicluri si cu m = n − 1 muchii. Avem 0 = ν(G) = n − 1 − n + k, unde kreprezinta numarul de componente conexe ale lui G, deci k = 1, adica G este conex.

3)⇒ 4) Fie G conex si cu m = n− 1 muchii. Avem ν(G) = n− 1− n + 1 = 0, deci G este faracicluri. Fie G + e = (V,E ∪ {e}), e ∈ E. Graful G + e ramane conex si are n noduri si m + 1 = nmuchii. Astfel ν(G+ e) = n− n+ 1 = 1, adica G+ e contine un ciclu (elementar).

4)⇒ 5) Fie G fara cicluri maximal. Daca G nu ar fi conex, atunci adaugand o muchie ıntre douanoduri x si y din componente conexe diferite ale lui G s-ar obtine un graf fara cicluri (deoarece nuexista lant ıntre x si y ın G), contradictie cu ipoteza. Deci G este conex.

Fie G − e = (V,E \ {e}), e ∈ E, e = [x, y]. Daca graful G − e ar fi conex, atunci ar exista unlant elementar [x, v1, . . . , vk, y] ın G− e si astfel [x, v1, . . . , vk, y, x] ar fi un ciclu ın G, contradictie cuipoteza. Deci G− e este neconex.

5)⇒ 6) Fie G conex minimal. Fie x, y ∈ V .Daca x = y, rezulta ca exista un lant elementar [x, . . . , y].Daca x = y exista de asemenea lantul elementar [x] de lungime zero.Daca ıntre nodurile x si y ar exista doua lanturi elementare distincte μ1 = [x, v1, . . . , vi, y] si

μ2 = [x,w1, . . . , wj, y], atunci notand cu e muchia [x, v1] a lantului μ1, graful G− e = (V,E \ {e}) arramane conex (deoarece ıntre x si v1 avem lantul [x,w1, . . . , wj, y, vi, . . . , v1]), contradictie cu ipoteza.Deci ıntre x si y exista un unic lant elementar.

6)⇒ 1) Fie G cu proprietatea ca ıntre orice doua noduri exista un unic lant elementar. Evident,G este conex. Daca G ar avea un ciclu elementar C = [x, v1, . . . , vk, x] atunci [x, v1] si [v1, . . . , vk, x]ar fi doua lanturi elementare ıntre x si v1, contradictie cu ipoteza. Deci G nu are cicluri elementare,si nici neelementare (deoarece orice ciclu neelementar s-ar descompune ın cicluri elementare muchie-disjuncte).

TEMA 4. ARBORI 46

4.3 Numararea arborilor partiali

Definitia 4.3.1. Fie G = (V,E) un graf fara bucle, unde V = {v1, . . . , vn}. Matricea deadmitanta asociata grafului G este matricea M = (mij)i,j=1,n definita prin:

mii = dG(vi), ∀ i ∈ {1, . . . , n};

−mij = numarul de muchii sau arce dintre vi si vj, ∀ i, j ∈ {1, . . . , n}, i = j.

Exemplul 4.3.1. Fie G graful reprezentat ın Figura 4.3.1.

1 2

5

3 4

Figura 4.3.1:

Matricea de admitanta a acestui graf este

M =

⎛⎜⎜⎜⎜⎝

2 −1 −1 0 0−1 5 −2 −1 −1−1 −2 4 −1 00 −1 −1 2 00 −1 0 0 1

⎞⎟⎟⎟⎟⎠ .

Observatia 4.3.1. Matricea de admitanta este o matrice simetrica (si pentru grafuri orientate!) si aretoate sumele pe linii si pe coloane egale cu zero.

Observatia 4.3.2. Definitia 4.3.1 se poate extinde si pentru grafuri cu bucle, considerand drept matricede admitanta a unui astfel de graf matricea de admitanta a grafului obtinut prin eliminarea tuturorbuclelor.

Teorema 4.3.1 (Kirchoff-Trent). Fie G = (V,E) un graf fara bucle avand matricea de admitantaM = (mij)i,j=1,n, n ≥ 2. Atunci numarul t(G) de arbori partiali ai grafului G verifica egalitatea

t(G) = (−1)i+j det[M ]ij, ∀ i, j ∈ {1, . . . , n},

unde [M ]ij reprezinta matricea obtinuta din M prin eliminarea liniei i si coloanei j.

Observatia 4.3.3. Teorema anterioara este valabila si pentru grafuri cu bucle, folosind Observatia4.3.2.

Exemplul 4.3.2. Aplicand teorema anterioara rezulta ca numarul arborilor partiali ai grafului G dinExemplul 4.3.1 este

t(G) = det[M ]22 =

∣∣∣∣∣∣∣∣2 −1 0 0−1 4 −1 00 −1 2 00 0 0 1

∣∣∣∣∣∣∣∣ = 12.

TEMA 4. ARBORI 47

Definitia 4.3.2. a) Graful neorientat simplu Kn = (V,E) definit prin

V = {v1, . . . , vn}, E = {[vi, vj]|i, j ∈ {1, . . . , n}, i = j}se numeste graf complet de ordinul n, unde n ∈ N

�.b) Graful neorientat simplu Kp,q = (V,E) definit prin

V = {x1, . . . , xp, y1, . . . , yq}, E = {[xi, yj]|i ∈ {1, . . . , p}, j ∈ {1, . . . , q}}se numeste graf bipartit complet, unde p, q ∈ N

�.

Corolarul 4.3.1. Graful complet Kn are nn−2 arbori partiali.

Demonstratie. Matricea de admitanta a grafului Kn este

M =

⎛⎜⎜⎝

n− 1 −1 . . . −1−1 n− 1 . . . −1. . . . . . . . . . . .−1 −1 . . . n− 1

⎞⎟⎟⎠ ( de tipul n× n),

deci conform teoremei anterioare avem

t(Kn) = det[M ]11 =

∣∣∣∣∣∣∣∣n− 1 −1 . . . −1−1 n− 1 . . . −1. . . . . . . . . . . .−1 −1 . . . n− 1

∣∣∣∣∣∣∣∣(determinant de ordinul n− 1). Adunand toate liniile la prima linie, apoi adunand linia obtinuta lacelalalte linii obtinem

t(Kn) =

∣∣∣∣∣∣∣∣1 1 . . . 1−1 n− 1 . . . −1. . . . . . . . . . . .−1 −1 . . . n− 1

∣∣∣∣∣∣∣∣ =

∣∣∣∣∣∣∣∣1 1 . . . 10 n . . . 0. . . . . . . . . . . .0 0 . . . n

∣∣∣∣∣∣∣∣ = nn−2.

Observatia 4.3.4. Corolarul anterior poate fi reformulat astfel: numarul arborilor ce pot fi construiticu n noduri date (numiti si arbori etichetati) este egal cu nn−2.

Corolarul 4.3.2. Graful bipartit complet Kp,q are pq−1qp−1 arbori partiali.

4.4 Arbori partiali de cost minim

Definitia 4.4.1. Un graf ponderat este o pereche (G, c), unde G = (V,E) este un graf iar c : E →R este o functie numita pondere (cost). Pentru orice e ∈ E, c(e) se numeste ponderea (costul)muchiei sau arcului e.

Definitia 4.4.2. Fie (G, c) un graf ponderat, G = (V,E).

a) Daca H = (U, F ) este un subgraf al lui G, atunci costul (ponderea) lui H este

c(H) =∑e∈F

c(e)

(adica suma costurilor muchiilor sau arcelor sale).

TEMA 4. ARBORI 48

b) Un arbore partial T � = (V, F ) al lui G cu proprietatea ca

c(T �) = min{c(T )|T = arbore partial al lui G}se numeste arbore partial de cost minim (APM) al grafului ponderat (G, c).

Observatia 4.4.1. Conform Propozitiei 4.1.7, un graf ponderat are arbori partiali de cost minim dacasi numai daca este conex.

Problema determinarii arborilor partiali de cost minim are numeroase aplicatii practice. Prezentamın continuare doi algoritmi fundamentali pentru rezolvarea acestei probleme.

Algoritmul 4.4.1 (Kruskal). Fie (G, c) un graf ponderat conex cu G = (V,E), V = {v1, . . . , vn}.Algoritmul are n− 1 pasi.

• La pasul i, i = 1, n− 1, dintre muchiile neselectate la pasii anteriori se selecteaza o muchieei ∈ E de cost minim cu proprietatea ca nu formeaza cicluri cu muchiile {e1, . . . , ei−1} selectatela pasii anteriori.

Algoritmul 4.4.2 (Prim). Fie (G, c) un graf ponderat conex cu G = (V,E), V = {v1, . . . , vn}.Algoritmul are n pasi.

• La pasul 0 se selecteaza un nod arbitrar x0 ∈ V .

• La pasul i, i = 1, n− 1, se selecteaza o muchie ei = [xj, xi] ∈ E de cost minim cu proprietateaca are ca extremitati un nod xj ∈ V selectat la un pas anterior si celalalt nod xi ∈ V neselectatla pasii anteriori; se selecteaza si nodul xi.

Teorema 4.4.1 (de corectitudine a algoritmilor Kruskal si Prim). In contextul AlgoritmilorKruskal sau Prim, fie F = {e1, . . . , en−1} multimea muchiilor selectate. Atunci T = (V, F ) este unarbore partial de cost minim al grafului ponderat (G, c).

Demonstratie. Vom prezenta o demonstratie comuna a corectitudinii celor doi algoritmi. Fie T0 =(V, ∅) si Ti = (V, {e1, . . . , ei}), ∀ i ∈ {1, 2, . . . , n− 1}, unde e1, e2, . . . , en−1 sunt muchiile selectate, ınaceasta ordine, de Algoritmul Kruskal sau de Algoritmul Prim.

Graful G fiind conex, selectarea muchiei ei este posibila la fiecare pas i, iar Ti este o padurepartiala a lui G (afirmatie evidenta pentru Algoritmul Kruskal, iar pentru Algoritmul Prim este oconsecinta a faptului ca nodurile neselectate la pasul i sunt izolate ın Ti).

Demonstram prin inductie dupa i ∈ {0, 1, . . . , n− 1} ca exista un APM T � = (V, F �) astfel ıncat

Ti ⊆ T � (adica {e1, . . . , ei} ⊆ F �). (4.4.1)

Pentru i = 0 afirmatia este evidenta, luand T � orice APM (exista, deoarece G este conex).Presupunem (4.4.1) adevarata pentru i − 1, adica exista T � = (V, F �) APM cu Ti−1 ⊆ T � si o

demonstram pentru i (i ∈ {1, 2, . . . , n− 1}).Fie ei = [xj, xi] muchia selectata de Algoritmul Kruskal sau de Algoritmul Prim la pasul i. In

cazul Algoritmului Prim, xj este nodul selectat la un pas anterior (j ≤ i− 1). Avem doua cazuri.Cazul 1) ei ∈ F �. Atunci {e1, . . . , ei} ⊆ F �, deci Ti ⊆ T �.Cazul 2) ei ∈ F �. Conform Teoremei numarului ciclomatic, graful H = T � + ei = (V, F � ∪ {ei})

obtinut din T � prin adaugarea muchiei ei contine un ciclu elementar unic

Ci = [xj, w0, . . . , wk, xi, xj]

avand ultima muchie chiar muchia ei. Cum Ti = Ti−1+ei este o padure, rezulta ca xj si xi sunt ın com-ponente conexe diferite ale lui Ti−1 (ın caz contrar Ti ar contine un ciclu de forma [xj, y0, . . . , yr, xi, xj]avand ultima muchie ei). Rezulta ca lantul elementar

μi = [xj, w0, . . . , wk, xi]

TEMA 4. ARBORI 49

(obtinut din ciclul Ci prin eliminarea muchiei ei) contine o muchie e′i = [x′, y′] astfel ıncat x′ esteın aceeasi componenta conexa cu xj ın padurea Ti−1, iar y′ nu este ın aceasta componenta conexa.Evident, rezulta ca e′i nu este muchie a lui Ti−1, adica e′i ∈ {e1, . . . , ei−1}, iar graful T ′

i = Ti−1 + e′inu contine cicluri. De asemenea, e′i = ei, deci e′i ∈ F ∗.

Pe de o parte, din descrierea Algoritmului Kruskal deducem ca

c(ei) ≤ c(e′i)

(deoarece muchia e′i nu formeaza cicluri cu {e1, . . . , ei−1}, deci ei fiind muchia selectata la pasul iverifica aceasta inegalitate).

Pe de alta parte, din descrierea Algoritmului Prim deducem ca la pasul i nodul x′ era deja selectatla un pas anterior (fiind ın aceeasi componenta conexa cu xj ın Ti−1), iar nodul y′ nu era selectat laun pas anterior (nefiind ın acea componenta conexa), deci din nou avem

c(ei) ≤ c(e′i)

(ei fiind muchia selectata la pasul i verifica aceasta inegalitate).Continuam demonstratia comuna pentru cei doi algoritmi. Fie

T �� = (T � + ei)− e′igraful partial al lui G obtinut din T � prin adaugarea muchiei ei si eliminarea muchiei e′i, adicaT �� = (V, F ��), unde F �� = F � ∪ {ei} \ {e′i}.

Evident, T �� este conex (T � este conex iar ıntre nodurile x′ si y′ dupa eliminarea muchiei e′iramane lantul obtinut din ciclul Ci prin eliminarea acestei muchii) si are n− 1 muchii (deoarece T �

are n− 1 muchii). Conform Teoremei numarului ciclomatic rezulta ca T �� este un arbore partial algrafului G.

Deoarece c(ei) ≤ c(e′i) obtinem

c(T ��) ≤ c(T �)

si cum T � este un APM rezulta ca si T �� este un APM (si, ın plus, c(T ��) = c(T �)). Cum Ti ⊆ T ��,demonstratia prin inductie a relatiei (4.4.1) este completa.

Luand i = n−1 ın aceasta relatie obtinem ca T ⊆ T �, unde T = Tn−1 = (V, F ), F = {e1, . . . , en−1}(multimea muchiilor selectate de algoritm) iar T � este un APM. Dar T si T � au fiecare cate n − 1muchii, deci T = T � si astfel T este un APM al grafului dat.

Exemplul 4.4.1. Fie graful ponderat (G, c) reprezentat ın Figura 4.4.1, unde costul fiecarei muchiieste scris langa segmentul corespunzator acesteia.

120150

130

90

80

40

70

2060

30 50 100

70

110

100 30

10

1 2 3 4

5

6

7 8 9 10

Figura 4.4.1:

Aplicarea Algoritmului Kruskal este evidentiata ın urmatorul tabel:

TEMA 4. ARBORI 50

Pas Muchia selectata Costul ei1 [5, 8] 102 [3, 6] 203 [1, 2] 304 [8, 9] 305 [2, 3] 506 [2, 5] 607 [4, 6] 908 [7, 8] 1009 [4, 10] 120

Arborele partial de cost minim obtinut este reprezentat ın Figura 4.4.2. Costul acestui APM este de510.

Aplicarea Algoritmului Prim pentru acelasi graf este evidentiata ın urmatorul tabel:

Pas Muchia selectata Costul ei Nodul selectat0 - - 11 [1, 2] 30 22 [2, 3] 50 33 [3, 6] 20 64 [2, 5] 60 55 [5, 8] 10 86 [8, 9] 30 97 [6, 4] 90 48 [8, 7] 100 79 [4, 10] 120 10

Arborele partial de cost minim obtinut este deci acelasi cu cel obtinut prin aplicarea AlgoritmuluiKruskal.

120

90

2060

30 50

100 30

10

1 2 3 4

5

6

7 8 9 10

Figura 4.4.2:

Observatia 4.4.2. Algoritmii Kruskal si Prim sunt specifici metodei de programare Greedy.Algoritmul Kruskal selecteaza muchii, ın ordinea crescatoare a costurilor, subgrafurile induse peparcurs de acestea nefiind neaparat conexe. Algoritmul Prim selecteaza muchii si noduri, nu neaparatın ordinea crescatoare a costurilor muchiilor, iar subgrafurile induse pe parcurs de muchiile selectatesunt conexe.

In implementari optime, se poate arata ca Algoritmul Kruskal are complexitatea O(m lnn) (fiindnecesara sortarea muchiilor dupa cost), iar Algoritmul Prim are complexitatea O(n2) (o astfel deimplementare va fi prezentata ın continuare), unde n si m reprezinta numerele de noduri, respectivde muchii ale grafului dat. Graful fiind conex, m ≥ n− 1.

TEMA 4. ARBORI 51

Pentru grafuri simple, m ≤ n(n−1)2

. Folosind si inegalitatea lnn ≤ n − 1, obtinem ca AlgoritmulKruskal este mai eficient pentru grafuri ”sarace” ın muchii, iar Algoritmul Prim este mai eficientpentru grafuri ”bogate” ın muchii.

Observatia 4.4.3. Pentru implementarea Algoritmului Kruskal, memoram graful ponderat conex(G, c), unde G = (V,E), V = {1, . . . , n}, E = {e1, . . . , em}, ıntr-o matrice cu 3 linii si m coloaneP = (pik) i = 1, 3

k = 1,m

avand semnificatia:

daca ek = [xk, yk] ∈ E, atunci p1k = xk, p2k = yk si p3k = c(ek).

Utilizam un vector S cu semnificatia

S[k] =

{1, daca ek a fost selectata,0, ın caz contrar,

∀ k ∈ {1, . . . ,m} si un vector CC cu semnificatia

CC[i] = numarul componentei conexe ın care se afla nodul i ın graful indus de muchiile selectate,∀ i ∈ {1, . . . , n}.

Astfel o muchie [x, y] nu formeaza cicluri cu muchiile selectate daca si numai daca

CC[x] = CC[y].

Descrierea ın pseudocod a algoritmului are formaKruskal :{ sortare(P );//se sorteaza coloanele matricei P

//crescator dupa costurile muchiilorpentru i = 1, m S[i]← 0;pentru i = 1, n CC[i]← i;cost← 0;//costul APMpoz ← 0;//cautarea urmatoarei muchii ek ce

//va fi selectata ıncepe de pe pozitia poz + 1pentru l = 1, n− 1 //pasul l{ k ← poz;

repeta{ k ← k + 1; x← p1k; y ← p2k; c← p3k;}

cat timp (CC[x] = CC[y]);S[k]← 1;//selectam ek = [x, y]cost← cost + c; poz ← k;aux← CC[y];//actualizam vectorul CC prin

//unificarea componentelor conexe ale lui x si ypentru i = 1, n

daca (CC[i] = aux) CC[i]← CC[x];}

}.Observatia 4.4.4. Pentru implementarea Algoritmului Prim, memoram graful ponderat conex sisimplu (G, c), unde G = (V,E), V = {1, . . . , n}, E = {e1, . . . , em}, cu ajutorul unei matriceC = (cij)i,j=1,n a costurilor (directe) avand semnificatia

cij =

⎧⎨⎩

c([i, j]), daca [i, j] ∈ E,0, daca i = j,∞, ın rest,

(4.4.2)

TEMA 4. ARBORI 52

∀i, j ∈ {1, . . . , n}. Pentru grafuri neorientate, matricea C este simetrica. In cazul grafurilor nesimpleputem lua

cij = min{c(e)|e = [i, j] ∈ E}.Utilizam un vector S cu semnificatia

S[i] =

{1, daca nodul i a fost selectat,0, ın caz contrar

si doi vectori t si TATA avand semnificatia

t[i] = costul minim al unei muchii [i, j] de la nodul i la un nod selectat j,

TATA[i] = nodul j ce atinge minimul ın t[i], ∀ i ∈ {1, . . . , n}.Descrierea ın pseudocod a algoritmului are forma

Prim :{ S[1]← 1;//selectam nodul 1

cost← 0;//costul APMpentru i = 2, n{ S[i]← 0; t[i]← ci1; TATA[i]← 1;}

pentru l = 1, n− 1 //cautam nodul y si muchia [x, y]//ce vor fi selectate la pasul l

{ min←∞;pentru i = 2, n{ daca (S[i] = 0) si (t[i] < min){ min← t[i]; y ← i;}

}S[y]← 1;// selectam nodul yx← TATA[y];// si muchia [x, y]cost← cost + cxy;pentru i = 2, n// actualizam vectorii t si TATA{ daca (S[i] = 0) si (t[i] > ciy){ t[i]← ciy; TATA[i]← y;}

}}

}.

Tema 5

Arborescente

5.1 Teorema de caracterizare a arborescentelor

Definitia 5.1.1. Fie G = (V,E) un graf orientat. Un nod x ∈ V se numeste radacina a grafuluiG daca pentru orice nod y ∈ V \ {x} exista cel putin un drum de la x la y.

Exemplul 5.1.1. In graful din Exemplul 3.1.2 nodurile 1, 2 si 3 sunt radacini, iar nodurile 4 si 5 nusunt radacini.

Definitia 5.1.2. a) O arborescenta este un arbore care are o radacina.

b) O arborescenta partiala a unui graf orientat G = (V,E) este un graf partial al lui G ce estearborescenta (adica o arborescenta T = (V, F ) cu F ⊆ E).

Exemplul 5.1.2. Graful din Exemplul 3.1.2 nu este arborescenta (are cicluri, deci nu este arbore).Doua arborescente partiale ale sale sunt reprezentate ın Figurile 5.1.1 si 5.1.2.

1 2

5

43

Figura 5.1.1:

1 2

5

43

Figura 5.1.2:

1 2

43

Figura 5.1.3:

Definitia 5.1.3. Un graf orientat G = (V,E) se numeste quasi-tare conex daca pentru orice douanoduri x, y ∈ V exista un nod z ∈ V si drumuri de la z la x si de la z la y.

Observatia 5.1.1. Ca si ın definitiile conexitatii si tare-conexitatii, si ın Definitiile 5.1.1 si 5.1.3 putemınlocui termenul de ”drum” cu ”drum elementar” (conform Observatiei 3.4.5).

Observatia 5.1.2. Evident, orice graf quasi-tare conex este conex. Reciproca nu este adevarata. Deexemplu, graful reprezentat ın Figura 5.1.3 este conex, dar nu este quasi-tare conex (pentru nodurilex = 1 si y = 4 nu exista noduri z din care sa avem drumuri la x si la y).

Observatia 5.1.3. Orice graf tare-conex este quasi-tare conex (deoarece pentru orice noduri x, y luandz = x exista drumuri (z, . . . , x) si (z, . . . , y)). Reciproca nu este adevarata. De exemplu, graful dinExemplul 3.1.2 este quasi-tare conex, dar nu este tare-conex.

Propozitia 5.1.1. Un graf orientat este quasi-tare conex daca si numai daca are (cel putin) oradacina.

53

TEMA 5. ARBORESCENTE 54

Demonstratie. ”⇒” Fie G = (V,E) un graf quasi-tare conex, V = {v1, . . . , vn}. Demonstram prininductie dupa k ∈ {1, . . . , n} ca exista un nod xk ∈ V cu drumuri (xk, . . . , v1), (xk, . . . , v2), . . . , (xk, . . . , vk).

Pentru k = 1 luam x1 = v1.Presupunem adevarata afirmatia pentru k − 1 si o demonstram pentru k. Deoarece graful este

quasi-tare conex, rezulta ca exista un nod xk ∈ V cu drumuri (xk, . . . , xk−1) si (xk, . . . , vk). Conformipotezei de inductie, exista drumuri (xk−1, . . . , v1), . . . , (xk−1, . . . , vk−1), deci exista drumuri

(xk, . . . , xk−1, . . . , v1), . . . , (xk, . . . , xk−1, . . . , vk−1), (xk, . . . , vk).

Demonstratia prin inductie este ıncheiata.Luand k = n, nodul xn este o radacina a grafului G.

”⇐” Fie G = (V,E) si z ∈ V o radacina a lui G. Pentru orice noduri x, y ∈ V exista drumuri(z, . . . , x) si (z, . . . , y), deci G este quasi-tare conex.

Teorema 5.1.1 (de caracterizare a arborescentelor). Fie G = (V,E) un graf orientat cu nnoduri. Urmatoarele afirmatii sunt echivalente:

1) G este quasi-tare conex si fara cicluri;

2) G este quasi-tare conex si are m = n− 1 arce;

3) G este o arborescenta (adica arbore cu radacina);

4) exista un nod x ∈ V astfel ıncat pentru orice nod v ∈ V exista un unic drum de la x la v;

5) G este quasi-tare conex si minimal cu aceasta proprietate, adica daca se elimina un arc oarecaregraful obtinut nu mai este quasi-tare conex;

6) G este conex si exista un nod x ∈ V astfel ıncat d−(x) = 0 si d−(v) = 1 ∀ v ∈ V \ {x};7) G este fara cicluri si exista un nod x ∈ V astfel ıncat d−(x) = 0 si d−(v) = 1 ∀ v ∈ V \ {x}.

Demonstratie. 1) ⇒ 2) Fie G quasi-tare conex si fara cicluri. Fiind quasi-tare conex, G este conex.Deci G este un arbore si astfel are m = n− 1 arce (conform Teoremei de caracterizare a arborilor).

2)⇒ 3) Fie G quasi-tare conex si cu m = n− 1 arce. Fiind quasi-tare conex, G este conex si areradacina (conform propozitiei anterioare). Fiind conex cu m = n − 1 arce, G este arbore (conformteoremei amintite mai sus).

3)⇒ 4) Fie G arborescenta si x o radacina a lui G. Deci pentru orice nod v ∈ V exista un drumde la x la v. Graful G fiind un arbore, acest drum, fiind si lant, este unic.

4) ⇒ 5) Fie G cu proprietatea 4). Deci x este o radacina a lui G si astfel G este quasi-tareconex (conform propozitiei anterioare). Fie e = (y, z) ∈ E un arc arbitrar fixat. Demonstram caG − e = (V,E \ {e}) nu este quasi-tare conex prin reducere la absurd. Daca G − e ar fi quasi-tareconex, atunci ar exista un nod v ∈ V si drumuri (v, . . . , y) si (v, . . . , z) ın G − e. x fiind radacinaın G, s-ar obtine doua drumuri distincte (x, . . . , v, . . . , y, z) si (x, . . . , v, . . . , z) de la x la z ın G,contradictie cu ipoteza.

5) ⇒ 6) Fie G quasi-tare conex minimal. Fiind quasi-tare conex, G este conex. Conformpropozitiei anterioare, G are o radacina x. Demonstram ca d−(x) = 0 prin reducere la absurd.Daca am avea d−(x) > 0, atunci ar exista un arc e = (y, x) ∈ E, iar G − e ar avea ın continuareradacina x (deoarece exista drum elementar (x, . . . , y) ın G, deci si ın G−e) si astfel G−e ar ramanequasi-tare conex (conform propozitiei anterioare), contradictie cu ipoteza.

Fie acum v ∈ V \ {x} un nod arbitrar fixat. x fiind radacina, exista un drum (x, . . . , y, v) delungime nenula (v = x), deci d−(v) ≥ 1 (∃(y, v) ∈ E). Demonstram ca d−(v) = 1 prin reducere laabsurd. Daca am avea d−(v) > 1, atunci ar exista doua arce diferite e1 = (y1, v),e2 = (y2, v) ∈ E, iar


G − e1 ar avea ın continuare radacina x (deoarece exista un drum (x, . . . , y2, v) ın G − e1) si astfelG− e1 ar ramane quasi-tare conex (conform propozitiei anterioare), contradictie cu ipoteza.

6)⇒ 7) Fie G cu proprietatea 6). Conform Propozitiei 3.3.2, m =∑t∈V

d−(t) = n− 1, deci G este

un arbore (conform Teoremei de caracterizare a arborilor) si astfel nu are cicluri.

7)⇒ 1) Fie G cu proprietatea 7). Din nou, m =∑t∈V

d−(t) = n− 1, deci G este un arbore si astfel

este conex. Rezulta ca pentru orice nod y ∈ V exista un lant elementar unic [x, v1, . . . , vk, y].Deoarece d−(x) = 0 nu putem avea (v1, x) ∈ E, deci (x, v1) ∈ E. Cum (x, v1) ∈ E si d−(v1) = 1,

nu putem avea (v2, v1) ∈ E, deci (v1, v2) ∈ E.Continuand ın acest mod (inductie!) obtinem (v2, v3) ∈ E, . . . , (vk, y) ∈ E, deci lantul [x, v1, . . . , vk, y]

este un drum de la x la y.Rezulta ca x este o radacina ın G si astfel, conform propozitiei anterioare, G este quasi-tare

conex.

Corolarul 5.1.1. Orice arborescenta G = (V,E) are o unica radacina x si aceasta verifica pro-prietatile 4), 6) si 7) din teorema anterioara.

Demonstratie. Concluzia rezulta imediat din demonstratia teoremei anterioare.

5.2 Arborescente partiale de cost minim

Definitia 5.2.1. Fie (G, c) un graf orientat ponderat, G = (V,E). O arborescenta partiala T ∗ =(V, F ) a lui G cu proprietatea ca

c(T �) = min{c(T )|T = arborescenta partiala a lui G}se numeste arborescenta partiala de cost minim a grafului ponderat (G, c).

Pezentam ın continuare un algoritm fundamental pentru rezolvarea acestei probleme. Avemnevoie de cateva notiuni si rezultate pregatitoare.

Lema 5.2.1. Un graf orientat are arborescente partiale daca si numai daca este quasi-tare conex,adica daca si numai daca are (cel putin) o radacina.

Definitia 5.2.2. Fie (G, c) un graf orientat ponderat si quasi-tare conex, G = (V,E), V = {v1, . . . , vn}.Fie x = vs o radacina ın G.

Definim graful partial α(G, c) = (V, F ) astfel:

• pentru fiecare nod vi ∈ V \{x}, fie ei ∈ E un arc de cost minim avand forma ei = (y, vi), y ∈ V(exista un astfel de arc, conform proprietatii 6) din Teorema 5.1.1, Corolarului 5.1.1 si Lemei5.2.1);

• daca d−(x) = 0, atunci F = {ei|i ∈ {1, . . . , n} \ {s}};• daca d−(x) > 0, fie es ∈ E un arc de cost minim avand forma es = (y, x), y ∈ V . Fie ei� un

arc de cost maxim din multimea {ei|i ∈ {1, . . . , n}}. Atunci F = {ei|i ∈ {1, . . . , n} \ {i�}}.Observatia 5.2.1. In contextul definitiei anterioare, daca d−(x) = 0 atunci x este unica radacina a luiG, iar daca d−(x) > 0 atunci multimea F nu depinde de alegerea lui x; deci ın ambele cazuri grafulα(G, c) nu depinde de alegerea radacinii x.

Exemplul 5.2.1. Fie (G, c) graful ponderat reprezentat ın Figura 5.2.1.Arcele de cost minim la intrarea ın noduri fiind (5, 1), (3, 2), (5, 3), (2, 4), (4, 5), (4, 6), (1, 7),

(7, 8) iar cel mai mare cost dintre aceste arce avand arcul (5, 1), obtinem ca graful α(G, c) este celreprezentat ın Figura 5.2.2.


20

155

40

30

25

20

10 15

10

20

5

10

23

1

2 3

4 5

6

7

8

Figura 5.2.1:

Lema 5.2.2. Fie (G, c) un graf orientat ponderat si quasi-tare conex, si fie α(G, c) graful partial allui G dat de definitia anterioara. Daca α(G, c) nu are circuite, atunci α(G, c) este o arborescentapartiala de cost minim a grafului (G, c).

Definitia 5.2.3. Fie (G, c) un graf orientat ponderat, G = (V,E), si fie C un circuit elementar allui G. Definim graful ponderat (G|C , c|C), G|C = (V ′, E ′) astfel:

• V ′ = V \ V (C) ∪ {xC}, unde V (C) este multimea nodurilor circuitului C, iar xC ∈ V este unnod nou; spunem ca nodul xC este obtinut prin contractia circuitului C;

• E ′ = E1 ∪ E2 ∪ E3, unde

E1 = {e ∈ E|e = (x, y), x, y ∈ V (C)},E2 = {(xC , y)|y ∈ V (C), ∃x ∈ V (C) astfel ıncat (x, y) ∈ E},E3 = {(y, xC)|y ∈ V (C), ∃x ∈ V (C) astfel ıncat (y, x) ∈ E};

• pentru orice e = (x, y) ∈ E1, c|C(e) = c(e);

• pentru orice e = (xC , y) ∈ E2,

c|C(e) = min{c(x, y)|x ∈ V (C), (x, y) ∈ E};

spunem ca arcul e provine din arcul (x, y) ∈ E ce atinge acest minim;

• pentru orice e = (y, xC) ∈ E3,

c|C(e) = min{c(y, x)− c(z, x)|x ∈ V (C), (y, x) ∈ E, (z, x) ∈ E(C)}

(unde E(C) reprezinta multimea arcelor circuitului C); spunem din nou ca arcul e provinedin arcul (y, x) ∈ E ce atinge acest minim.

Spunem ca graful ponderat (G|C , c|C) se obtine din graful (G, c) prin contractia circuitului C.


155

20

15

10

5

10

1

2 3

4 5

6

7

8

Figura 5.2.2:

15

20

5

40

20

8

30

1

6

7

8

9C

x=

Figura 5.2.3:

Exemplul 5.2.2. Pentru graful ponderat (G, c) din Exemplul 5.2.1 si circuitul elementar C = (2, 4, 5, 3, 2),graful (G|C , c|C) este reprezentat ın Figura 5.2.3.

De exemplu, arcul (xC , 6) provine din arcul de cost minim dintre (4, 6) si (5, 6), adica din (4, 6), siare costul 20; arcul (1, xC) provine din acel arc dintre (1, 2) si (1, 3) ce are diferenta de cost minimadintre c(1, 2)− c(3, 2) = 20−10 = 10 si c(1, 3)− c(5, 3) = 23−15 = 8, adica din (1, 3) si are costul 8.

Definitia 5.2.4. Fie (G, c) un graf orientat ponderat, G = (V,E), V = {v1, . . . , vn}, C un circuitelementar al lui G si (G|C , c|C) graful ponderat obtinut din G prin contractia circuitului C, G|C =(V ′, E ′). Fie T = (V ′, F ′) o arborescenta partiala ın graful G|C si xT radacina sa. Definim grafulpartial ϕ(T ) = (V, F ) al lui G prin:

• daca xT = xC (xC fiind nodul obtinut prin contractia circuitului C ın graful G), atunci F =F1 ∪ F2 ∪ [E(C) \ {e�}], unde

F1 = {e ∈ F ′|e = (x, y), x, y ∈ V ′ \ {xC}},F2 = {(x, y)|(x, y) ∈ E este arcul din care provine un arc (xC , y) ∈ F ′}


(luand un singur arc (x, y) ∈ E pentru fiecare arc e = (xC , y) ∈ F ′),

E(C) este multimea arcelor circuitului C, iar e� este un arc de cost maxim din E(C);

• daca xT = xC, atunci F = F1 ∪ F2 ∪ {(y, x)} ∪ [E(C) \ {(z, x)}], unde F1 si F2 sunt definitemai sus, (y, x) ∈ E este arcul din care provine unicul arc (y, xC) ∈ F ′, iar (z, x) ∈ E(C) (arculunic de pe circuitul C incident cu x spre interior).

Lema 5.2.3. In contextul definitiei anterioare, ϕ(T ) este o arborescenta partiala ın graful G.

Definitia 5.2.5. In contextul definitiei anterioare, spunem ca arborescenta partiala ϕ(T ) se obtinedin arborescenta partiala T prin decontractia circuitului C.

Exemplul 5.2.3. Fie graful (G, c) din Exemplul 5.2.1, circuitul elementar C = (2, 4, 5, 3, 2) si graful(G1, c1) calculat si reprezentat ın Exemplul 5.2.2.

Graful partial T = α(G1, c1) construit conform Definitiei 5.2.2 este reprezentat ın Figura 5.2.4.

155

20

8

1

6

7

8

9C

x=

Figura 5.2.4:

Deci T este o arborescenta partiala (de cost minim, conform Lemei 5.2.2) ın graful (G1, c1), avandradacina 1, 1 = xC . Arborescenta partiala ϕ(T ) a grafului initial G obtinuta din T prin decontractiacircuitului C este reprezentata ın Figura 5.2.5. Arcul (xC , 6) din T s-a ınlocuit ın ϕ(T ) cu arcul (4, 6)din care a provenit; arcul (1, xC) din T s-a ınlocuit ın ϕ(T ) cu arcul (1, 3) din care a provenit si acondus si la eliminarea arcului (5, 3) (arcul unic de pe circuitul C incident cu 3 spre interior).

Lema 5.2.4. Fie (G, c) un graf orientat ponderat, C un circuit elementar al lui G si (G1, c1) =(G|C , c|C) graful ponderat obtinut din G prin contractia circuitului C. Atunci G are arborescentepartiale daca si numai daca G1 are arborescente partiale.

Lema 5.2.5. Fie (G, c) un graf orientat ponderat si quasi-tare conex, C un circuit elementar allui G si (G1, c1) = (G|C , c|C) graful ponderat obtinut din G prin contractia circuitului C. Fie To arborescenta partiala ın graful (G1, c1) si ϕ(T ) arborescenta partiala ın graful (G, c) construitaconform Definitiei 5.2.4. Atunci, cu notatiile din acea definitie, avem

c(ϕ(T )) =

{c1(T ) + c(C), daca xC = xT ,c1(T ) + c(C)− c(e�), daca xC = xT .


155

20

10

5

10

23

1

2 3

4 5

6

7

8

Figura 5.2.5:

Lema 5.2.6. Fie (G, c) un graf orientat ponderat si quasi-tare conex si fie α(G, c) graful partial allui G dat de Definitia 5.2.2. Fie C un circuit elementar ın graful α(G, c), deci si ın graful G. Fie(G1, c1) = (G|C , c|C) graful ponderat obtinut din G prin contractia circuitului C si fie T o arborescentapartiala de cost minim ın acest graf. Atunci graful ϕ(T ) construit conform Definitiei 5.2.4 este oarborescenta partiala de cost minim ın graful (G, c).

Exemplul 5.2.4. Revenind la exemplul anterior, cum T = α(G1, c1) este o arborescenta partiala decost minim ın graful (G1, c1) (conform Lemei 5.2.2), rezulta ca ϕ(T ) este o arborescenta partiala decost minim ın graful initial (G, c).

Conform Lemelor 5.2.2 si 5.2.6 obtinem urmatorul algoritm pentru determinarea unei arborescentepartiale de cost minim.

Algoritmul 5.2.1 (Edmonds). Fie (G, c) un graf orientat ponderat si quasi-tare conex (verificareaquasi-tare conexitatii poate fi efectuata pe baza Propozitiei 5.1.1). Fie G = (V,E), V = {1, . . . , n}.Algoritmul descris ın pseudocod are formaEdmonds :{ repeta{ k ← 1; nv ← n;//k = pasul; nv = numarul de noduri la pasul curent

greedy;//se determina graful partial α(G, c) pentru graful curentdaca (exista circuit) //acesta contine circuite{ determina circuit;// se determina un circuit elementar C

nv ← nv + 1;//nv reprezinta nodul xC

contractie;// se efectueaza contractia circuitului Ck ← k + 1;//se reia algoritmul pentru noul graf

}}cat timp (exista circuit);

//nu mai exista circuite, structura α(G, c) din graful curent este arborescenta partiala de cost minim//ın acest graf; trecem la decontractiile succesive ale arborescentelor partiale de cost minim,//ın ordinea inversa a pasilor

k ← k − 1;cat timp (k > 0){ decontractie;//decontractia arborescentei partiale din graful curent


nv ← nv − 1;k ← k − 1;//se reia algoritmul pentru noul graf

}afisare;//se afiseaza arborescenta partiala de cost minim

}.Graful partial (structura de tip greedy) α(G, c) poate fi usor memorat ıntr-un vector TATA avand

semnificatia

TATA[i] =

{j, daca (j, i) este un arc al grafului α(G, c),0, ın caz contrar,

iar circuitul elementar C din acest graf poate fi determinat si memorat folosind un vector PAS avandsemnificatia

PAS[i] =

{k, daca nodul i face parte din circuitul C de la un pas k,0, ın caz contrar.

Observatia 5.2.2. Algoritmul Edmonds este specific metodei de programare Greedy. In imple-mentarea optima, se poate arata ca acest algoritm are complexitatea O(mn), unde n si m reprezintanumerele de noduri, respectiv de arce ale grafului dat.

Tema 6

Clase particulare de grafuri

6.1 Grafuri euleriene

Definitia 6.1.1. a) Fie G = (V,E) un graf. Un lant simplu, ciclu, drum simplu sau circuit ıngraful G ce contine toate muchiile sau arcele lui G se numeste eulerian.

b) Un graf neorientat se numeste eulerian daca are (cel putin) un ciclu eulerian.

c) Un graf orientat se numeste eulerian daca are (cel putin) un circuit eulerian.

Exemplul 6.1.1. Graful neorientat reprezentat ın Figura 6.1.1 este eulerian, un ciclu eulerian al saufiind C = [1, 2, 3, 4, 10, 9, 3, 6, 2, 5, 8, 7, 5, 1].

1 2 3 4

7 8 9 10

65

Figura 6.1.1:

Exemplul 6.1.2. Fie graful orientat reprezentat ın Figura 6.1.2. Un drum eulerian ın acest graf este(1, 2, 3, 4, 6, 3, 5, 6, 1, 5, 4).

2

1

3

4

5 6

Figura 6.1.2:

61

TEMA 6. CLASE PARTICULARE DE GRAFURI 62

Observatia 6.1.1. Existenta lanturilor, ciclurilor, drumurilor sau circuitelor euleriene nu este influentatade prezenta unor eventuale noduri izolate, deci putem analiza ın continuare doar grafurile fara noduriizolate.

Teorema 6.1.1 (Euler, de caracterizare a grafurilor euleriene neorientate). Un graf neorientat faranoduri izolate este eulerian daca si numai daca este conex si par.

Demonstratie. ”⇒” Fie G = (V,E) un graf neorientat eulerian, fara noduri izolate. Fie C un ciclueulerian al lui G. Neexistand noduri izolate, orice nod x ∈ V are o muchie incidenta, si cum aceastamuchie apartine lui C rezulta ca si nodul x apartine lui C. Deci C contine si toate nodurile luiG. Rezulta ca G este conex, ıntre orice doua noduri distincte x, y ∈ V existand un lant elementarcontinut ın ciclul C.

Cum C contine toate muchiile lui G rezulta ca

dG(x) = dC(x) = par, ∀ x ∈ V(orice ciclu este evident un subgraf par).

”⇐” Fie G = (V,E) un graf neorientat conex, par si fara noduri izolate. Conform Propozitiei4.1.2, graful G are o descompunere ın cicluri elementare muchie-disjuncte C1, . . . , Ck, k ≥ 1.

Daca k = 1, atunci C1 este un ciclu eulerian ın G.Daca k ≥ 2, graful G fiind conex, ciclul C1 are un nod comun cu un alt ciclu din {C2, . . . , Ck}. Fie

C2 acest ciclu si C ′2 ciclul obtinut pornind din nodul comun si parcurgand ıntai C1 apoi C2. Spunem

ca C ′2 se obtine prin concatenarea (alipirea) ciclurilor C1 si C2.

Daca k = 2, atunci C ′2 este un ciclu eulerian ın G.

Daca k ≥ 3, din conexitatea lui G obtinem ca C ′2 are un nod comun cu un alt ciclu din

{C3, . . . , Ck}, fie acesta C3, si fie C ′3 ciclul obtinut prin concatenarea ciclurilor C ′

2 si C3. Continuandacest procedeu de concatenare a ciclurilor, rezulta (prin inductie dupa k) ca obtinem un ciclu C ′

k ceeste eulerian ın G.

Exemplul 6.1.3. Graful din Exemplul 6.1.1 este conex, par si fara noduri izolate, deci este eulerian.

Observatia 6.1.2. Demonstratia teoremei anterioare este constructiva, ea indicand un algoritm dedeterminare a unui ciclu eulerian ıntr-un graf neorientat conex, par si fara noduri izolate.

Prezentam ın continuare un algoritm pentru determinarea unui ciclu eulerian bazat pe arboreleDF al grafului dat.

Algoritmul 6.1.1 (de determinare a unui ciclu eulerian). Fie G = (V,E) un graf neorientatconex, par si fara noduri izolate. Verificarea conexitatii, cu neglijarea nodurilor izolate, poate fiefectuata cu ajutorul parcurgerii DF (Algoritmul 3.5.3), iar verificarea paritatii poate fi efectuata cuajutorul Propozitiei 3.3.1. Fie T = (V, F ) arborele DF al lui G, considerand ca radacina a parcurgeriiDF un nod x1 ∈ V arbitrar fixat. Un ciclu eulerian ın G poate fi obtinut astfel:

• se porneste din nodul radacina x1;

• se parcurg cu prioritate muchiile (neparcurse anterior) ce nu apartin arborelui DF (adica dacaexista o astfel de muchie [x, y], incidenta cu nodul curent x, se parcurge aceasta muchie si nodulcurent devine y, iar daca nu exista o astfel de muchie se parcurge, daca exista, o muchie [x, z]a arborelui DF , incidenta cu nodul curent x, si nodul curent devine z).

• se continua parcurgerea ın modul descris mai sus, cat timp este posibil.

Exemplul 6.1.4. Arborele DF (1) al grafului din Exemplul 6.1.1 este reprezentat ın Figura 6.1.3.Aplicand algoritmul anterior obtinem ciclul eulerian

[1, 5, 8, 7, 5, 2, 6, 3, 9, 10, 4, 3, 2, 1].


1 2 3 4

7 8 9 10

65

Figura 6.1.3:

Observatia 6.1.3. Datorita necesitatii parcurgerii DF , dar si a tuturor muchiilor grafului dat, com-plexitatea Algoritmului 6.1.1 este O(m), unde m reprezinta numarul de muchii ale grafului dat.

Observatia 6.1.4. Pentru implementarea Algoritmului 6.1.1, ın cazul grafurilor simple putem memoraarborele DF tot ın matricea de adiacenta A considerand

aij = 2 daca muchia [i, j] apartine arborelui DF.

Algoritmul descris ın pseudocod are formaciclu eulerian(x) :{ i← x;//i este nodul curent al ciclului eulerian

repeta{ afiseaza i;

j ← 1;cat timp (aij = 1) si (j ≤ n) j ← j + 1;// cautam [i, j] ∈ DFdaca (j ≤ n) //exista, deci [i, j] ∈ ciclu eulerian{ aij ← 0; aji ← 0;//eliminam [i, j] din graf

i← j;}

altfel{ j ← 1;

cat timp (aij = 2) si (j ≤ n) j ← j + 1;//cautam [i, j] ∈ DFdaca (j ≤ n) //exista, deci [i, j] ∈ ciclu eulerian{ aij ← 0; aji ← 0;//eliminam [i, j] din graf

i← j;}

}}cat timp (j ≤ n);

}.Observatia 6.1.5. In cazul grafurilor nesimple, pentru implementarea Algoritmului 6.1.1 graful datpoate fi memorat cu ajutorul matricei de adiacenta, iar arborele DF poate fi memorat cu ajutorulvectorului TATA. Verificarea daca [i, j] ∈ DF revine la ”TATA[i] = j sau TATA[j] = i”, iareliminarea unei muchii [i, j] din graf revine la ”aij ← aij − 1 si aji ← aji − 1”.

Corolarul 6.1.1. Un graf neorientat fara noduri izolate are un lant eulerian deschis daca si nu-mai daca este conex si are exact doua noduri de grade impare. In plus, orice lant eulerian are caextremitati cele doua noduri de grade impare.

Demonstratie. ”⇒” Fie G = (V,E) un graf neorientat fara noduri izolate, avand un lant euleriandeschis μ = [x, v1, . . . , vk, y]. Evident, G este conex.


Fie G′ = (V,E ∪ {e}), unde e = [y, x], e ∈ E (muchie noua). Adaugand muchia e la lantul μobtinem un ciclu eulerian C = [x, v1, . . . , vk, y, x] ın graful G′. Conform Teoremei 6.1.1, G′ este conexsi par. Rezulta ca

dG(x) = dG′(x)− 1 = impar,

dG(y) = dG′(y)− 1 = impar,

dG(z) = dG′(z) = par ∀ z ∈ V \ {x, y}.

”⇐” Fie G = (V,E) un graf neorientat conex, fara noduri izolate, cu exact doua noduri x si yde grade impare. Fie G′ graful definit ca mai sus. Rezulta ca G′ este conex si par, deci conformTeoremei 6.1.1 el contine un ciclu eulerian C = [x, v1, . . . , vk, y, x]. Eliminand muchia e = [y, x] depe ciclul C obtinem un lant eulerian deschis μ = [x, v1, . . . , vk, y] ın graful G.

Observatia 6.1.6. Folosind trecerea ıntre grafurile G si G′ si ıntre lantul eulerian deschis μ si cicluleulerian C din demonstratia corolarului anterior, precum si Algoritmul 6.1.1, se obtine un algoritmpentru determinarea lanturilor euleriene deschise ıntr-un graf dat.

Teorema 6.1.2 (de caracterizare a grafurilor euleriene orientate). Un graf orientat fara noduriizolate este eulerian daca si numai daca este conex si d+(x) = d−(x), pentru orice nod x.

Demonstratie. Demonstratia este analoga cu cea a Teoremei 6.1.1, ınlocuind ”ciclu” cu ”circuit” si”d(x) = par” cu ”d+(x) = d−(x)”.

Existenta unui circuit se obtine pornind dintr-un nod arbitrar si parcurgand succesiv arce cattimp este posibil (revenirea ın nodul initial este asigurata de conditia d+(x) = d−(x) ∀x).Corolarul 6.1.2. Un graf orientat fara noduri izolate are un drum eulerian deschis daca si numaidaca este conex si are doua noduri x si y astfel ıncat d+(x) = d−(x) + 1, d+(y) = d−(y) − 1,d+(z) = d−(z) pentru orice nod z diferit de x si y. In plus, orice drum eulerian are ca extremitateinitiala nodul x si ca extremitate finala nodul y.

Demonstratie. Demonstratia este analoga cu cea a Corolarului 6.1.1, utilizand acum Teorema 6.1.2.

Exemplul 6.1.5. Graful din Exemplul 6.1.2 este conex, fara noduri izolate sid+(1) = d−(1) + 1, d+(4) = d−(4)− 1, d+(z) = d−(z) ∀ z ∈ V \ {1, 4},deci graful are drumuri euleriene de forma (1, . . . , 4).

Observatia 6.1.7. Demonstratia Teoremei 6.1.2 este constructiva, ea indicand un algoritm de de-terminare a unui circuit eulerian ıntr-un graf orientat ce verifica ipotezele teoremei. De asemenea,analog Observatiei 6.1.6, acest algoritm poate fi utilizat si pentru determinarea unui drum euleriandeschis ıntr-un graf orientat ce verifica ipotezele Corolarului 6.1.2.

6.2 Grafuri hamiltoniene

Definitia 6.2.1. a) Fie G = (V,E) un graf. Un lant elementar, ciclu elementar, drum elementarsau circuit elementar ın graful G ce contine toate nodurile lui G se numeste hamiltonian.

b) Un graf neorientat se numeste hamiltonian daca are (cel putin) un ciclu hamiltonian.

c) Un graf orientat se numeste hamiltonian daca are (cel putin) un circuit hamiltonian.

Exemplul 6.2.1. Graful eulerian din Exemplul 6.1.1 nu este hamiltonian, deoarece pentru ca un circuitsa treaca de la nodul 1 la nodul 3 si sa revina ın nodul 1 ar trebui sa treaca de cel putin doua oriprin nodul 2.


Exemplul 6.2.2. Graful reprezentat ın Figura 6.2.1 este hamiltonian, un ciclu hamiltonian al sau fiindC = [1, 2, 3, 4, 8, 7, 6, 5, 1]. Acest graf nu este eulerian, avand 4 noduri de grade impare.

1 2 3 4

5 6 7 8

Figura 6.2.1:

Observatia 6.2.1. Spre deosebire de problemele euleriene studiate ın sectiunea anterioara, problemelede testare a hamiltoneitatii unui graf si de determinare a unui ciclu sau circuit hamiltonian optimıntr-un graf ponderat sunt probleme pentru care nu se cunosc (pana ın prezent) algoritmi de rezolvarecu complexitate polinomiala (numite si probleme NP). Dispunem totusi de numeroase conditii fienecesare, fie suficiente, pentru ca un graf dat sa fie hamiltonian. Cateva astfel de conditii vor fiprezentate ın continuare.

Observatia 6.2.2. Este evident ca ıntr-un graf cu n ≥ 3 noduri orice lant, ciclu, drum sau circuithamiltonian nu utilizeaza bucle si nici muchii sau arce multiple, deci este suficient sa studiem hamil-toneitatea pentru grafurile simple.

Lema 6.2.1 (Bondy, Chvatal). Fie G = (V,E) un graf neorientat simplu cu n ≥ 3 noduri. Fiex, y ∈ V astfel ıncat

x = y, [x, y] ∈ E si d(x) + d(y) ≥ n.

Atunci graful G este hamiltonian daca si numai daca graful

G+ [x, y] = (V,E ∪ {[x, y]})

este hamiltonian.

Demonstratie. Evident, daca G este hamiltonian atunci orice ciclu hamiltonian ın G este ciclu hamil-tonian si ın G+ [x, y], deci G+ [x, y] este hamiltonian.

Reciproc, fie G+ [x, y] hamiltonian si C un ciclu hamiltonian ın acest graf.Cazul 1) Daca C nu contine muchia [x, y], atunci C este un ciclu hamiltonian ın graful G.Cazul 2) Daca C contine muchia [x, y], atunci prin eliminarea muchiei [x, y] din ciclul C obtinem

un lant hamiltonian

μ = [x = v1, v2, . . . , vn = y]

ın graful G. Fie

A = {i ∈ {1, . . . , n− 1}|[x, vi+1] ∈ E},B = {i ∈ {1, . . . , n− 1}|[vi, y] ∈ E}.

Avem card (A) = d(x) si card (B) = d(y), deci, conform ipotezei,

card (A) + card (B) ≥ n.


Cum A ∪B ⊆ {1, . . . , n− 1}, avem card (A ∪B) ≤ n− 1, deci

card (A ∩B) = card (A) + card (B)− card (A ∪B) ≥ n− (n− 1) = 1,

adica A ∩B = ∅. Fie k ∈ A ∩B. Atunci

[x = v1, v2, . . . , vk, y = vn, vn−1, . . . , vk+1, x]

este un ciclu hamiltonian ın graful G.

Definitia 6.2.2. Fie G un graf neorientat simplu cu n ≥ 3 noduri. Inchiderea lui G, notata cucl(G), este graful neorientat simplu obtinut din G prin adaugarea repetata a tuturor muchiilor [x, y]ıntre noduri distincte si neadiacente x, y cu d(x) + d(y) ≥ n ın graful curent.

Observatia 6.2.3. Daca H = cl(G), atunci pentru orice noduri distincte x, y cu [x, y] ∈ E(H) avemdH(x) + dH(y) < n, unde E(H) este multimea muchiilor grafului H.

Observatia 6.2.4. Graful cl(G) este bine definit, nedepinzand de ordinea de adaugare a muchiilor.Acest fapt poate fi demonstrat prin inductie dupa numarul muchiilor adaugate.

Exemplul 6.2.3. Fie G graful reprezentat ın Figura 6.2.2.

2

1

3

4

6 5

Figura 6.2.2:

Adaugand succesiv muchiile [1, 5] (deoarece d(1) + d(5) = 4 + 2 ≥ n = 6), [2, 4] (deoareced(2) + d(4) = 2 + 4 ≥ n, ın graful curent), [2, 5] (deoarece d(2) + d(5) = 3 + 3 ≥ n, ın graful curent!),[2, 6], [3, 5] si [3, 6], obtinem ınchiderea cl(G) = K6, unde K6 este graful complet cu 6 noduri.

Lema 6.2.2 (Lema ınchiderii; Bondy, Chvatal). Fie G un graf neorientat simplu cu n ≥ 3 noduri.Atunci G este hamiltonian daca si numai daca graful cl(G) este hamiltonian.

Demonstratie. Concluzia este evidenta conform Lemei 6.2.1 si definitiei anterioare.

Lema 6.2.3. Fie G un graf neorientat simplu cu n ≥ 3 noduri. Daca avem cl(G) = Kn, atunci Geste hamiltonian.

Demonstratie. Concluzia rezulta folosind lema anterioara si faptul ca graful complet Kn, n ≥ 3, esteevident hamiltonian (orice succesiune de forma [v1, v2, . . . , vn, v1] cu nodurile v1, . . . , vn distincte esteun ciclu hamiltonian ın Kn).

Observatia 6.2.5. Reciproca lemei anterioare nu este adevarata. De exemplu graful G reprezentat ınFigura 6.2.3 este hamiltonian, dar cl(G) = G = K6.


2

1

3

4

6 5

Figura 6.2.3:

Teorema 6.2.1 (Chvatal). Fie G = (V,E) un graf neorientat simplu cu n ≥ 3 noduri avand gradele

d1 ≤ d2 ≤ · · · ≤ dn.

Daca pentru orice k ∈ N� este verificata proprietatea

dk ≤ k <n

2⇒ dn−k ≥ n− k,

atunci G este hamiltonian.

Demonstratie. Se arata ca are loc egalitatea cl(G) = Kn si conform lemei anterioare rezulta astfel caG este hamiltonian.

Observatia 6.2.6. Daca graful G verifica ipoteza Teoremei lui Chvatal atunci cl(G) = Kn. Reciprocanu este adevarata. De exemplu, graful G din Exemplul 6.2.3 are cl(G) = Kn, dar nu verifica ipotezaTeoremei lui Chvatal (are gradele, ın ordine crescatoare, 2, 2, 3, 3, 4, 4, deci d2 ≤ 2 < n

2dar d4 < 4).

Astfel nici reciproca Teoremei lui Chvatal nu este adevarata.

Corolarul 6.2.1 (Teorema lui Bondy). Fie G un graf neorientat simplu cu n ≥ 3 noduri avandgradele

d1 ≤ d2 ≤ · · · ≤ dn.

Daca pentru orice p, q ∈ N� este verificata proprietatea

dp ≤ p, dq ≤ q, p = q ⇒ dp + dq ≥ n,


Demonstratie. Se arata ca graful G verifica ipoteza Teoremei lui Chvatal si astfel este hamiltonian.

Observatia 6.2.7. Teorema lui Chvatal generalizeaza Teorema lui Bondy. Aceasta generalizare estestricta. De exemplu, graful reprezentat ın Figura 6.2.4 are gradele, ın ordine crescatoare, 3, 3, 3, 4, 5, 5, 5, 6,deci verifica ipoteza Teoremei lui Chvatal dar nu verifica ipoteza Teoremei lui Bondy (d3 = 3 ≤ 3,d4 = 4 ≤4, dar d3 + d4 = 7 <n = 8).

Corolarul 6.2.2 (Teorema lui Posa). Fie G un graf neorientat simplu cu n ≥ 3 noduri avand gradele

d1 ≤ d2 ≤ · · · ≤ dn.

Daca {dk > k, ∀ k < n−1

2,

dk+1 > k, pentru k = n−12

si n = impar,



1

2 3

4

5

67

8

Figura 6.2.4:

Demonstratie. Se arata ca graful G verifica ipoteza Teoremei lui Bondy (corolarul anterior) si astfeleste hamiltonian.

Observatia 6.2.8. Teorema lui Bondy generalizeaza Teorema lui Posa. Generalizarea este stricta. Deexemplu, graful reprezentat ın Figura 6.2.5 are gradele, ordonate crescator, 2, 2, 4, 4, 4, 4, deci verificaipoteza Teoremei lui Bondy, dar nu verifica ipoteza Teoremei lui Posa.

1

2 3

4

56

Figura 6.2.5:

Corolarul 6.2.3 (Teorema lui Ore). Fie G = (V,E) un graf neorientat simplu cu n ≥ 3 noduri.Daca pentru orice doua noduri x, y distincte si neadiacente avem

d(x) + d(y) ≥ n,


Demonstratie. Se arata ca graful G verifica ipoteza Teoremei lui Posa (corolarul anterior) si astfeleste hamiltonian.

Observatia 6.2.9. Teorema lui Posa generalizeaza Teorema lui Ore. Aceasta generalizare este stricta.De exemplu, graful reprezentat ın Figura 6.2.6 are gradele, ordonate crescator, 2, 3, 3, 4, 4, 4, deciverifica ipoteza Teoremei lui Posa, dar nu verifica ipoteza Teoremei lui Ore.

Corolarul 6.2.4 (Teorema lui Dirac). Fie G = (V,E) un graf neorientat simplu cu n ≥ 3 noduri.Daca

d(x) ≥ n

2, ∀ x ∈ V,



Demonstratie. Se arata ca graful G verifica ipoteza Teorema lui Ore (corolarul anterior), deci estehamiltonian.

Observatia 6.2.10. Teorema lui Ore generalizeaza Teorema lui Dirac. Aceasta generalizare estestricta. De exemplu, graful reprezentat ın Figura 6.2.7 verifica ipoteza Teoremei lui Ore, dar nuverifica ipoteza Teoremei lui Dirac.

1

2 3

4

56

Figura 6.2.6:

1

2 3

4

56

Figura 6.2.7:

6.3 Grafuri bipartite

Definitia 6.3.1. Un graf G = (V,E) se numeste bipartit daca exista o partitie V = A∪B (A = ∅,B = ∅, A∩B = ∅) a.ı. fiecare muchie sau arc al grafului are o extremitate ın A si cealalta extremitateın B.

Exemplul 6.3.1. Graful reprezentat ın Figura 6.2.3 este bipartit, luand partitia nodurilor V ={1, 3, 5} ∪ {2, 4, 6}. O alta reprezentare a acestui graf bipartit, cu evidentierea partitiei nodurilorprin asezarea ın stanga a nodurilor din partea A = {1, 3, 5} si ın dreapta a nodurilor din parteaB = {2, 4, 6}, este data ın Figura 6.3.1.

Figura 6.3.1:

Teorema 6.3.1 (de caracterizare a grafurilor bipartite). Un graf cu n ≥ 2 noduri este bipartit dacasi numai daca nu contine cicluri de lungime impara.

Demonstratie. ”⇒” Fie G = (V,E) un graf bipartit avand partitia nodurilor V = A ∪ B ca ındefinitia anterioara. Orice ciclu al grafului G are una din formele [a1, b1, a2, b2, . . . , ak, bk, a1] sau[b1, a1, b2, a2, . . . , bk, ak, b1] cu a1, a2, . . . , ak ∈ A si b1, b2, . . . , bk ∈ B, deci are lungimea 2k.


”⇐” FieG = (V,E) un graf cu n ≥ 2 noduri ce nu contine cicluri de lungime impara. Demonstramca graful G este bipartit ın doua etape.

Etapa 1) Presupunem ca graful G este conex. Fie v ∈ V un nod arbitrar fixat. Pentru orice nodx ∈ V definim numarul d(v, x) ∈ N prin

d(v, x) = min{l(μ)|μ este lant de la v la x ın G},unde l(μ) reprezinta lungimea lantului μ. Definitia este corecta, deoarece graful este conex. Pentrugrafuri neorientate d(v, x) se numeste distanta de la v la x. Fie

A = {x ∈ V |d(v, x) = numar par} si B = {x ∈ V |d(v, x) = numar impar}.Evident, V = A∪B si A∩B = ∅. Deoarece d(v, v) = 0 rezulta ca v ∈ A, deci A = ∅. Fie v1 un nodvecin cu v (exista, deoarece graful este conex si are cel putin doua noduri). Atunci d(v, v1) = 1, deciv1 ∈ B si astfel B = ∅.

Demonstram prin reducere la absurd ca orice muchie (sau arc) a grafului are o extremitate ın A sicealalta extremitate ın B si astfel va rezulta ca graful este bipartit. Fie [x, y] ∈ E o muchie (sau arc)arbitrar fixata. Fie μ1 un lant de lungime minima de la v la x si μ2 un lant de lungime minima de la vla y, deci l(μ1) = d(v, x) si l(μ2) = d(v, y). Evident, lanturile μ1 si μ2 sunt elementare. Presupunemprin absurd ca x, y ∈ A sau x, y ∈ B, adica numerele d(v, x) si d(v, y) au aceeasi paritate. Atunci[x, y] nu apartine lantului μ1, deoarece ın caz contrar y ar fi penultimul nod al acestui lant si cum oricesublant (portiune) al unui lant de lungime minima este un lant de lungime minima ıntre extremitatilesale am avea d(v, y) = d(v, x)− 1, fals. Analog, [x, y] nu apartine nici lantului μ2. Fie

μ = [v, . . . , x, y, . . . , v]

lantul ınchis obtinut parcurgand ıntai lantul μ1 de la v la x, apoi muchia [x, y] si apoi lantul μ2 dela y la v. Avem

l(μ) = l(μ1) + 1 + l(μ2) = d(v, x) + 1 + d(v, y) = numar impar.

Deoarece muchia [x, y] nu apartine lanturilor μ1 si μ2, rezulta ca prin eliminarea din lantul ınchisμ a eventualelor portiuni comune L1, . . . , Lr ale lanturilor μ1 si μ2 ramane o multime nevida decicluri (elementare) muchie-disjuncte C1, . . . , Cs (iar muchia [x, y] apartine unuia din aceste cicluri).Folosind aceasta descompunere, lungimea lantului ınchis μ poate fi scrisa sub forma

l(μ) = 2l(L1) + · · ·+ 2l(Lr) + l(C1) + · · ·+ l(Cs).

Cum l(μ) este un numar impar, rezulta ca l(C1) + · · · + l(Cs) = numar impar, deci cel putin unuldin ciclurile C1, . . . , Cs are lungimea impara, contradictie cu ipoteza. Demonstratia prin reducere laabsurd este ıncheiata.

Etapa 2) Fie acum G un graf oarecare si G1 = (V1, E1), . . . , Gk = (Vk, Ek) componentele saleconexe. Deoarece G nu contine cicluri de lungime impara, rezulta ca si componentele sale conexeG1, . . . , Gk au aceasta proprietate. Conform etapei 1) rezulta ca toate componentele conexe Gi cu celputin doua noduri sunt grafuri bipartite. Pentru fiecare astfel de componenta conexa, fie Vi = Ai∪Bi

partitia corespunzatoare grafului bipartit Gi. Daca exista si componente conexe Gi cu un singur nod(adica cardVi = 1 si Ei = ∅, deoarece Gi nu contine bucle, buclele fiind cicluri de lungime 1), atuncipentru fiecare astfel de componenta conexa definim Ai = Vi, Bi = ∅ sau Bi = Vi, Ai = ∅. Fie

A = A1 ∪ · · · ∪ Ak si B = B1 ∪ · · · ∪Bk.

Atunci V = A ∪ B este o partitie si fiecare muchie sau arc al grafului G are o extremitate ın A sicealalta extremitate ın B, deci graful G este bipartit.


Exemplul 6.3.2. Graful reprezentat ın Figura 6.2.2 nu este bipartit, deoarece contine cicluri de lungimeimpara (de exemplu ciclul [1, 2, 3, 1] de lungime 3).

Corolarul 6.3.1. Orice graf bipartit conex G = (V,E) are o unica partitie V = A ∪ B ce verificaDefinitia 6.3.1.

Demonstratie. Pentru un nod v arbitrar fixat, submultimile A si B definite ın etapa 1) a demonstratieiteoremei anterioare determina unica partitie cu proprietatea ca v ∈ A. Intr-adevar, fie V = A′ ∪ B′

o partitie arbitrara ce verifica Definitia 6.3.1 si proprietatea v ∈ A′. Pentru orice nod x ∈ A existaμ = [v = v0, v1, . . . , v2k = x] lant de lungime minima de la v la x, deci avem, succesiv:

v = v0 ∈ A′, v1 ∈ B′, v2 ∈ A′, . . . , v2k = x ∈ A′.

Analog, pentru orice nod y ∈ B exista μ = [v = w0, w1, . . . , w2p+1 = y] lant de lungime minima de lav la y, deci avem, succesiv:

v = w0 ∈ A′, w1 ∈ B′, w2 ∈ A′, . . . , w2p+1 = y ∈ B′.

Rezulta ca A ⊆ A′ si B ⊆ B′. Cum B = V \ A si B′ = V \ A′ rezulta ca A = A′ si B = B′.

Observatia 6.3.1. Demonstratia teoremei anterioare este constructiva, indicand urmatorul algoritmde determinare daca un graf G este bipartit si, ın caz afirmativ, a unei partitii V = A ∪ B anodurilor sale.

• Se determina componentele conexe G1, . . . , Gk.

• Pentru fiecare componenta Gi = (Vi, Ei) cu cel putin doua noduri, se parcurg urmatoareleetape:

– Se fixeaza un nod vi ∈ Vi.

– Se calculeaza distantele d(vi, x) pentru toate nodurile x ∈ Vi. De exemplu,

d(vi, x) = lungimea lantului elementar unic de la vi la x ın arborele BF (vi)

(corespunzator parcurgerii BF a grafului neorientat G pornind din nodul vi; daca grafulG este orientat se parcurge graful neorientat obtinut prin eliminarea orientarii arcelor!).

– Se calculeaza multimile

Ai = {x ∈ Vi|d(vi, x) = numar par} si Bi = {x ∈ Vi|d(vi, x) = numar impar}.

– Daca exista o muchie (sau arc) de forma [x, y] ∈ Ei a.ı. x, y ∈ Ai sau x, y ∈ Bi, atuncicomponenta Gi nu este graf bipartit, deci nici graful G nu este bipartit si algoritmul seıncheie.

– In caz contrar componentaGi este graf bipartit si Vi = Ai∪Bi este partitia corespunzatoareacestui graf bipartit.

• Pentru fiecare componenta Gi = (Vi, Ei) cu cate un singur nod, adica Vi = {vi}, se parcurgurmatoarele etape:

– Daca [vi, vi] ∈ Ei (bucla), atunci graful G nu este bipartit si algoritmul se ıncheie.

– In caz contrar se calculeaza multimile Ai = Vi, Bi = ∅ pentru prima componenta Gi siBi = Vi, Ai = ∅ pentru urmatoarele componente Gi (se asigura astfel ca A = ∅ si B = ∅).


• Toate componentele conexe cu cel putin doua noduri sunt grafuri bipartite, iar toate compo-nentele conexe cu cate un singur nod nu contin bucle. Atunci graful G este bipartit si o partitiecorespunzatoare este V = A ∪B, cu A = A1 ∪ · · · ∪ Ak si B = B1 ∪ · · · ∪Bk.

Exemplul 6.3.3. Fie graful reprezentat ın Figura 6.2.1. Aplicam algoritmul din observatia anterioara.Fixand nodul v = 1 (pentru singura componenta conexa), obtinem distantele

d(1, 1) = 0, d(1, 2) = d(1, 5) = 1, d(1, 3) = d(1, 6) = 2, d(1, 4) = d(1, 7) = 3, d(1, 8) = 4,

deci A = {1, 3, 6, 8} si B = {2, 4, 5, 7}. Nu exista nicio muchie [x, y] a.ı. x, y ∈ A sau x, y ∈ B, decigraful dat este bipartit si unica partitie corespunzatoare este V = A ∪ B. O reprezentare a acestuigraf bipartit, cu evidentierea partitiei nodurilor, este data ın Figura 6.3.2.

Figura 6.3.2:

Tema 7

Distante si drumuri minime

Problema determinarii distantelor si drumurilor minime ıntre nodurile unui graf ponderat apare ınnumeroase aplicatii practice. In continuare vom prezenta doi algoritmi clasici pentru rezolvareaacestei probleme.

7.1 Expunerea problemei

Definitia 7.1.1. Fie (G, c) un graf ponderat, unde G = (V,E), V = {v1, . . . , vn} iar c : E → R+.

a) Daca μ = (x0, e1, x1, . . . , xk−1, ek, xk) este un drum al grafului G, unde x0, x1, . . . , xk ∈ V ,e1, . . . , ek ∈ E, k ∈ N, atunci costul (ponderea) lui μ este

c(μ) =

⎧⎨⎩

0, daca k = 0,k∑

i=1

c(ei), daca k ≥ 1

(adica suma costurilor arcelor sau muchiilor sale).

b) Fie x, y ∈ V . Un drum μ� = (x, . . . , y) ın graful G cu proprietatea ca

c(μ�) = min{c(μ)|μ este drum de la x la y ın G}

se numeste drum minim (drum de cost minim, drum de pondere minima) de la x lay ın graful ponderat (G, c). Costul c(μ�) al acestui drum minim se numeste distanta minimade la x la y ın graful (G, c).

Observatia 7.1.1. Eliminand eventualele circuite C1, . . . , Cp dintr-un drum μ de la nodul x la nodul

y obtinem un drum elementar μ′ de la x la y cu proprietatea ca c(μ′) = c(μ)−p∑

k=1

c(Ck) ≤ c(μ).

Daca drumul μ este minim atunci si drumul elementar μ′ este minim si c(e) = 0 pentru oricemuchie sau arc e al circuitelor C1, . . . , Cp. Deci existenta unui drum minim de la x la y implicaexistenta unui drum minim elementar de la x la y. Astfel distanta minima de la x la y poate ficonsiderata ca fiind costul minim al unui drum elementar de la x la y. Mai mult, daca functia costc este strict pozitiva, atunci orice drum minim este elementar.

Observatia 7.1.2. Multimea drumurilor elementare fiind evident finita, avem echivalenta: exista dru-muri minime de la x la y daca si numai daca exista drumuri de la x la y.

Observatia 7.1.3. Distanta minima de la un nod x la el ınsusi este egala cu zero, drumul minimelementar de la x la x fiind drumul de lungime zero, μ = (x).

73

TEMA 7. DISTANTE SI DRUMURI MINIME 74

Observatia 7.1.4. Daca μ = (x0, x1, . . . , xk) este un drum minim de la x0 la xk, atunci orice subdrumμ′ = (xi, xi+1, . . . , xj) (0 ≤ i ≤ j ≤ k) al sau este un drum minim de la xi la xj (principiuloptimalitatii al lui Bellman). Afirmatia poate fi justificata usor prin reducere la absurd.

Exemplul 7.1.1. Fie graful ponderat (G, c) reprezentat ın Figura 7.1.1.

4

10

105 5

5

5

5

5

15

53

1

2

Figura 7.1.1:

Drumurile elementare de la nodul 1 la nodul 5 sunt μ1 = (1, 3, 5), avand costul c(μ1) = 10+5 = 15,μ2 = (1, 4, 5), avand costul c(μ2) = 5 + 5 = 10, deci μ2 este un drum minim de la 1 la 5. Astfeldistanta minima de la nodul 1 la nodul 5 este c(μ2) = 10.

Definitia 7.1.2. Fie (G, c) un graf ponderat, unde G = (V,E), V = {v1, . . . , vn}, c : E → R+.

a) Matricea distantelor (costurilor) directe asociata grafului (G, c) este matricea C = (cij)i,j=1,n

definita prin

cij =

⎧⎨⎩

0, daca i = j,min{c(e)|e = (vi, vj) ∈ E}, daca i = j si ∃ (vi, vj) ∈ E,∞, daca i = j si ∃ (vi, vj) ∈ E

(pentru grafuri neorientate (vi, vj) desemnand de fapt muchia [vi, vj]).

b) Matricea distantelor (costurilor) minime asociata grafului (G, c) este matricea C� =(c�ij)i,j=1,n definita prin

c�ij =

⎧⎨⎩

c(μ�), μ� = drum minim de la vi la vj,daca ∃ μ = (vi, . . . , vj) drum ın G,

∞, ın caz contrar.

Observatia 7.1.5. Evident, pentru orice graf neorientat atat matricea distantelor directe cat si ma-tricea distantelor minime sunt matrice simetrice.

Observatia 7.1.6. Conform Observatiei 7.1.1, putem sa ınlocuim termenul de ”drum” cu cel de ”drumelementar” ın definitia anterioara.

Conform Observatiei 7.1.2, punctul b) din definitia anterioara este o extindere a definitiei distanteiminime de la punctul b) al Definitiei 7.1.1.

Conform Observatiei 7.1.3, c�ii = 0 ∀ i ∈ {1, . . . , n}.


Exemplul 7.1.2. Matricele distantelor directe, respectiv minime asociate grafului din Exemplul 7.1.1sunt

C =

⎛⎜⎜⎜⎜⎝

0 15 10 5 ∞∞ 0 ∞ ∞ ∞∞ 5 0 ∞ 5∞ 10 ∞ 0 55 5 ∞ ∞ 0

⎞⎟⎟⎟⎟⎠ , C� =

⎛⎜⎜⎜⎜⎝

0 15 10 5 10∞ 0 ∞ ∞ ∞10 5 0 15 510 10 20 0 55 5 15 10 0

⎞⎟⎟⎟⎟⎠ .

7.2 Algoritmul Dijkstra

Vom expune un algoritm pentru determinarea distantelor minime si a drumurilor minime de la unnod fixat, numit si nod sursa, la toate nodurile grafului ponderat dat.

Algoritmul 7.2.1 (Dijkstra). Fie (G, c) un graf ponderat, G = (V,E), V = {v1, v2, . . . , vn}, c : E →R+. Fie C = (cij)i,j=1,n matricea distantelor directe asociata grafului (G, c) si fie vs ∈ V un nodarbitrar fixat, numit nod sursa. Distantele minime de la nodul vs la nodurile grafului sunt calculatesi memorate ıntr-un vector t = (t1, . . . , tn) astfel:

• La pasul 1 se selecteaza nodul sursa vs si se ia ts = 0;

• La pasul k, 2 ≤ k ≤ n, se cunosc nodurile vi1 , . . . , vik−1selectate la pasii anteriori si distantele

corespondente ti1 , . . . , tik−1.

a) Daca nu mai exista nici-o muchie sau arc de la un nod selectat vj ∈ {vi1 , . . . , vik−1} la

un nod neselectat vi ∈ V \ {vi1 , . . . , vik−1}, atunci se ia ti = ∞ pentru orice nod neselectat

vi ∈ V \ {vi1 , . . . , vik−1} si algoritmul se ıncheie.

b) In caz contrar se selecteaza un nod vik ∈ V \ {vi1 , . . . , vik−1} cu proprietatea ca exista un

nod selectat vjk∈ {vi1 , . . . , vik−1

} astfel ıncat

tjk+ cjkik = min{tj + cji|vj ∈ {vi1 , . . . , vik−1

}, vi ∈ V \ {vi1 , . . . , vik−1}}. (7.2.1)

Se ia

tik = tjk+ cjkik (7.2.2)

si se trece la pasul k + 1.

Observatia 7.2.1. Evident, algoritmul executa cel mult n pasi.

Teorema 7.2.1 (de corectitudine a Algoritmului Dijkstra). In contextul Algoritmului Dijkstra, avem

ti = c�si, ∀ i ∈ {1, . . . , n}(adica distanta ti calculata de algoritm este chiar distanta minima de la vs la vi).

Demonstratie. Vom demonstra prin inductie dupa k ca nodul vik selectat la pasul k si distantacorespondenta tik calculata la acel pas verifica egalitatea din enunt, adica

tik = c�sik ,

si, ın plus, tik <∞.Pentru k = 1 afirmatia este evidenta deoarece

vi1 = vs, ti1 = 0 = c�ss.


Presupunem adevarata afirmatia pentru orice pas mai mic decat k si o demonstram pentru pasulk. Fie vjk

∈ {vi1 , . . . , vik−1} un nod ce verifica egalitatea (7.2.1). Din descrierea algoritmului si din

ipoteza de inductie (nodul vjkfiind selectat la un pas anterior), rezulta ca tjk

= c�sjk<∞ si cjkik <∞,

deci tik <∞ (conform (7.2.2)).Daca (vs, . . . , vjk

) este un drum minim de la vs la vjk(exista, deoarece c�sjk

< ∞), atunci μ =(vs, . . . , vjk

, vik) este un drum de la vs la vik , avand costul c(μ) = c�sjk+ cjkik = tjk

+ cjkik = tik(conform (7.2.2)), deci

c�sik ≤ tik <∞. (7.2.3)

Rezulta ca exista drumuri minime de la vs la vik . Fie

μ� = (vs = x0, x1, . . . , xp−1, xp = vik)

un drum elementar minim de la vs la vik . Fie l ∈ {0, 1, . . . , p − 1} indicele maxim astfel ıncatxl ∈ {vi1 , . . . , vik−1

} (exista, deoarece x0 = vs = vi1).Fie xl = vir , 1 ≤ r ≤ k − 1, si fie xl+1 = viq , q ≥ k.Din descrierea pasului q al algoritmului, conform relatiilor (7.2.1) si (7.2.2) rezulta ca

tiq ≤ tir + ciriq ,

iar conform ipotezei de inductie pentru r avem

tir = c�sir <∞.Deci

tiq ≤ c�sir + ciriq = c�siq (7.2.4)

(conform principiului optimalitatii al lui Bellman pentru subdrumurile dintre x0 = vs si xl = vir ,respectiv dintre x0 = vs si xl+1 = viq ale drumului minim μ�).

Cazul 1) Daca l = p − 1. atunci xl+1 = vik , deci q = k si din (7.2.3) si (7.2.4) rezulta catik = c�sik <∞.

Cazul 2) Daca l < p− 1, deci q = k, demonstram ca

tik = c�sik

prin reducere la absurd. Intr-adevar, ın caz contrar conform (7.2.3) am avea c�sik < tik .Cum q > k, din descrierea algoritmului avem tiq ≥ tik (deoarece valorile tik sunt monoton

crescatoare de la un pas la altul, inductie!). Utilizand (7.2.4) am obtine

c�sik < tik ≤ tiq ≤ c�siq ,

ceea ce contrazice faptul ca are loc inegalitatea c�siq ≤ c�sik (conform principiului optimalitatii al luiBellman pentru subdrumul dintre vs si viq al drumului minim μ�).

Demonstratia prin inductie este ıncheiata.Evident, pentru orice nod vi ramas neselectat ın urma executarii ultimului pas al algoritmului

avem ti =∞ = c�si.Intr-adevar, daca ar exista un drum elementar minim

μ = (vs = y0, y1, . . . , yp = vi),

luand l ∈ {0, 1, . . . , p − 1} indicele maxim pentru care yl este selectat (exista, deoarece y0 = vs esteselectat) atunci yl+1 ar fi neselectat desi exista o muchie sau un arc de la yl la yl+1, contradictie cudescrierea modului de ıncheiere a algoritmului.


Exemplul 7.2.1. Pentru graful ponderat din Exemplul 7.1.1, luand ca nod sursa nodul 1, aplicareaAlgoritmului Dijkstra este evidentiata ın urmatorul tabel:

Pas Nodul selectat Distanta minima1 1 02 4 53 3 104 5 105 2 15

De exemplu, la pasul 3 avem deja selectate nodurile i1 = 1 si i2 = 4, cu distantele minime t1 = c�11 = 0si t4 = c�14 = 5. Se selecteaza nodul i3 = 3, cu distanta minima t3 = 10, deoarece

min{t1 + c12, t1 + c13, t1 + c15, t4 + c42, t4 + c43, t4 + c45}= min{0 + 15, 0 + 10, 0 +∞, 5 + 10, 5 +∞, 5 + 5} = 10 = t1 + c13.

Observatia 7.2.2. Algoritmul Dijkstra este specific metodei de programare Greedy, el selectandnodurile ın ordinea crescatoare a distantei fata de nodul sursa.

Observatia 7.2.3. Pentru implementarea Algoritmului Dijkstra, consideram ca V = {1, . . . , n} si canodul sursa este s ∈ V . Utilizam un vector S avand semnificatia

S[i] =

{1, daca nodul i a fost selectat,0, ın caz contrar,

∀ i ∈ {1, . . . , n}

si un vector t avand semnificatiat[i] = distanta minima de la nodul sursa s la nodul i, ∀ i ∈ {1, . . . , n},

calculat conform (7.2.1) si (7.2.2).Pentru determinarea drumurilor minime de la nodul s la nodurile grafului vom utiliza si un vector

TATA avand semnificatiaTATA[i] = nodul j ce este predecesorul direct al nodului i pe drumul minim de la s la i,

∀ i ∈ {1, . . . , n}.Daca i = ik este nodul selectat la pasul k, atunci j = jk se determina conform egalitatii (7.2.1).Descrierea ın pseudocod a algoritmului are forma urmatoare.

Dijkstra(s) :{ pentru i = 1, n// initializari{ S[i]← 0; t[i]←∞; TATA[i]←∞;}t[s]← 0; TATA[s]← 0;//s este nodul sursarepeta{ min←∞;//selectam urmatorul nod x, ın ordinea crescatoare a

//distantelor minime de la s la xpentru i = 1, n{ daca (S[i] = 0) si (t[i] < min){ min← t[i]; x← i;}

}daca (min <∞)// exista x, ıl selectam{ S[x]← 1;

pentru i = 1, n// actualizam vectorii t si TATA{ daca (S[i] = 0) si (cxi <∞){ daca (t[i] > t[x] + cxi)


{ t[i]← t[x] + cxi; TATA[i]← x;}

}}

}}cat timp (min <∞);

}.Observatia 7.2.4. Implementarea anterioara necesita O(n2) operatii (deoarece blocul ”repeta” seexecuta de cel mult n ori si necesita de fiecare data cel mult n comparatii pentru determinareanodului selectat x si cel mult n comparatii si n adunari pentru actualizarea vectorilor t si TATA).Aceasta este de fapt si complexitatea Algoritmului Dijkstra (ın implementarea optima).

7.3 Algoritmul Roy-Floyd

Vom expune un algoritm pentru determinarea distantelor minime si a drumurilor minime ıntre oricedoua noduri ale grafului ponderat dat. Acest algoritm este asemanator cu Algoritmul Roy-Warshallpentru determinarea matricei drumurilor.

Algoritmul 7.3.1 (Roy-Floyd). Fie (G, c) un graf ponderat, G = (V,E), V = {v1, v2, . . . , vn},c : E → R+. Fie C = (cij)i,j=1,n matricea distantelor directe asociata grafului (G, c). Se calculeazamatricele

C(k) = (c(k)ij )i,j=1,n, k ∈ {0, 1, . . . , n}

definite prin

C(0) = C, (7.3.1)

c(k)ij = min{c(k−1)

ij , c(k−1)ik + c

(k−1)kj }, ∀k, i, j ∈ {1, . . . , n}. (7.3.2)

Teorema 7.3.1 (de corectitudine a Algoritmului Roy-Floyd). In contextul Algoritmului Roy-Floyd,ultima matrice calculata este chiar matricea distantelor minime asociata grafului (G, c), adica

C(n) = C�.

Demonstratie. Vom demonstra prin inductie dupa k ∈ {0, 1, . . . , n} ca pentru orice i, j ∈ {1, . . . , n}avem

c(k)ij =

⎧⎨⎩

min{c(μ)|μ = (vi, . . . , vj), I(μ) ⊆ {v1, . . . , vk}}, daca∃ μ = (vi, . . . , vj) drum cu I(μ) ⊆ {v1, . . . , vk},

∞, ın caz contrar,(7.3.3)

unde I(μ) reprezinta multimea nodurilor intermediare ale drumului μ si {v1, . . . , vk} reprezintamultimea {vi|1 ≤ i ≤ k}, deci pentru k = 0 aceasta multime este ∅.

Pentru k = 0 avem c(0)ij = cij (conform (7.3.1)) si egalitatea (7.3.3) este evidenta din definitia

matricei C a costurilor directe si faptul ca I(μ) = ∅ ınseamna ca drumul μ este de fapt un arc sau omuchie pentru i = j, respectiv ca μ este o bucla sau drumul (vi) de lungime 0 pentru i = j.

Presupunem acum egalitatea (7.3.3) adevarata pentru k− 1 (1 ≤ k ≤ n) si o demonstram pentruk. Fie d ∈ [0,∞). Folosind (7.3.2), ipoteza de inductie si principiul optimalitatii al lui Bellman avem


echivalentele:

c(k)ij = d⇔ c

(k−1)ij = d ≤ c

(k−1)ik + c

(k−1)kj sau c

(k−1)ik + c

(k−1)kj = d < c

(k−1)ij

⇔ ∃ μ = (vi, . . . , vj) drum minim cu proprietatea ca I(μ) ⊆ {v1, . . . , vk−1}(adica de cost minim dintre toate drumurile de la vi la vj ce satisfac aceasta

proprietate), c(μ) = d ≤ c(μ1) + c(μ2) ∀ μ1 = (vi, . . . , vk), μ2 = (vk, . . . , vj)

drumuri cu I(μ1), I(μ2) ⊆ {v1, . . . , vk−1)

sau

∃ μ′1 = (vi, . . . , vk), μ

′2 = (vk, . . . , vj) drumuri minime cu proprietatea ca

I(μ′1), I(μ

′2) ⊆ {v1, . . . , vk−1}, c(μ′

1) + c(μ′2) = d < c(μ”), ∀ μ” = (vi, . . . , vj)

drum cu I(μ”) ⊆ {v1, . . . , vk−1}⇔ ∃ μ = (vi, . . . , vj) drum minim cu proprietatea ca

I(μ) ⊆ {v1, . . . , vk}, vk ∈ I(μ), c(μ) = d

sau

∃ μ′ = (vi, . . . , vk, . . . , vj) drum minim cu proprietatea ca

I(μ′) ⊆ {v1, . . . , vk}, vk ∈ I(μ′), c(μ′) = d

(μ′ se obtine parcurgand ıntai μ′1, apoi μ′

2 si, reciproc,

μ′1 si μ′

2 sunt portiunile din μ′ dintre vi si prima aparitie a lui vk ın I(μ′),

respectiv dintre ultima aparitie a lui vk ın I(μ′) si vj; ıntre aceste aparitii

eventualele arce sau muchii ale lui μ′ au costul 0 conform Observatiei 7.1.1)

⇔ ∃ μ = (vi, . . . , vj) drum minim cu proprietatea ca

I(μ) ⊆ {v1, . . . , vk}, c(μ) = d.

Demonstratia prin inductie a egalitatii (7.3.3) este astfel ıncheiata.Pentru k = n conditia I(μ) ⊆ {v1, . . . , vn} poate fi eliminata, fiind ıntotdeauna adevarata, deci

din (7.3.3) si Definitia 7.1.2 obtinem c(n)ij = c�ij, ∀ i, j ∈ {1, . . . , n}, adica egalitatea din enunt.

Observatia 7.3.1. Algoritmul Roy-Floyd are complexitatea O(n3) (deoarece necesita cate o adunaresi o comparatie pentru fiecare triplet (k, i, j), cu k, i, j ∈ {1, . . . , n}).Exemplul 7.3.1. Pentru graful din Exemplul 7.1.1, prin aplicarea Algoritmului Roy-Floyd obtinemmatricele:

C(0) = C =

⎛⎜⎜⎜⎜⎝

0 15 10 5 ∞∞ 0 ∞ ∞ ∞∞ 5 0 ∞ 5∞ 10 ∞ 0 55 5 ∞ ∞ 0

⎞⎟⎟⎟⎟⎠ ; C(1) =

⎛⎜⎜⎜⎜⎝

0 15 10 5 ∞∞ 0 ∞ ∞ ∞∞ 5 0 ∞ 5∞ 10 ∞ 0 55 5 15 10 0

⎞⎟⎟⎟⎟⎠


(deoarece, de exemplu, c(1)53 = min{c(0)

53 , c(0)51 + c

(0)13 } = min{∞, 5 + 10} = 15);

C(2) =

⎛⎜⎜⎜⎜⎝

0 15 10 5 ∞∞ 0 ∞ ∞ ∞∞ 5 0 ∞ 5∞ 10 ∞ 0 55 5 15 10 0

⎞⎟⎟⎟⎟⎠ ; C(3) =

⎛⎜⎜⎜⎜⎝

0 15 10 5 15∞ 0 ∞ ∞ ∞∞ 5 0 ∞ 5∞ 10 ∞ 0 55 5 15 10 0

⎞⎟⎟⎟⎟⎠ ;

C(4) =

⎛⎜⎜⎜⎜⎝

0 15 10 5 10∞ 0 ∞ ∞ ∞∞ 5 0 ∞ 5∞ 10 ∞ 0 55 5 15 10 0

⎞⎟⎟⎟⎟⎠ ; C(5) =

⎛⎜⎜⎜⎜⎝

0 15 10 5 10∞ 0 ∞ ∞ ∞10 5 0 15 510 10 20 0 55 5 15 10 0

⎞⎟⎟⎟⎟⎠ = C�

(matricea distantelor minime).

Observatia 7.3.2. Conform ecuatiilor (7.3.3), Algoritmul Roy-Floyd este un algoritm specific metodeiprogramarii dinamice.

Conform ecuatiilor (7.3.2) avem c(k)ik = c

(k−1)ik si c

(k)kj = c

(k−1)kj , ∀ k, i, j ∈ {1, . . . , n}, deci pentru imple-

mentarea algoritmului putem utiliza o singura matrice C(k). Astfel obtinem urmatoarea descriere ınpseudocod a algoritmului.Roy Floyd :{ pentru i = 1, n

pentru j = 1, n c�ij ← cij;//initializare

pentru k = 1, npentru i = 1, n

pentru j = 1, ndaca (c�ik + c�kj < c�ij) c�ij ← c�ik + c�kj;

}.Considerand ca functia cost c este strict pozitiva, pentru determinarea tuturor drumurilor minime

(elementare) dintre doua noduri distincte x, y putem utiliza echivalenta:

(x, z, . . . , y) = drum minim ⇔{z = x,cxz + c�zy = c�xy,

unde multimea nodurilor este multimea standard V = {1, . . . , n}.Astfel putem determina toate nodurile z ce sunt succesori directi ai nodului x pe drumuri minime

de la x la y, si continuand acest procedeu pentru subdrumurile minime dintre z si y se gasesc toatedrumurile minime elementare de la x la y.

Tema 8

Fluxuri ın retele de transport

8.1 Problema fluxului maxim

8.2 Algoritmul Ford-Fulkerson

81

Date post:	05-Jul-2015
Category:	Documents
Upload:	nicolae-mihai
View:	1,953 times
Download:	5 times

Alg_graf

Documents