cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. notat˘ii generale....

60
Cuprins 1 Not ¸iuni preliminare ¸ si scurt istoric 3 1.1 Scurt istoric ......................................... 3 1.2 Structura cursului ..................................... 3 1.3 Notat ¸ii generale. Not ¸iuni recapitulative de combinatoric˘ a ............... 4 2 Grafuri, digrafuri, multigrafuri ¸ si grafuri generale 7 2.1 Teorie ............................................ 7 2.2 Problema s˘ apt˘ amˆ anii .................................... 10 2.3 Seminar ........................................... 10 3 Subgrafuri ¸ si morfisme de grafuri 13 3.1 Teorie ............................................ 13 3.1.1 Operat ¸ii cu subgrafuri ............................... 14 3.1.2 Propriet˘ at ¸i ..................................... 15 3.2 Problema s˘ apt˘ amˆ anii .................................... 16 3.3 Seminar ........................................... 16 4 Grade ¸ si semigrade 17 4.1 Teorie ............................................ 17 4.2 Problema s˘ apt˘ amˆ anii .................................... 20 4.3 Seminar ........................................... 20 5 Drumuri, cicluri ¸ si circuite 21 5.1 Teorie ............................................ 21 5.1.1 Conexitate ..................................... 22 5.2 Problema s˘ apt˘ amˆ anii .................................... 22 5.3 Seminar ........................................... 22 6 Conexitate 23 6.1 Teorie ............................................ 23 6.2 Problema s˘ apt˘ amˆ anii .................................... 24 6.3 Seminar ........................................... 24 7 Clase importante de grafuri 25 7.1 Teorie ............................................ 26 7.2 Problema s˘ apt˘ amˆ anii .................................... 28 7.3 Seminar ........................................... 28 1

Upload: others

Post on 20-Oct-2019

8 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cuprins

1 Notiuni preliminare si scurt istoric 3

1.1 Scurt istoric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Structura cursului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Notatii generale. Notiuni recapitulative de combinatorica . . . . . . . . . . . . . . . 4

2 Grafuri, digrafuri, multigrafuri si grafuri generale 7

2.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Subgrafuri si morfisme de grafuri 13

3.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1.1 Operatii cu subgrafuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.1.2 Proprietati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 Grade si semigrade 17

4.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5 Drumuri, cicluri si circuite 21

5.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.1.1 Conexitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

6 Conexitate 23

6.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

7 Clase importante de grafuri 25

7.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

7.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

7.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1

Page 2: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CUPRINS CUPRINS

8 Arbori. Arbori partiali 298.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

9 Arbori partiali de cost minim. Algoritmul lui Kruskal/Prim 339.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

10 Probleme de numarare a arborilor 3910.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3910.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4010.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

11 Algoritmi de cautare 4111.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4111.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4111.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

12 Probleme de drum minim (maxim) 4312.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4312.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4612.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

13 Algoritmii lui Dantzig si Ford, Dijkstra, Floyd si Warshall 4713.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4713.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4913.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

14 Metoda drumului critic 5114.1 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5114.2 Problema saptamanii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5314.3 Seminar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

15 Diagrame 55

2

Page 3: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 1

Notiuni preliminare si scurt istoric

1.1 Scurt istoric . . . . . . . . . . . . 31.2 Structura cursului . . . . . . . . 31.3 Notatii generale. Notiuni recapi-

tulative de combinatorica . . . . 4

1.1 Scurt istoric

Claude Berge (1926-2002) a fost un matematician francez, recunoscut drept unul din fondatoriicombinatoricii si teoriei grafurilor. Acesta a jucat un rol major ın renasterea combinatoricii, iar ınteoria grafurilor a ramas cunoscut pentru conjectura grafurilor perfecte, rezolvata dupa cateva lunide la moartea sa.

1.2 Structura cursului

Scopul cursului consta ın parcurgerea notiunilor de baza legate de grafuri si prezentarea catorvarezultate fundamentale ce au fost de mare folos ın rezolvarea problemelor teoretice sau practice.Pe scurt, vom parcurge urmatoarele aspecte:

♦ Notiuni fundamentale

�1 Grafuri, digrafuri, multigrafuri si grafuri generale

�2 Metode de reprezentare a grafurilor si digrafurilor

�3 Subgrafuri si morfisme de grafuri

�4 Grade si semigrade

�5 Drumuri, cicluri si circuite

�6 Conexitate

�7 Clase importante de grafuri: grafuri complete, grafuri planare, grafuri bipartite,grafuri regulate.

♦ Arbori

�1 Arbori. Arbori partiali

�2 Arbori partiali de cost minim. Algorimii lui Kruskal/ Prim

�3 Probleme de numarare a arborilor

♦ Probleme de drum ın grafuri si digrafuri

�1 Algoritmi de cautare

�2 Probleme de drum minim (maxim)

�3 Algorimii lui Dantzig si Ford, Dijkstra, Floyd si Warshall

�4 Metoda drumului critic.

3

Page 4: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

1.3. NOTATII GENERALE. NOTIUNI RECAPITULATIVE DE COMBINATORICACURSUL 1. NOTIUNI PRELIMINARE SI SCURT ISTORIC

1.3 Notatii generale. Notiuni recapitulative de combinatorica

Vom nota prin N multimea numerelor naturale

N := {0, 1, 2, . . . , n, . . .} ,

iar pentru i ∈ N, notam N≥i := {i, i+ 1, . . .}. Vom obisnui sa mai notam

[n] := {1, 2, . . . , n} si [n]0 := {0, 1, 2, . . . , n} ,

iar pentru n = 0, facem conventia [0] := ∅.Oricare ar fi x, y ∈ R notam

x ∧ y := min {x, y} si x ∨ y := max {x, y} .

Oricare ar fi x ∈ R si k ∈ N definim functia factorial descrescator

[x]k := x (x− 1) (x− 2) · . . . · (x− k + 1) =: xk,

si functia factorial crescator

[x]k := x (x+ 1) (x+ 2) · . . . · (x+ k − 1) =: xk,

iar pentru k = 0 consideram prin conventie [x]0 = [x]0 = 1.Vom nota prin ∑

i

x1 · . . . · xi

suma tuturor produselor de cate i numere din n numere x1, x2, . . . , xn, unde n ∈ N.Pe tot parcursului cursului vom lucra doar cu multimi finite. Data o multime finita A, vom nota

cu |A| cardinalul acesteia. Pentru doua multimi finite A,B vom nota cu F (A,B) multimea tuturorfunctiilor definite pe A cu valori ın B. Pe multimea F (A,B) definim relatia de echipotenta prin

A ∼ B :⇔ ∃f ∈ F (A,B) , f functie bijectiva.

Putem defini acum notiunea de multime finita prin

Definitia 1 O multime A se numeste finita daca este vida sau daca este echipotenta cu multimea{1, 2, . . . , n}. O multimea este inifnita daca nu este finita.

Teorema 2 Daca o multime este finita, atunci aceasta nu este echipotenta cu nici o submultimeproprie a sa.

Legat de multimile A si B vom folosi deseori

incluziunea A ⊆ B :⇔ (x ∈ A⇒ x ∈ B)reuniunea A ∪B := {x | x ∈ A sau x ∈ B}intersectia A ∩B := {x | x ∈ A si x ∈ B}diferenta A−B := {x | x ∈ A si x 6∈ B}reuniunea disjucta A tB := (A ∪B)− (A ∩B)diferenta simetrica A∆B := (A−B) ∪ (B −A) .

Oricarei functii f : A → B, unde A = {a1, a2, . . . , am} si B = {b1, b2, . . . , bn} ,m, n ∈ N∗, ıiputem asocia o aranjarea a obiectelor din A, ın casutele din B astfel ıncat

casuta bi = {a ∈ A | f (a) = bi} .

Aceasta corespondenta este o bijectie. Mai mult, putem stabili o corespondenta bijectiva ıntremultimea F (A,B) si multimea m−uplelor formate cu elemente din B sau a cuvintelor de m litereformate cu litere din multimea B :

F (A,B) 3 f 7−→ f (a1) f (a2) . . . f (am) ,

unde ordinea literelor este vitala. Deci, avem ca

4

Page 5: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 1. NOTIUNI PRELIMINARE SI SCURT ISTORIC1.3. NOTATII GENERALE. NOTIUNI RECAPITULATIVE DE COMBINATORICA

Propozitia 3 Cardinalul multimii F (A,B) este nm.

Se numeste permutare a multimii A = {a1, a2, . . . , am} orice aplicatie bijectiva σ : A → A.Vom nota multimea tuturor permutarilor multimii A cu

Sm = {σ ∈ F (A,A) | σ functie bijectiva} .

O partitie a multimii A este o descompunere de forma

A = A1 tA2 t . . . t Ak.

Dat un numar k ∈ N, 1 ≤ m ≤ n, unde m = |A| , se numeste aranjament de n elementeluate cate m orice submultime ordonata alcatuita din m elemente ale lui A. Cu alte cuvinte,un aranjament de n elemente luate cate m este un cuvant de lungime m format cu litere diferitedin multimea B, iar numarul lor este

[n]m := Amn =n!

(n−m)!.

Orice aranjament poate fi privit ca o functie injectiva, iar un aranjament de m elemente luate catem se numeste permutare. Astfel, orice permutare poate fi privit ca o functie bijectiva.

Observatia 4 Numarul de posibilitati de a introduce m bile, numerotate de la 1 la m, ın n urne,numerotate de la 1 la n, este egal cu [n]m. Numarul functiilor injective f : A→ B este egal cu[n]m. De vreme ce, ın cazul finit, o functie injectiva este tot una cu o functie bijectiva deducem canumarul functiilor [m]m = m!.

Daca multimea B este o multimea ordonata astfel ıncat b1 < . . . < bn, un cuvant de lungime nformat cu litere din B, bi1bi2 . . . bik se numeste crescator daca

bi1 ≤ bi2 ≤ . . . ≤ bik ,

si strict crescator daca inegalitatile de mai sus sunt stricte. Cuvintele strict crescatoare de lungimem formate cu n simboluri se mai numesc combinari de n luate cate m, iar cele crescatoare senumesc combinari cu repetitii de n luate cate m.

Numarul de combinari de n luate cate m, respectiv, numarul de combinari cu repetitii de nluate cate m este (

n

m

):=

[n]mm!

=n!

m! (n−m)!, respectiv, r

(n

m

):=

[n]m

m!.

Numarul

(n

m

)se numeste numar binomial si este egal si cu numarul submultimilor cu m elemente

ale unei multimi cu n elemente. Au loc formulele de calcul(n

m

)=

(n− 1

m

)+

(n− 1

m− 1

), ∀a, b ∈ C : (a+ b)n =

n∑k=0

(n

k

)akbn−k.

Oricare ar fi p multimile finite A1, A2, . . . , Ap are loc principiul includerii si excluderii

|A1 ∪A2 ∪ . . . ∪ Ap| =∑|Ai|−

∑|Ai ∩Aj |+

∑|Ai ∩Aj ∩Ak|−. . .+

∑(−1)p |A1 ∩ . . . ∩ Ap| .

Cu ajutorul acestui principiu se poate stabili ca numarul functiilor surjective f : A →B, |A| = m, |B| = n,m, n ∈ N∗,m ≥ n este egal cu

nm −(n

1

)(n− 1)m +

(n

2

)(n− 2)m −

(n

3

)(n− 3)m + . . .+ (−1)n−1

(n

n− 1

).

5

Page 6: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

1.3. NOTATII GENERALE. NOTIUNI RECAPITULATIVE DE COMBINATORICACURSUL 1. NOTIUNI PRELIMINARE SI SCURT ISTORIC

Numim functie generatoare asociata unui sir de numere (an) ca fiind suma seriei

∞∑n=0

anxn,

ın ipoteza ın care seria este convergenta pe R sau pe o submultime a sa.Numarul lui Catalan reprezinta numarul de moduri ın care se pot pune parantezele ıntr-un

produs neasociativ de n factori, scrisi ın ordinea a1, . . . , an. Acest numar se poate calcula cuajutorul formulei

∀n ∈ N∗ : T (n) :=1

n

(2n− 2

n− 1

).

6

Page 7: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 2

Grafuri, digrafuri, multigrafuri si grafuri generale

2.1 Teorie . . . . . . . . . . . . . . . 72.2 Problema saptamanii . . . . . . . 102.3 Seminar . . . . . . . . . . . . . . 10

2.1 Teorie

Fie V o multime nevida si finita, i.e. V = {v1, v2, . . . , vn} , n ∈ N∗. Multimea partilor multimii V ovom nota cu P (V ), iar multimea partilor multimii V alcatuite din 2 elemente, respectiv, multimeaperechilor ordonate formate cu elemente din X o vom nota cu

P2 (V ) := {Y ⊆ V | |Y | = 2} , respectiv,−−−−→P2 (V ) := {(x, y) | x, y ∈ V, x 6= y} .

Tinand cont de formulele de calcul din Cursul 0, putem stabili urmatoarea

Propozitia 5 Daca V 6= ∅ si |V | = n, atunci

|P (V )| = 2n, |P2 (V )| = 2C2n =

√2n(n−1),

∣∣∣−−−−→P2 (V )∣∣∣ = 2n(n−1). (2.1)

Definitia 6 Se numeste graf neorientat o perechea ordonata de multimi G = (V,E) , unde Veste o multimi nevida, finita si E ⊆ P2 (V ).

Elementele multimii V se numesc varfuri (vertices) sau noduri ale grafului G, iar elementelelui E se numesc muchii (edges). Ordinul grafului G = (V,E), notat cu o (G) , reprezinta cardinalulmultimii V , iar dimensiunea grafului G, notata cu dimG, reprezinta cardinalul multimii E. Datao muchie e = {u, v} ∈ E, u, v se numesc extremitatile muchiei si o vom mai nota cu [u, v]. Maimult, daca [u, v] ∈ E, spunem ca varfurile u, v sunt adiacente ın graful G si incidente ın muchia[u, v]. Daca u = v, muchia e se numeste bucla. Multimea

N (v) := {u ∈ V | u, v sunt incidente ın muchia [u, v]}

se numeste vecinatatea varfului v.

Daca E = ∅, atunci graful (V,∅) se numeste graf nul pe care ıl vom nota cu On, iar dacaE = P2 (V ) , atunci graful (V,P2 (V )) se numeste graf complet pe care le vom nota cu Kn.

7

Page 8: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

2.1. TEORIECURSUL 2. GRAFURI, DIGRAFURI, MULTIGRAFURI SI GRAFURI GENERALE

Exemplu 7 Vom reprezenta grafurile cu ajutorul unor desene alcatuite din puncte si linii continuece vor lega anumite perechi de puncte. Grafuri Peterson

Exemplu 8 Orice multime ordonata (alfabetul limbii latine, multimea R, laticele, clasa partilorunei multimi etc.) este o latice.

Exemplu 9 Oricarui poliedru ıi putem asocia un graf neorientat. In particular, pentru poliedrelePlaton (tetraedru, cub, octoedru, dodecaedru, icosaedru) avem grafurile corespuzatoare

Exemplu 10 Graficul oricarei functii numerice reale este un graf.

8

Page 9: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 2. GRAFURI, DIGRAFURI, MULTIGRAFURI SI GRAFURI GENERALE2.1. TEORIE

Exemplu 11 (din lumea reala) Arborele genealogic al unui individ dintr-o anumita populatie(oameni sau animale), reteaua de drumuri/cai ferate a unei tari, paginile Web etc.

Definitia 12 (constructii de grafuri) Fie G1 = (V1, E1) si G2 = (V2, E2) grafuri neorientate.

(i) Numim complementarul grafului G1 perechea ordonta de multimi G1 := (V,P2 (V )− E), i.e.este graful alcatuit din aceleasi varfuri si doua varfuri sunt adiacente ın G daca si numaidaca nu sunt adiacente ın G.

(ii) Numim produsul cartezian al grafurilor G1 si G2 perechea ordonata G1 ×G2 := (V1 × V2, E) ,unde varfurile {(v1, v2) , (v′1, v′2)} sunt adiacente ın graful G1 ×G2 daca si numai daca

v1 = v′1 si{v2, v

′2

}∈ E2 sau v2 = v′2 si

{v1, v

′1

}∈ E1.

Definitia 13 Se numeste graf orientat sau digraf o perechea ordonata de multimi G = (V,E) ,

unde V este o multimi nevida, finita si E ⊆−−−−→P2 (V ).

Elementele multimii V se numesc varfuri (vertices) sau noduri ale grafului G, iar elementelelui E se numesc arc. Ordinul grafului orientat G = (V,E), notat cu o (G) sau nG sau n (G) ,reprezinta cardinalul multimii V , iar dimensiunea grafului G, notata cu dimG sau mG sau m (G) ,reprezinta cardinalul multimii E. Data o muchie e = {u, v} ∈ E, u, v se numesc extremitatile(initiale/finale) muchiei si o vom mai nota cu [u, v]. Daca u = v, muchia e se numeste bucla.

Observatia 14 Din punct de vedere al reprezentarii grafice, digrafurile au ın plus un sens deparcurs al arcelor.

Observatia 15 In baza propozitiei de la ınceputul cursului putem afirma ca exista√

2n(n−1) grafuricu n varfuri, respectiv, 2n(n−1) grafuri orientate cu n varfuri.

Definitia 16 (generalizari) (i) Se numeste graf multiplu sau multigraf o pereche ordonatade multimi G = (V,E) , unde V este o multime nevida, finita si E este o familie de elementedin P2 (V ), i.e.

e ∈ E, e = ({ui, vi})i∈I ,∀i ∈ I : ui, vi ∈ V, ui 6= vi

(ii) Se numeste graf general sau pseudograf o pereche ordonata de multimi G = (V,E), undeV este o multime nevida, finita si E este o familie de elemente din P1 (V ) ∪ P2 (V ).

(iii) Se numeste graf mixt o pereche ordonata de multimi G = (V,E ∪ E′), unde V este o multime

nevida, finita, E ⊆ P2 (V ) si E′ ⊆−−−−→P2 (V ).

Exemplu 17 Intuitiv un graf multiplu este un graf ın care ıntre doua varfuri pot exista mai multemuchii/arce. Observam ca grafurile sunt multigrafuri muchii multiple sau pseudografuri fara muchiimultiple si fara bucle.

9

Page 10: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

2.2. PROBLEMA SAPTAMANIICURSUL 2. GRAFURI, DIGRAFURI, MULTIGRAFURI SI GRAFURI GENERALE

2.2 Problema saptamanii

In sectiunea de fata ne propunem sa descriem o problema interesanta care se poate solutiona cuajutorul grafurilor.

Problema 18 (problema prieteniei a lui Paul Erdos) Descrieti printr-un graf un grup de 2n+1 persoane astfel ıncat oricare doua persoane au exact un prieten comun ın interiorul grupului.

2.3 Seminar

Exercitiul 19 Aratati ca ıntr-un grup de mai mult de doua persoane exista ıntotdeauna douapersoane cu acelasi numar de prieteni din interiorul grupului.

Solutie 20 Fie V = {1, 2, . . . , n} , n ∈ N, n ≥ 2 fixat, un grup oarecare de persoane si E ⊆ P2 (V ).O muchie {i, j} ∈ E, i, j ∈ V reprezinta faptul ca i si j sunt prieteni. Formal ne propunem saaratam ca

∃i, j ∈ V : i 6= j ⇒ |N (i)| = |N (j)| ,

unde N (i) = {j ∈ V | {i, j} ∈ E}. Daca presupunem pentru reducere la absurd ca

∀i, j ∈ V : i 6= j ⇒ |N (i)| 6= |N (j)|

ceea ce este echivalent cu injectivitatea functiei

N : {1, 2, . . . , n} → {0, 1, . . . , n− 1} .

Injectivitatea, surjectivitatea si bijectivitatea coincid ın cazul ın care functia ın discutie este definitaıntre multimi finite cu acelasi numar de elemente. Prin urmare, N este surjectiva, i.e.

∃i, j ∈ V : |N (i)| = 0 si |N (j)| = n− 1

Exercitiul 21 Construiti graful complementar asociat grafului

G = ({1, 2, 3, 4, 5, 6} , {{1, 2} , {1, 4} , {2, 5} , {3, 5} , {3, 6} , {5, 6}})

si produsul cartezian al grafurilor G1 = ({1, 2, 3, 4} , {{1, 2} , {2, 3} , {3, 4} , {4, 1}}) si G2 = ({z, y, x} , {{z, y} . {y, x}}) .

Solutie 22 ...

Exercitiul 23 Sa se deseneze graful corespunzator clasei partilor unei multimi finite A. Sa secalculeze marimea acestui graf?

Solutie 24 Graful corespunzator clasei partilor multimii A, P (A), este G = (V,E) unde V =P (A) si {A1, A2} ∈ E daca si numai daca

A1 ⊆ A2 si /∃A3 ∈ V : A1 ⊂ A3 ⊂ A2

sauA2 ⊆ A1 si /∃A3 ∈ V : A2 ⊂ A3 ⊂ A1.

Urmarind cu atentie desenul de mai sus putem deduce urmatoarea formula de calcul pentrumarimea grafului G

|E| = m (G) =

n∑k=0

(n

k

)k = n2n−1.

Exercitiul 25 Sa se deseneze graful corespunzator divizorilor unui numar natural n ≥ 2. Sa secalculeze marimea acestui graf?

10

Page 11: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 2. GRAFURI, DIGRAFURI, MULTIGRAFURI SI GRAFURI GENERALE2.3. SEMINAR

Solutie 26 Trebuie sa realizam desenul grafului G = (V,E), unde V = {d | d divide n} si {d1, d2} ∈E daca si numai daca

d1 | d2 si /∃ d3 ∈ V − {d1, d2} : d1 | d3 | d2sau

d2 | d1 si /∃ d3 ∈ V − {d1, d2} : d2 | d3 | d1.Dat un n ∈ N, n ≥ 2, avem n = pα1

1 pα22 · . . . · p

αkk si

|V | =k∏i=1

(αk + 1) si |E| =∑d|n

f (d) ,

unde f (d) reprezinta numarul de fatori primi din descompunerea lui d = pβ11 p

β22 · . . . · p

βkk , 0 ≤ βj ≤

αj , j ∈ 1, k. De exemplu, avem f (1) = 0,∑αj divizori de forma

d = pβj

j , 1 ≤ βj ≤ αj , j ∈ 1, k,∑αiαj divizori de forma

d = pβj

j pβii , 1 ≤ βi ≤ αi, 1 ≤ βj ≤ αj , i, j ∈ 1, k,

si inductiv α1α2 . . . αk divizori de forma

d = pβ11 p

β22 · . . . · p

βkk , 1 ≤ βj ≤ αj , j ∈ 1, k.

Prin urmare...

Exercitiul 27 Sa se deseneze graful corespunzator comutativitatii unui grup. Sa se calculezemarimea acestui graf? Sa se arate ca ın cazul grupurilor abeliene acest graf coincide cu Kn.

Solutie 28 Dat un grup (H, ·) graful comutativitatii acestuia este G = (V,E), unde V = H si,oricare ar fi x, y ∈ H, {x, y} ∈ E daca si numai daca xy = yx.

Exercitiul 29 Intr-o tara sunt 2000 de orase si niciun drum ıntre acestea. Sa se arate ca se poateconstrui o retea de drumuri astfel ıncat din 2 orase sa porneasca cate un drum, din alte 2 orase saporneasca cate 2 drumuri si tot asa pana cand la ultimele 2 din care vor porni 1000 de drumuri.

Solutie 30 Exista cel putin doua abordari ale acestei probleme daca la o olimpiada desfasurata ınorasul Sankt-Petersburg, ın anul 2001. Prima din ele consta ın demonstrarea prin inductie a uneiafirmatii generale din care vom regasi problema noastra drept un caz particular. Cea de-a douautilizeaza notiunea de graf bipartit.

Demonstram prin inductie dupa numarul de varfuri ca exista un graf cu 4n varfuri astfel ıncatgradul a doua varfuri sa fie 1, gradul altor doua sa fie 2, ..., gradul ultimelor doua varfuri sa fie 2.Pentru n = 1, luam 4 varfuri v1, v2, v3, v4 si construim muchiile {v1, v2} , {v2, v3} si {v3, v4}. Astfelv1 si v4 au gradul 1, iar v2 si v3 au gradul 2.

Presupunem acum ca afirmatia este adevarata pentru un graf cu 4n varfuri si o vom demonstrapentru un graf cu 4n+ 4 varfuri. Fie G un graf cu 4n varfuri care satisface proprietatea enuntata.

v0

v1

v2

v3

v4

v5

v6

11

Page 12: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

2.3. SEMINARCURSUL 2. GRAFURI, DIGRAFURI, MULTIGRAFURI SI GRAFURI GENERALE

Exercitiul 31 Vlad a observat ca printre cei 25 de colegi de clasa ai lui nu exista 2 care sa aibaacelasi numar de prieteni, ın schimb fiecare coleg are cel putin un prieten. Cati prieteni are Vlad?

12

Page 13: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 3

Subgrafuri si morfisme de grafuri

3.1 Teorie . . . . . . . . . . . . . . . 133.1.1 Operatii cu subgrafuri . . 143.1.2 Proprietati . . . . . . . . 15

3.2 Problema saptamanii . . . . . . . 163.3 Seminar . . . . . . . . . . . . . . 16

3.1 Teorie

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

• Se numeste subgraf al lui G un graf G′ = (V ′, E′), unde V ′ ⊂ V si V ′ ⊂ E.

• Se numeste subgraf al lui G generat de V ′ ⊂ V, graful G (V ′) = (V ′, E ∩ P2 (V ′)) .

• Se numeste subgraf al lui G generat de E′ ⊂ E, graful G (E′) = (U,E′), unde U estemultimea varfurilor din V unite prin muchii din E′.

Observatia 33 Pe multimea subgrafurilor lui G = (V,E) avem relatia de ordine

G′ =(V ′, E′

)≤ G′′ =

(V ′′, E′′

)⇔ V ′ ⊂ V ′′ si E′ ⊂ E′′.

Observatia 34 Daca V ′ = V, atunci G′ = (V,E′) , E′ ⊂ E, se numeste graf partial. Daca E′ = E,atunci G′ = (V ′, E) , V ′ ⊂ V , se numeste subgraf total/plin al lui G.

13

Page 14: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

3.1. TEORIE CURSUL 3. SUBGRAFURI SI MORFISME DE GRAFURI

3.1.1 Operatii cu subgrafuri

Fie G = (V,E) , G1 = (V1, E1) grafuri neorientate, V ′ ⊂ V si E′ ⊂ E.

• G − V ′ graful care se obtine eliminand din G toate varfurile din V ′ si toate muchiile ceau macar o extremitate ın V ′. In particular, pentru V ′ = {v} , avem G−B′ := G− v.

• G − E′ graful care se obtine eliminand din G toate muchiile din E′, dar pastrand toatevarfurile. In particular, pentru E′ = {e} , avem G− E′ = G− e.

• G+ U graful obtinut prin adaugarea elementelor din U drept varfuri izolate, unde U esteo multime astfel ıncat U ∩ V = ∅

• G+G1 graful (V ∪ V1, E ∪ E1) , impunand conditia E ∩ E1 = ∅.

Definitia 35 Fie G = (V,E) un graf si U ⊂ V .

• Daca G (U) = (U,∅), i.e. G (U) este graful nul, atunci U se numeste multime stabila a luiG. Numarul maxim de elemente ale unei multimi stabile se numeste numar de stabilitate.

• Daca G (U) = (U,P2 (U)), i.e. G (U) este graf complet, atunci U se numeste clica a lui G.Numarul maxim de elemente ale unei clici se numeste densitatea lui G, notat cu ρ (G).

Exemplu 36 Considerand graful din figura de mai jos,

constatam ca multimile {3, 4} , {1, 6} , {1, 4, 6} etc. sunt stabile, iar numarul de stabilitate este 3,multimile {1, 2} , {1, 2, 3} etc. sunt clici, iar densitatea lui G este 3.

Definitia 37 Fie G = (V,E) si G′ = (V ′, E′) doua grafuri. Se numeste morfism de grafuri de laG la G′ o functie f : V → V ′ astfel ıncat

∀e = {u, v} ∈ E : f (e) = {f (u) , f (v)} ∈ E′.

Exemplu 38 Date grafurile din figurile de mai jos, putem defini morfismul f : {1, 2, 3, 4, 5} →{1, 2} prin

f (1) = f (2) = f (3) = f (4) = 1 si f (5) = f (6) = 2.

.

14

Page 15: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 3. SUBGRAFURI SI MORFISME DE GRAFURI 3.1. TEORIE

3.1.2 Proprietati

1. Orice morfism de grafuri invariaza relatiile de incidenta si de adiacenta.

2. Compunerea a doua morfisme de grafuri este un morfism de grafuri.

Utilizand morfismele de grafuri, ıncercam ın cele ce urmeaza sa dam o teorema de caracterizarea grafurilor colorabile ın sensul definitiei urmatoare.

Definitia 39 Fie G = (V,E) un graf si r ∈ N∗.

• Se numeste colorare proprie a lui G o atribuire de culori varfurilor lui G astfel ıncat toatevarfurile adiacente sa fie colorate diferit.

• Se numeste numar cromatic al lui G numarul minim de culori necesare pentru o colorareproprie. Acest numar ıl vom nota cu χ (G).

• G se numeste r − colorabil daca admite o colorare cu r culori.

Teorema 40 Un graf G = (V,E) este r − colorabil daca si numai daca exista un morfism de laG la Kr.

Demonstratie. .......

Exemplu 41 Grafurile 1 − colorabile sunt cele formate din varfuri izolate. Cubul, ın generalhipercubul, este un graf 2 − colorabil, morfismul fiind f : G→ K2 definit prin

f (1) = f (3) = f (6) = f (8) = 1 si f (2) = f (4) = f (5) = f (7) = 2.

Graful lui Peterson este un graf 3 − colorabil, iar morfismul este f : G→ K3, definit prin

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

Una din probleme de colectie ale matematicii ce are legatura cu aceasta teorema este problemacelor 4 culori (pentru mai multe detalii vezi sectiunea urmatoare).

Definitia 42 Fie G = (V,E) un graf si G′ = (V ′, E′). Se numeste izomorfism de la G la G′ ofunctie bijectiva f : V → V ′ care este morfism. Daca G = G′, atunci f se va numi automorfisma lui G, iar cu Aut (G) vom nota multime automorfismelor lui G.

15

Page 16: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

3.2. PROBLEMA SAPTAMANII CURSUL 3. SUBGRAFURI SI MORFISME DE GRAFURI

Observatia 43 (Aut (G) , ◦) este grup.

Exemplu 44 Orice permutare σ din Sn este automorfism al grafului complet cu n varfuri, Kn.Deci, Aut (Kn) ∼= Sn.

Exemplu 45 Grupul automorfismelor grafului ciclic cu n varfuri, Cn, este izomorf cu grupuldiedral D2n. De exemplu, pentru n = 4, avem

Aut (C4) =

{(1 2 3 41 2 3 4

), ρ =

(1 2 3 42 3 4 1

), ε =

(1 2 3 42 1 4 3

), ρ2, ρ3, ρε, ρ2ε, ρ3ε

}Exemplu 46 Graful An definit prin{

V = {ai, bi, ci | 0 ≤ i < n}E = {(ai, ai+1) , (ai, bi) , (ai, ci) , (bi, ci) , (ci, ai+1) | 0 ≤ i < n} ,

i.e. An este un poligon cu n muchii, iar pe fiecare muchie este desenat un dreptunghi ımpreuna cuo diagonala a acestuia. Grupul automorfismelor lui An este izomorf cu Zn.

Exemplu 47 Automorfismele grafului G, definit prin V = {1, 2, 3, 4} , E = {{1, 2}}, este formatdin permutarile(

1 2 3 41 2 3 4

),

(1 2 3 42 1 3 4

),

(1 2 3 41 2 4 3

),

(1 2 3 42 1 4 3

).

Prin urmare, Aut (G) este izomorf cu grupul lui Klein.

3.2 Problema saptamanii

Problema 48 (De Morgan, 1852/solutie computationala 1976) Data o harta, se pot coloratarile acesteia cu cel mult 4 culori astfel ıncat oricare doua tari vecine sa fie colorate diferit.

3.3 Seminar

16

Page 17: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 4

Grade si semigrade

4.1 Teorie . . . . . . . . . . . . . . . 174.2 Problema saptamanii . . . . . . . 204.3 Seminar . . . . . . . . . . . . . . 20

4.1 Teorie

Definitia 49 Fie G = (V,E) un graf si v ∈ V . Definim gradul (valenta) varfului v ca fiindnumarul natural

dG (v) := card {e ∈ E | v ∈ e} . (4.1)

Observatia 50 Gradul unui varf oarecare v se poate la fel de bine defini prin

dG (v) := card {u ∈ V | {u, v} ∈ E} .

Daca dG (v) = 0, atunci v este varf izolat, iar daca dG (v) = 1, atunci v se numeste varf pendant.

Observatia 51 Definitia de mai sus poate fi extinsa la pseudografuri si multigrafuri.

Calculand cardinalul multimii M = {(v, e) ∈ V × E | e ∈ E} ın doua moduri, i.e.

cardM =∑v∈V

card {e ∈ E | v ∈ e} =∑v∈V

dG (v)

si

cardM =∑e∈E

card {v ∈ V | v ∈ e} =∑e∈E

2 = 2 cardE,

obtinem un rezultat prin rezultat remarcabil.

Teorema 52 (Euler) Daca G = (V,E) este graf, atunci are loc egalitatea∑v∈V

dG (v) = 2 cardE. (4.2)

17

Page 18: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

4.1. TEORIE CURSUL 4. GRADE SI SEMIGRADE

Corolar 53 In orice graf numarul varfurilor de grad impar este par, dupa cum se poate vedea ınexemplul urmator

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

• Numarul δG := min {dG (v) | v ∈ V } se numeste gradul minim al lui G.

• Numarul ∆G := max {dG (v) | v ∈ V } se numeste gradul maxim al lui G.

• Numarul

dG :=1

|V |∑v∈V

dG (v) , |V | := cardV,

se numeste gradul mediu al lui G.

Se poate observa cu usurinta ca

∀v ∈ V : δG ≤ dG (v) ≤ ∆G si dG =2 |E||V |

=2mG

2nG,

unde mG reprezinta numarul de muchii din graful F , iar nG numarul de varfuri/noduri din grafulG.

Definitia 55 Fie G = (V,E) un digraf si v ∈ V .

• Numim semigrad exterior al varfului v ca fiind numarul natural

d+G (v) := card {e ∈ E | e = {v, u} , u ∈ V } . (4.3)

• Numim semigrad interior al varfului v ca fiind numarul natural

d−G (v) := card {e ∈ E | e = {u, v} , u ∈ V } . (4.4)

Cu alte cuvinte, daca d+G (v) = 1, atunci varful v este extremitate initiala a unei singure muchii,iar daca d−G (v) = 1, atunci v este extremitate finala a unei singure muchii. Teorema lui Euler ıncazul digrafilor are forma ∑

v∈Vd+G (v) =

∑v∈V

d−G (v) = |E| . (4.5)

Definitia 56 Fie r ∈ N. Un graf G = (V,E) se numeste r − regulat daca toate varfurile au gradulr, i.e.

∀v ∈ V : dG (v) = r.

Exemplul standard de graf (n− 1)− regulat este graful complet cu n varfuri, Kn.

18

Page 19: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 4. GRADE SI SEMIGRADE 4.1. TEORIE

Teorema 57 Fie r ∈ N. Daca G = (V,E) este graf r − regulat de ordin n, atunci

r ∈ {0, 1, . . . , n− 1} si n · r ∈ 2N.

Reciproc, oricare ar fi n ∈ N∗ si r ∈ 0, n− 1 cu proprietatea ca n · r ∈ 2N, exista un graf r −regulat de ordin n.

Demonstratie. ....

Observatia 58 Teorema de mai sus ne ofera odata cu demonstratia sa si un algoritm de constructiea unui graf r − regulat. De exemplu, dorim sa construim un graf r − regulat de ordinul n. Fie

multimea M ={±1,±2, . . . , q

}, daca r = 2q, sau M =

{±1,±2, . . . , q,m

}, daca r = 2q + 1 si

n = 2m. Atunci construind graful cu varfurile V = Z6 si muchiile obtinute prin

∀x, y ∈ Zn : {x, y} ∈ E ⇔ x− y ∈M, (4.6)

vom obtine un graf care r − regulat de ordinul n.

Definitia 59 Fie n ∈ N∗ si{di ∈ N | i ∈ 1, n

}astfet ıncat d1 ≥ d2 ≥ . . . ≥ dn. Spunem ca

d1, d2, . . . , dn este un sir de grade/ sir grafic daca exista un graf G = (V,E) cu V ={vi | i ∈ 1, n

}astfel ıncat

∀i ∈ 1, n : dG (vi) = di.

De exemplu, sirul 4, 3, 3, 3, 1 este un sir grafic, iar graful corespunzator este

Criteriu 60 Pentru rezolvarea problemei sirului grafic trebuie sa verificam unul din urmatoareledoua cazuri

1. Fie n ≥ 2 si d1, d2, . . . , dn ∈ N cu d1 ≥ . . . ≥ dn si d1 6= 0. Atunci{di | i ∈ 1, n

}este sir

grafic daca si numai daca

d2 − 1, d3 − 1, . . . , dd1+1 − 1, dd1+2 − 1, . . . , dn

este sir grafic.

2. Fie n ≥ 2 si d1, d2, . . . , dn ∈ N cu d1 ≥ . . . ≥ dn. Atunci{di | i ∈ 1, n

}este sir grafic daca si

numai daca

n∑i=1

di ∈ 2N si ∀k ∈ 1, n− 1 :

n∑i=1

di ≤ k (k − 1) +

n∑i=k+1

min {k, di} .

19

Page 20: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

4.2. PROBLEMA SAPTAMANII CURSUL 4. GRADE SI SEMIGRADE

4.2 Problema saptamanii

Exercitiul 61 Studiati existenta unui graf pentru care gradele varfurilor sunt

Problema 62 (i) 4, 3, 3, 3, 1.v (zmeu+o muchie exterioara)

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

(iii) 4, 3, 1, 1, 1.x

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

(v) 5, 3, 2, 1, 1.x

Problema 63 In general, date numerele naurale d1 ≥ . . . ≥ dn, sa se decida daca exista un grafG = (V,E) cu V =

{di | i ∈ 1, n

}si

∀i ∈ 1, n : dG (vi) = di.

4.3 Seminar

20

Page 21: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 5

Drumuri, cicluri si circuite

5.1 Teorie . . . . . . . . . . . . . . . 215.1.1 Conexitate . . . . . . . . 22

5.2 Problema saptamanii . . . . . . . 225.3 Seminar . . . . . . . . . . . . . . 22

5.1 Teorie

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

• Se numeste ruta ın G o secventa de tipul

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

{vi ∈ V , i ∈ 1, k + 1

ej ∈ E , j ∈ 1, k.

Vom nota cu l (µ) = k lungimea rutei.

• Se numeste ruta simpla ın G o ruta pentru care toate muchiile sunt distincte.

• Se numeste drum ın G o ruta pentru care toate varfurile sunt distincte (eventual cu exceptiaextremitatilor).

• Se numeste ruta ciclica ın G o ruta µ = (v1, e1, v2, e2, . . . , vk, ek, vk+1) ın care v1 = vk+1.

B

• Se numeste ciclu ın G o ruta simpla ciclica.

• Se numeste ciclu elementar ın G un ciclu pentru care si muchiile si varfurile sunt distinctedoua cate doua (cu exceptia extremitatilor).

• Se numeste ciclu eulerian ın G un ciclu ce contine toate muchiile lui G.

• Se numeste ciclu hamiltonian ın G un ciclu ce contine toate varfurile lui G.

Exemplu 65 Abundenta...Trapez si un varf izolat- ciclu eulerian, ciclul

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

este un ciclu hamiltonian ın cub.

21

Page 22: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

5.2. PROBLEMA SAPTAMANII CURSUL 5. DRUMURI, CICLURI SI CIRCUITE

Teorema 66 Fie G = (V,E) un graf. Daca, pentru toate varfurile din V , dG (v) ≥ 2m, atunci Gcontine cicluri.

Teorema 67 Fie G = (V,E) un graf astfel ıncat cardV ≥ 3. Daca cardE ≥ cardV , atunci Gcontine cicluri.

Teorema 68 Fie G = (V,E) un graf. Daca exista u, v ∈ V, distincte, astfel ıncat ıntre u si vexista doua drumuri diferite, atunci G admite cicluri.

Observatia 69 Toate conceptele definite mai sus se pot generaliza pentru digrafuri, multigrafuri sipseudografuri. Bunaoara, ın cazul digrafilor un ciclu poarta denumirea de circuit. Se poate arataca un digraf G = (V,E) admite circuite daca

∀v ∈ V : d+G (v) ≥ 1 sau d−G (v) ≥ 1.

Teorema 70 (criteriu grafuri bipartite) Un graf este bipartit daca si numai daca nu continecicluri de lungime impara.

Pentru o aplicatie interesanta a acestui rezultat merita sa parcugem problema din sectiuneaurmatoare.

5.1.1 Conexitate

Definitia 71 Un graf G = (V,E) se numeste conex daca ıntre oricare doua varfuri distincte existacel putin un drum.

Observatia 72 Daca G este un graf oarecare, atunci putem defini pe V relatia ∼ prin

∀u, v ∈ V : u ∼ v⇔ ∃µ− deum de la u la v.

Se arata imediat ca ∼ este o relatia de echivalenta, iar clasele de echivalenta le vom numi compo-nente conexe ale lui G (evident sunt grafuri conexe).

Sa presupunem ca G este conex. Fie v0 ∈ V si definim multimile

V1 := {v ∈ V | ∃µ drum de lungime impara de la v0 la v}

siV2 := {v ∈ V | ∃µ drum de lungime para de la v0 la v} .

Atunci se poate arata ca (V1, V2) este o bipartitie a lui V .

5.2 Problema saptamanii

Problema 73 (Hamilton) Fie n ∈ N. Fie o tabla de sah cu n2 patratele. Se poate ca un calsarind ın L sa plece de pe o anumita pozitie, sa treaca prin toate patratele tablei si ın final sa seıntoarca ın pozitia initiala?

Solutie 74 Daca n ∈ 2N+1, nu deoarece fiind un graf bipartit nu exista cicluri de lungime impara(n2 este impar). In rest, daca n ≥ 6 si n ∈ 2N, atunci raspunsul este afirmativ.

.....

5.3 Seminar

22

Page 23: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 6

Conexitate

6.1 Teorie . . . . . . . . . . . . . . . 236.2 Problema saptamanii . . . . . . . 246.3 Seminar . . . . . . . . . . . . . . 24

6.1 Teorie

Definitia 75 Un graf G = (V,E) se numeste conex daca ıntre oricare doua varfuri distincte existacel putin un drum.

Observatia 76 Daca G este un graf oarecare, atunci putem defini pe V relatia ∼ prin

∀u, v ∈ V : u ∼ v⇔ ∃µ− deum de la u la v.

Se arata imediat ca ∼ este o relatia de echivalenta, iar clasele de echivalenta le vom numi com-ponente conexe ale lui G (evident sunt grafuri conexe). Vom nota numarul total al componentelorconexe sau cardinalul multimii factor prin p (G).

Graful din figura de mai jos contine 3 componente conexe.

Definitia 77 Un digraf G = (V,E) se numeste

• tare comex daca ∀u, v ∈ V, u 6= v, exista cel putin un drum de la u la v.

• unilateral conex daca ∀u, v ∈ V, u 6= v, exista cel putin un drum de la u la v sau de la v lau.

• conex daca graful suport al lui G, G′ = (V,E′) , E′ = {{u, v} | (u, v) ∈ E}, este conex.

23

Page 24: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

6.2. PROBLEMA SAPTAMANII CURSUL 6. CONEXITATE

Exemplu 78 In figura de mai jos regasim 3 exemple, cate unul pentru fiecare notiune introdusaın definitia anterioara.

Teorema 79 (legatura dintre |E| , |V | si p (G)) Fie G = (V,E) un graf, n = |V | ,m = |E| sip = p (G). Atunci avem estimarea

n− p ≤ m ≤ C2n−p+1. (6.1)

Demonstratie. Inductie dupa n...

Teorema 80 Un graf G = (V,E), cu n = |V | ,m = |E| si p = p (G), nu admite cicluri daca sinumai daca m− n+ p = 0.

Observatia 81 Notam ca numarul m− n+ p se numeste numar ciclomatic al lui G.

Lema 82 Fie G = (V,E) un graf cu proprietatea ca, pentru toti v ∈ V , 2 ≤ dG (v) ∈ 2N. Atunciorice muchie a lui G este continuta ıntr-un ciclu.

Teorema 83 (Euler) Fie G = (V,E) un graf conex cu proprietatea ca |V | ≥ 2. Atunci G admiteun ciclu eulerian daca si numai daca

∀v ∈ V : dG (v) ∈ 2N.

Observatia 84 Teorema de mai sus are loc si pentru multigrafuri.

6.2 Problema saptamanii

Problema 85 Problema celor 7 poduri de la Konigsberg (azi cunoscut sub denumirea de Kalinin-grad). Se pune problema existentei unui ciclu eulerian ın multigraful de mai jos

6.3 Seminar

24

Page 25: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 7

Clase importante de grafuri

7.1 Teorie . . . . . . . . . . . . . . . 267.2 Problema saptamanii . . . . . . . 287.3 Seminar . . . . . . . . . . . . . . 28

25

Page 26: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

7.1. TEORIE CURSUL 7. CLASE IMPORTANTE DE GRAFURI

7.1 Teorie

Definitia 86 Se numeste graf planar un graf care admite o reprezentare ın plan astfel ıncat mu-chiile sa se intersecteze cel mult ın varfuri.

Observatia 87 Orice graf planar ımparte planul ın suprafete conexe numite fete. Numarul mu-chiilor care delimiteaza o fata se va numi gradul acelei fete. Vom nota un graf planar G prin

G = (V,E, F ) ,

unde F este multimea fetelor.

Teorema 88 (Euler) Daca G = (V,E, F ) este un graf planar, atunci∑f∈F

dG (f) = 2 cardE. (7.1)

Teorema 89 (formula poliedrala a lui Euler) Daca G = (V,E, F ) este un graf planar conex,atunci

|V | − |E|+ |F | = 2.

Exemplu 90 Grafurile platonice sunt grafuri obtinute din muchiile si varfurile celor cinci poliedreregulate ale lui Platon. Aceste sunt

26

Page 27: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 7. CLASE IMPORTANTE DE GRAFURI 7.1. TEORIE

• tetraedrul

• octoedrul

• cubul

• icosaedrul

• dodecaedrul.

In figurile de mai jos sunt reprezentate cele 5 grafuri.

Corolar 91 Fie G = (V,E, F ) un graf planar conex.

(i) Daca cu |V | ≥ 3, atunci|E| ≤ 3 |V | − 6.

27

Page 28: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

7.2. PROBLEMA SAPTAMANII CURSUL 7. CLASE IMPORTANTE DE GRAFURI

(ii) Exista un varf v ∈ V astfel ıncat dG (v) ≤ 5.

Exemplu 92 Grafurile K5 si K3,3 nu sunt planare.

Definitia 93 Spunem ca realizam o diviziune a unui graf G daca inseram varfuri de grad 2 pemuchiile sale. Graful nou obtinut se numeste subdiviziune a lui G.

Teorema 94 (Kuratowski) Un graf G este planar daca si numai daca nu contine subdiviziuniale grafurilor K5 si K3,3.

Demonstratie. ...

Observatia 95 Folosind teorema de mai sus se poate arata ca graful lui Peterson nu este planar.

7.2 Problema saptamanii

7.3 Seminar

28

Page 29: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 8

Arbori. Arbori partiali

8.1 Teorie . . . . . . . . . . . . . . . 298.2 Problema saptamanii . . . . . . . 308.3 Seminar . . . . . . . . . . . . . . 32

8.1 Teorie

Definitia 96 Se numeste arbore un graf conex aciclic.

Propozitia 97 Fie G = (V,E) un arbore. Atunci G are urmatoarele proprietati

(i) ∀u, v ∈ V, u 6= v, exista un unic drum de la u la v.

(ii) |E| = |V | − 1.

(iii) Exista cel putin 2 varfuri de grad 1.

Teorema 98 (de caracterizare a arborilor) Fie G = (V,E) un graf. Urmatoarel afirmatii suntechivalente.

(i) G este arbore.

29

Page 30: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

8.2. PROBLEMA SAPTAMANII CURSUL 8. ARBORI. ARBORI PARTIALI

(ii) G este conex si |E| = |V | − 1.

(iii) G este aciclic si |E| = |V | − 1.

(iv) G este aciclic si, oricare ar fi e ∈ P2 (V ) \ E, graful G+ e are exact un ciclu.

(v) G este conex si, oricare ar fi e ∈ E, graful G− e nu este conex.

Teorema 99 Fie numerele d1 ≥ d2 ≥ . . . ≥ dn ≥ 1. Atunci exista un arbore cu sirul gradelord1, d2, . . . , dn daca si numai daca

n∑i=1

di = 2n− 2.

Demonstratie. ...

Definitia 100 Fie G = (V,E) un graf si G′ = (V,E′) un graf partial al lui G. Spunem ca G′ senumeste arbore partial al lui G, daca G′ este arbore.

Teorema 101 Un graf admite arbori partiali daca si numai daca este graf conex.

8.2 Problema saptamanii

Problema 102 Dat un graf conex G = (V,E) construiti un arbore partial al sau.

Pentru a rezolva aceasta problema, intuitiv, trebuie sa parcurgem urmatori pasi

• plecam de la graful nul G0 = (V,∅) ;

• adaugam succesiv muchii astfel ıncat ele sa nu formeze cicluri cu muchiile deja adaugate;

• ne oprim cand numarul de muchii este |V | − 1.

Concret, solutia problemei va rezulta aplicand cu multa grija urmatorul algoritm format din 5pasi:

1. Dat graful G = (V,E), construim G0 = (V,∅) si fie i = 0;

2. Presupunem ca am construit graful Gi = (V,Ei).

Daca i = |V | − 1

atunci Gi este un arbore partial al lui G;

STOP;

3. Cautam o muchie e ∈ E \ Ei astfel ıncat ea are extremitatile ın componente conexe diferiteale lui Gi.

Daca exista o astfel de muchie e

atunci Gi+1 := Gi + e;

altfel trecem la pasul 5;

4. i := i+ 1

Trecem la pasul 1;

5. Graful G nu este conex, deci nu admite arbori partiali.

STOP.

30

Page 31: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 8. ARBORI. ARBORI PARTIALI 8.2. PROBLEMA SAPTAMANII

1. Dat graful G = (V,E), construim G0 = (V,∅) si fie i = 0;

2. Presupunem ca am construit graful Gi = (V,Ei).

Daca i = |V | − 1

atunci Gi este un arbore partial al lui G;

STOP;

3. Cautam o muchie e ∈ E\Ei astfel ıncat ea are extremitatile ın componente conexe

diferite ale lui Gi.

Daca exista o astfel de muchie e

atunci Gi+1 := Gi + e;

altfel trecem la pasul 5;

4. i := i + 1

Trecem la pasul 1;

5. Graful G nu este conex, deci nu admite arbori partiali.

STOP.

Exemplu 103 Gasiti arborele partial al lui G dat ın figura de mai jos

i = 0

i = 1

i = 2

31

Page 32: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

8.3. SEMINAR CURSUL 8. ARBORI. ARBORI PARTIALI

i = 3

i = 4

i = 5

STOP!

Exemplu 104 Dupa 10 iteratii ale algortmului de mai sus, se arata ca graful din dreapta estearborele partial obtinut din graful lui Peterson.

8.3 Seminar

32

Page 33: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 9

Arbori partiali de cost minim. Algoritmul lui Kruskal/Prim

9.1 Teorie . . . . . . . . . . . . . . . 339.2 Problema saptamanii . . . . . . . 379.3 Seminar . . . . . . . . . . . . . . 37

9.1 Teorie

Fie G = (V,E) un graf.

Definitia 105 O functie c : E → R care asociaza fiecarei muchii e ∈ E, numarul real c (e) senumeste functie cost asociata grafului G.

Daca luam G′ − (V ′, E′) un subgraf al lui G, atunci

c(G′)

=∑e∈E′

c (e) .

Problema 106 Dat un graf G = (V,E) si o functie cost c : E → R, sa se determine arborelepartial de cost minim al lui G.

Pentru ınceput, dat un graf trebuie sa obtinem arborele partial corespunzator. Acest lucru esteposibil utilizand algoritmul urmator (dat si ın cursul anterior):

1. Dat graful G = (V,E), construim G0 = (V,∅) si fie i = 0;

2. Presupunem ca am construit graful Gi = (V,Ei).

Daca i = |V | − 1

atunci STOP - Gi este un arbore partial al lui G;

STOP;

3. Cautam o muchie e∗ ∈ E\Ei astfel ıncat ea are extremitatile ın componente conexe

diferite ale lui Gi.

Daca exista o astfel de muchie e∗

atunci Gi+1 := Gi + e∗;

altfel trecem la pasul 5;

4. i := i+ 1;

Trecem la pasul 1;

33

Page 34: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

9.1. TEORIECURSUL 9. ARBORI PARTIALI DE COST MINIM. ALGORITMUL LUI KRUSKAL/PRIM

5. Graful G nu este conex, deci nu admite arbori partiali.

STOP.

Teorema 107 Fie G = (V,E) un graf, c : E → R functia cost asociata, G′ = (V ′, E′) un grafpartial aciclic al lui G si V1 o componenta conexa a lui G′. In aceste conditii, daca G′ este continutıntr-un arbore partial de cost minim al lui G si e∗ este o muchie de cost minim ce are exact oextremitate ın V1, atunci G′ + e∗ este de asemenea continut ıntr-un arbore partial de cost minimın G.

In continuare prezentam doi algoritmi pentru construirea unui arbore partial de cost minim.

Algoritmul 108 (Kruskal)

1. Dat graful G = (V,E), c : E → R, luam G0 = (V,∅) si fie i = 0;

2. Presupunem ca am construit graful Gi = (V,Ei).

Daca i = |V | − 1

atunci STOP - Gi este un arbore partial al lui G de cost minim;

3. Cautam o muchie de cost minim e∗ ∈ E \ Ei astfel ıncat ea are extremitatile ın

componente conexe diferite ale lui Gi.

Daca exista o astfel de muchie e∗

atunci Gi+1 := Gi + e∗;

altfel trecem la pasul 5;

4. i := i+ 1;

Trecem la pasul 2;

5. Graful G nu este conex, deci nu admite arbori partiali de cost minim.

STOP.

Exemplu 109 Aplicam algoritmul lui Kruskal pentru graful ce are varfurile V = {1, 2, 3, 4, 5} si

E = {{1, 2}2 , {1, 4}1 , {1, 5}4 , {2, 3}1 , {2, 5}1 , {3, 5}2 , {4, 3}3 , {4, 5}3} ,

unde {u, v}x reprezinta o muchie oarecare, iar x = c ({u, v}) ∈ R. Graful dat este reprezentat ınfigura de mai jos

34

Page 35: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 9. ARBORI PARTIALI DE COST MINIM. ALGORITMUL LUI KRUSKAL/PRIM9.1. TEORIE

i = 0

i = 1 i = 2

i = 4 i = 4

Algoritmul 110 (Prim)

1. Dat graful G = (V,E), c : E → R, luam v0 ∈ V, G0 = (V,∅) si i = 0;

2. Presupunem ca am construit graful Gi = (Vi, Ei).

Daca i = |V | − 1

atunci STOP - Gi este un arbore partial al lui G de cost minim;

3. Cautam o muchie de cost minim e∗ ∈ E \ Ei astfel ıncat ea are o extremitate ın

Vi si cealalta extremitate ın V \ Vi .

Daca exista o astfel de muchie e∗ = {u, v} , u ∈ Vi, v ∈ V \ Viatunci Vi+1 := Vi ∪ {v} ;

Ei+1 = Ei ∪ {e∗} ;

altfel trecem la pasul 5;

4. i := i+ 1;

Trecem la pasul 2;

5. Graful G nu este conex, deci nu admite arbori partiali de cost minim.

STOP.

35

Page 36: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

9.1. TEORIECURSUL 9. ARBORI PARTIALI DE COST MINIM. ALGORITMUL LUI KRUSKAL/PRIM

Exemplu 111 Aplicam algoritmul lui Prim pentru graful ce are varfurile V = {1, 2, 3, 4, 5} si

E = {{1, 2}2 , {1, 4}1 , {1, 5}4 , {2, 3}1 , {2, 5}1 , {3, 5}2 , {4, 3}3 , {4, 5}3} ,

unde {u, v}x reprezinta o muchie oarecare, iar x = c ({u, v}) ∈ R. Graful dat este reprezentat ınfigura de mai sus.

36

Page 37: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 9. ARBORI PARTIALI DE COST MINIM. ALGORITMUL LUI KRUSKAL/PRIM9.2. PROBLEMA SAPTAMANII

Teorema 112 (Tomescu) Intr-un graf cu n varfuri care nu contine un subgraf complet de ordink, k ≥ 2, atunci acesta contine cel putin m = {n/ (k − 1)} varfuri de grad

p ≤[

(k − 2)n

k − 1

],

unde {x} este cel mai mic numar ıntreg ≥ x.

Demonstratie. .........

Exercitiul 113 Intr-o multime M ce contine 1001 persoane, fiecare submultime de 11 persoanecontine cel putin doua care se cunosc reciproc. Sa se arate ca exista cel putin 101 persoane astfelıncat fiecare din ele cunoaste cel putin 100 persoane din M .

Exemplu 114 Sa se aplice cei doi algoritmi pentru graful de tip roata

9.2 Problema saptamanii

9.3 Seminar

37

Page 38: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

9.3. SEMINARCURSUL 9. ARBORI PARTIALI DE COST MINIM. ALGORITMUL LUI KRUSKAL/PRIM

38

Page 39: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 10

Probleme de numarare a arborilor

10.1 Teorie . . . . . . . . . . . . . . . 3910.2 Problema saptamanii . . . . . . . 4010.3 Seminar . . . . . . . . . . . . . . 40

10.1 Teorie

Teorema 115 (Cayley) Numarul arborilor cu n ∈ N varfuri, v1, v2, . . . , vn este egal cu nn−2.

Demonstratie. Pentru n = 0 si n = 1 se verifica imediat.

Pentru n = 3, Notam cu V = {1, 2, 3, . . . , n} si cu A (n) multilea arborilor cu varfuri ın V .

Definim functia f : A (n)→ V n−2, unde

V n−2 ={

(u1, u2, . . . , un−2) | ui ∈ V, i ∈ 1, n},

definita prin

G = (V,E) 7→ f (G) = (u1, u2, . . . , un−2)

definit astfel {v1 = min {v ∈ V | dG (v) = 1}

u1 ∈ N (v1) (unic)⇒ G1 = G− v1,{

v2 = min {v ∈ V \ {v1} | dG1 (v) = 1}u2 ∈ N (v2) (unic)

⇒ G2 = G1 − v2,

...{vk = min

{v ∈ V \ {v1, . . . vk−1} | dGk−1

(v) = 1}

uk ∈ N (vk) (unic)⇒ Gk = Gk−1 − vk.

Obtinem astfel un sir (u1, u2, . . . , un−2), numit cod Prufer al lui G. Aratand ca functia f estebijectiva se obtine concluzia dorita.

Observatia 116 Graful Gk = (Vk, Ek) este alcatuit din

Vk = V \ {v1, . . . , vk}

si

Ek ={{vi, ui} | i ∈ k + 1, n− 1

}.

39

Page 40: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

10.2. PROBLEMA SAPTAMANIICURSUL 10. PROBLEME DE NUMARARE A ARBORILOR

Observatia 117 Varfurile de grad 1 din Gk sunt {vk+1, vk+2, . . . , vn−1, n}\{uk+1, . . . , un−2}. Prinurmare putem defini

vi = min {v ∈ V | v 6= vk,∀k ≥ i si v 6∈ {v1, . . . , vi−1}} .

Exercitiul 118 Sa se gaseasca graful G al carui cod Prufer este

(i) f (G) = (2, 1, 1)

(ii) f (G) = (1, 1, 1, 1, 6, 5) .

Exercitiul 119 Sa se determine o metoda de a determina codul Prufer, daca avem dat graful G.

10.2 Problema saptamanii

10.3 Seminar

40

Page 41: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 11

Algoritmi de cautare

11.1 Teorie . . . . . . . . . . . . . . . 4111.2 Problema saptamanii . . . . . . . 4111.3 Seminar . . . . . . . . . . . . . . 41

11.1 Teorie

11.2 Problema saptamanii

11.3 Seminar

41

Page 42: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

11.3. SEMINAR CURSUL 11. ALGORITMI DE CAUTARE

42

Page 43: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 12

Probleme de drum minim (maxim)

12.1 Teorie . . . . . . . . . . . . . . . 4312.2 Problema saptamanii . . . . . . . 4612.3 Seminar . . . . . . . . . . . . . . 46

12.1 Teorie

Fie G = (V,E) un digraf, c : E → R functia cost asociata lui G. Vom face urmatoarele notatii:

• ∀e = (u, v) ∈ E, c (e) = c (u, v) se numeste ponderea arcului (u, v).

• ∀µ = (u1, . . . , uk) , c (µ) = c (u1, u2) + . . .+ c (uk−1, uk) se numeste ponderea drumului µ.

• µ = (u), atunci c (µ) = 0.

• ∀u, v ∈ V, (u, v) 6∈ E =⇒ c (u, v) =∞.

• ∀u, v ∈ V, D (u, v) = {µ | µ drum de la u la v}.

• ∀u, v ∈ V, d (u, v) = c (µ∗) , µ∗ = min {c (µ) | µ ∈ D (u, v)}. Prin conventie

d (u, u) = 0 si d (u, v) =∞, daca u 6= v si D (u, v) = ∅.

Vom studia ın cele ce urmeaza urmatoarea problema

Problema 120 (cost min/max) Fie G = (V,E) un graf si c : E → R functia cost asociata.Oricare ar fi u, v ∈ V , sa se determine µ∗ ∈ D (u, v) astfel ıncat

c (µ∗) = min {c (µ) | µ ∈ D (u, v)}

sauc (µ∗) = max {c (µ) | µ ∈ D (u, v)} .

Date doua drumuri µ1 = (x1, . . . , xk) si µ2 = (y1, . . . , yh), atunci definim

µ1 ◦ µ2 = (x1, . . . , xk−1, xk = y1, y2, . . . , yh)

si notam prin µ (xi, xk) = (xi, . . . , xk) , ∀i ∈ 1, k − 1.

Observatia 121 Problema de cost min /max se rezolva usor atunci cand digraful G nu continecircuite de pondere negativa.

43

Page 44: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

12.1. TEORIE CURSUL 12. PROBLEME DE DRUM MINIM (MAXIM)

Teorema 122 Fie G = (V,E) un digraf, c : E → R functia cost si presupunem ca G nu continecircuite de pondere negativa. Atunci

∀u, v, w ∈ V : d (u, v) ≤ d (u,w) + d (w, v) . (12.1)

Teorema 123 Fie G = (V,E) un digraf, c : E → R functia cost si presupunem ca G nu continecircuite de pondere negativa. Atunci oricare ar fi u, v ∈ V si oricare ar fi µ drum de pondereminima de la u la v, oricare ar fi w varf al lui µ, µ = (u,w) si µ (w, v) sunt drumuri de pondereminima de la u la w, respectiv de la w la v.

Teorema 124 Fie G = (V,E) un digraf, c : E → R functia cost si presupunem ca G nu continecircuite de pondere negativa. Atunci

∀v, u ∈ V : u 6= v ⇒ d (u, v) = min {d (u,w) + c (w, v) | w ∈ V \ {v}} .

Vom studia trei cazuri pentru problema de cost minim:

• G nu are circuite;

• c : R→ R+;

• G nu contine circuite de pondere negativa.

CAZUL I

Definitia 125 Fie G = (V,E) un digraf cu |V | = n. Numim numerotare aciclica a varfurilorlui G o functie bijectiva

ϕ : V → {1, 2, . . . , n} : ∀ (u, v) ∈ E, ϕ (u) < ϕ (v) .

Teorema 126 Un digraf G admite numerotare aciclica daca si numai daca G nu are circuite.

Observatia 127 Pentru determinarea unei numerotari aciclice a unui digraf fara circuite se pro-cedeaza dupa cum urmeaza. Fie

V1 ={v ∈ V | d−G (v) = 0 sau v nu are antecedenti

}.

Numerotam cu 1, 2, . . . , |V1| elementele multimii V1. Apoi alegem G1 = G−V1 si definim multimea

V2 ={v ∈ V \ V1 | d−G1

(v) = 0}.

Numerotam cu |V1| + 1, . . . , |V1| + |V2| elementele multimii V2. Continuam acest procedeu panaepuizam elementele multimii V . In figura de mai jos este un digraf numerotat conform cu celestabilite mai sus.

44

Page 45: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 12. PROBLEME DE DRUM MINIM (MAXIM) 12.1. TEORIE

Presupunem ca G nu are circuite, c : E → R, V = {1, 2, . . . , n} si

∀ (i, j) ∈ E : i < j.

Fixam s ∈ V . Oricare ar fi i ∈ V, d (s, i) := m (i) si notam cu p (i) varful ce precede varful i peun drum de pondere minima de la s la i. Avem ca

m (s) = 0, ∀i < s : m (i) =∞.

Oricare ar fi i ≤ h, presupunem cunoscute valorile m (i). Astfel avem

m (h+ 1) = min {m (i) + c (i, h+ 1) | s ≤ i ≤ h}= m (i∗) + c (i∗, h+ 1) .

Deducem ca p (h+ 1) = i∗.

CAZUL IIFie G = (V,E) un digraf, c : E → R+.Fixam s ∈ V, S ⊂ V astfel ıncat s ∈ S.

Definitia 128 Se numeste (s, S)− marcare a varfurilor lui G o functie

m : V → R, m (v) :=

{d (s, v) , v ∈ Smin {m (u) + c (u, v) | u ∈ S} , v ∈ V \ S .

In algoritmul lui Dijkstra se porneste de la S = {s} si se construieste un sir de (s, S)− marcariale varfurilor lui G. In final, vom lua S = V , situatie ın care

∀v ∈ V : m (v) = d (s, v) .

Teorema 129 In ipotezele anterioare, daca v0 ∈ V \ S astfel ıncat

m (v0) = min {m (v) ∈ V \ S} ,

atunci m′ : V → R definita prin

m′ (v) :=

{m (v) , v ∈ S ∪ {v0}min {m (v) ,m (v0) + c (v0, v)} , v ∈ V \ (S ∪ {v0})

este o (s, S ∪ {v0})− marcare a varfurilor lui G.

CAZUL IIIFie G = (V,E) un digrafm si c : E → R functia cost asociata. Presupunem ca G nu contine

circuite de pondere negativa.Fie V = {1, 2, . . . , n}. Oricare ar fi i, j ∈ V definim

D (i, j) := {µ | µ drum de la i la j}

sid (i, j) := min {c (µ) | µ ∈ D (i, j)} .

Pentru µ ∈ D (i, j), notam cu V (µ) multimea varfurilor lui µ, oricare ar fi k ∈ 1, n definim

Dk (i, j) := {µ ∈ D (i, j) | V (µ) \ {i, j} ⊂ {1, 2, 3, . . . , k}} ,

iar Dn (i, j) = D (i, j) , sidk (i, j) := min {c (µ) | µ ∈ Dk (i, j)} ,

iar dn (i, j) = d (i, j) .Algoritmul lui Floyd-Warshall de determinare de drumului de cost minim, se bazeaza pe gasirea

unei relatii de recurenta cu ajutorul careia putem calcula

dk (i, j) , k ∈ 1, n.

45

Page 46: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

12.2. PROBLEMA SAPTAMANII CURSUL 12. PROBLEME DE DRUM MINIM (MAXIM)

Teorema 130 In ipoteze anterioare, oricare ar fi i, j ∈ 1, n, avem{d0 (i, j) = c (i, j)∀k ≥ 0 : dk+1 (i, j) = min {dk (i, j) , dk (i, k + 1) + dk (k + 1, j)} . (12.2)

12.2 Problema saptamanii

12.3 Seminar

46

Page 47: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 13

Algoritmii lui Dantzig si Ford, Dijkstra, Floyd si Warshall

13.1 Teorie . . . . . . . . . . . . . . . 4713.2 Problema saptamanii . . . . . . . 4913.3 Seminar . . . . . . . . . . . . . . 49

13.1 Teorie

CAZUL IFixam s ∈ V . Oricare ar fi i ∈ V, d (s, i) := m (i) si notam cu p (i) varful ce precede varful i pe

un drum de pondere minima de la s la i. Avem ca

m (s) = 0, ∀i < s : m (i) =∞.

Algoritmul 131 (Dantzig si Ford) Acest algoritm returneaza drumul de cost minim ıntr-un grafce nu contine circuite.

1. m (s) := 0, ∀i < s : m (i) =∞; ∀i ≤ s : p (i) := s; h = s;

2. Presupunem cunoscute ∀i ≤ h,m (i) si p (i).

Definim m (h+ 1) = min {m (i) + c (i, h+ 1) | s ≤ i ≤ h} = m (i∗) + c (i∗, h+ 1) ;

p (h+ 1) = i∗;

3. h := h+ 1;

4. Daca h < n

atunci trecem la Pasul 2;

altfel trecem la Pasul 5;

5. Fie t ∈ {1, 2, 3, . . . , n} .Daca m (t) =∞

atunci STOP (nu exista drum de la s la t);

altfel m (t) este ponderea unui drum de pondere minima de la s la t si un astfel

de drum este

µ = (ir, ir−1, . . . , i1, t) , unde

i1 = p (t)i2 = p (i1). . .ir = p (ir−1) = s

.

47

Page 48: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

13.1. TEORIECURSUL 13. ALGORITMII LUI DANTZIG SI FORD, DIJKSTRA, FLOYD SI WARSHALL

CAZUL II

Oricare ar fi v ∈ V , notam cu m (v) ponderea minima de la s la v si cu p (v) varful care ılprecede pe v pe un drum de pondere minima de la s la v.

Algoritmul 132 (Dijkstra) Dam acum un algoritm pentru determinarea drumului de cost minimatunci cand c : E → R+.

1. m (s) := 0, ∀v ∈ V \ {s} : m (v) = c (s, v) ;

∀v ∈ V : p (v) := s;

S = {s} ;

2. Se determina v0 ∈ V \ S astfel ıncat

m (v0) = min {m (v) | v ∈ V \ S} .

3. S := S ∪ {v0} ;

Daca S = V

atunci trecem la Pasul5;

altfel trecem la Pasul4;

4. Oricare ar fi v ∈ V \ S, executa

Daca m (v) > m (v0) + c (v0, v)

atunci m (v) := m (v0) + c (v0, v) ;

p (v) := v0;

5. Oricare ar fi v ∈ V , m (v) reprezinta ponderea minima a unui drum de la s la

v, iar p (v) reprezinta varful ce precede v pe un astfel de drum.

48

Page 49: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 13. ALGORITMII LUI DANTZIG SI FORD, DIJKSTRA, FLOYD SI WARSHALL13.2. PROBLEMA SAPTAMANII

CAZUL III

Algoritmul 133 (Floyd si Warshall) Dam acum un algoritm pentru determinarea drumului decost minim atunci cand G nu contine circuite de pondere negativa.

1. Oricare ar fi i, j ∈ 1, n

d0 (i, j) := c (i, j) ;

p0 (i, j) := i;

k = 0;

2. Oricare ar fi i, j ∈ 1, n, executa

Daca dk (i, j) ≥ dk (i, k + 1) + dk (k + 1, j)

atunci dk+1 (i, j) = dk (i, k + 1) + dk (k + 1, j) ;

pk+1 (i, j) = pk (k + 1, j) ;

3. k := k + 1;

Daca k < n

atunci trecem la Pasul 2;

altfel trecem la Pasul 4;

4. Oricare ar fi i, j ∈ 1, n, dn (i, j) reprezinta ponderea minima a unui drum de la ila j, iar un astfel de drum este

µ = (i, ir, ir−1, . . . , i2, i1, j) , unde

pn (i, j) = i1pn (i, i1) = i2. . .pn (i, ir) = i

.

13.2 Problema saptamanii

13.3 Seminar

49

Page 50: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

13.3. SEMINARCURSUL 13. ALGORITMII LUI DANTZIG SI FORD, DIJKSTRA, FLOYD SI WARSHALL

50

Page 51: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 14

Metoda drumului critic

14.1 Teorie . . . . . . . . . . . . . . . 5114.2 Problema saptamanii . . . . . . . 5314.3 Seminar . . . . . . . . . . . . . . 53

14.1 Teorie

Fie P un proiect, X multimea operatiilui P. Oricare ar fi x ∈ X, notam cu P (x) multimea operatiilorce trebuie efectuate anterior lui x, numita si lista de precedenta. Fie x ∈ X, avem ca

• Daca P (x) = ∅, atunci x se numeste operatie initiala.

• Daca /∃y ∈ X, x ∈ P (y), atunci x se numeste operatie finala.

Definitia 134 Un digraf G = (V,E) este o reprezentare a listelor de precedenta P (x) , x ∈ X, dacaexista o functie injectiva f : X → E astfel ıncat, ∀x, y ∈ X, x ∈ P (y) daca si numai daca exista ınG un drum de la extremitatea finala a lui f (x) la extremitatea initiala a lui f (y).

Exemplu 135 De exemplu, daca X = {a, b, c, d}, atunci avem

x a b c d

P (x) ∅ ∅ a ab.

Observatia 136 Presupunem ca x ∈ P (y) si exista z ∈ P (y) astfel ıncat x ∈ P (z). Atunci xse poate elimina din P (y), caci efectuarea operatiei z va duce implicit si la efectuarea operatiei x.Facand toate liminarile posibile se obtin liste de precedenta ireductibile.

De exemplu, daca luam X = {a, b, c, d, e} cu b ∈ P (d) si ∃c ∈ P (d) astfel ca b ∈ P (c). Atunciputem scrie

x a b c d e

P (x) ∅ a b bc dcP′ (x) ∅ a b c c

,

unde ultima linie reprezinta o lista ireductibila.

Observatia 137 De acum ınainte presupunme ca lucram doar cu liste de precedenta ireductibile.

51

Page 52: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

14.1. TEORIE CURSUL 14. METODA DRUMULUI CRITIC

Oricare ar fi x ∈ X definim

Q (x) :=

x∈P(y)

P (x) , x nu este operatie finala

F , x este operatie finala

,

unde F este multimea tuturor operatiilor finale. Construim digraful G = (V,E) asociat proiectuluiP dupa cum urmeaza:

• ∀x, y ∈ X, x 6= y : P (x) 6= P (y) sau Q (x) 6= Q (y) .

Atunci construim G = (V,E) luand

V = {P (x) | x ∈ X} ∪ {Q (x) | x ∈ X}

siE = {(P (x) , Q (x)) | x ∈ X} ∪ {(Q (x) ,P (y)) | x ∈ P (y) 6= Q (x)} .

Prin urmare, G este o reprezentare a listelor de precedenta P (x) , x ∈ X. Aplicatia f : P →E, f (x) = (P (x) , Q (x)) este injectiva.

Conditia x ∈ P (y) este echivalenta cu

Q (x) = P (y)⇒ ∃µ = (Q (x))

sauQ (x) 6= P (y)⇒ ∃µ = (Q (x) ,P (y)) .

• ∃x ∈ X astfel ıncat

card {y ∈ X | P (x) = P (y) si Q (x) = Q (y)}︸ ︷︷ ︸Ax

≥ 2.

Presupunem ca Ax = {x, y1, y2, . . . , ypx} , px ≥ 1. Atunci construim G = (V,E) luand

V = {P (x) | x ∈ X} ∪ {Q (x) | x ∈ X} ∪ {Q1, Q2, . . . , Qpx | x ∈ X}

si

E = {(P (x) , Q (x)) | x ∈ X} ∪{

(P (x) , Qi) | x ∈ X, i ∈ 1, px}

∪{(Q (x) ,P (y)) | x ∈ P (y) 6= Q (x)} ∪{

(Qi, Q (x)) | x ∈ X, i ∈ 1, px}

= E1 ∪ E2,

unde E1 contine primele doua multimi, iar E2 ultimele doua. Prin urmare, G este o reprezen-tare a listelor de precedenta P (x) , x ∈ X. Aplicatia f : P→ E, f (x) = (P (x) , Qi) , i ∈ 1, px,este injectiva.

Conditia x ∈ P (y) este echivalenta cu

Q (x) = P (y)⇒ ∃µ = (Q (x))

sauQ (x) 6= P (y)⇒ ∃µ = (Q (x) ,P (y)) .

Digraful G = (V,E) astfel construit se numeste digraful asociat proiectului P. Oricare ar fix ∈ X, presupunem cunoscut timpul t (x) necesar efectuarii operatiei x si definim functia costc : E → R prin

c (u, v) :=

{t (x) , (u, v) corespunde operatiei x0 , (u, v) nu corespunde operatiei x

.

Notez cu T timpul minim necesar efectuarii operatiilor proiectului.

Teorema 138 In conditiile date mai sus, avem ca

T = maxµ

c (µ) ,

unde µ parcurge multimea drumurilor de la varful initial ∅ la varfurile finale din F.

52

Page 53: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 14. METODA DRUMULUI CRITIC 14.2. PROBLEMA SAPTAMANII

14.2 Problema saptamanii

14.3 Seminar

53

Page 54: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

14.3. SEMINAR CURSUL 14. METODA DRUMULUI CRITIC

54

Page 55: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

Cursul 15

Diagrame

Diagrame.....

55

Page 56: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 15. DIAGRAME

v0

v1

v2

v3

v4

v5v6v7

v8

v9

v10

v11

v12

v13

v14

v15

v16

v17

v18 v19v20

v21

v22

v23

v24

ΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓ

56

Page 57: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 15. DIAGRAME

ΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓΓ

EmptyStar

v5 v0

v1

v2

v3

v4

EmptyGridG0;0

G0;1

G0;2

G1;0

G1;1

G1;2

G2;0

G2;1

G2;2

G3;0

G3;1

G3;2

G4;0

G4;1

G4;2

57

Page 58: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 15. DIAGRAME

EmptyLader a0 a1 a2 a3 a4

b0 b1 b2 b3 b4

a0

a1

a2

a3

a4

a0

a1

a2

a3

a4

a0

a1

a2

a3

a4

a0

a1

a2

a3

a4

58

Page 59: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 15. DIAGRAME

a0

a1

a2

a3

59

Page 60: Cuprins - math.uaic.romartar/pdf/cursuri si seminarii/teoria... · 1.3. NOTAT˘II GENERALE. NOT˘IUNI RECAPITULATIVE DE COMBINATORICCURSUL 1. NOT˘IUNI PRELIMINARE S˘I SCURTAISTORIC

CURSUL 15. DIAGRAME

Graf cu muchii plecand dintr-un anumit varf

v0

v1

v2

v3

v4

v5

v6

v7

Ciclu

a0

a1

a2

a3

a4

a5

a6

a7

\GraphInit[vstyle=Classic]\SetGraphArtColor{red}{olive}

• Deseneaza un graf ıntre varful mentionat si ultimul varf

v0

v1

v2

v3

v4

v5

v6

v7

60