Cursul 8Teoria Grafurilor. Introducere

noiembrie 2020

Cursul 8

Teoria GrafurilorCuprins

Graf = structură de date pentru modelarea relaţiilor binare dintrecomponentele unui sistem.

G = (V ,E ) undeV : mulţime de noduri = componentele sistemuluiE : listă de muchii = legături/relaţii dintre noduri

Tipuri de grafuri:

I Neorientate:a

b c

d

eV = {a, b, c , d , e}E = [a−b, b−c , b−c , e−c ,

e−e, d−e, d−a, c−a]

I Orientate:a

b c

d

eV = {a, b, c , d , e}E = [a→b, b→c , c→b, e→c ,

e→e, e→d , d→a, c→a]Muchiile orientate se numesc si arce (singular: arc).

Observaţie: Dacă a 6= b atunci:În grafuri neorientate: a−b = b−a (orientarea nu contează)În grafuri orientate: a→b 6= b→a (orientarea contează!)

Cursul 8

Vocabularul teoriei grafurilorTerminologie

Orice muchie este incidentă la 2 noduri (capetele muchiei).

Un arc a→b are sursa a şi destinaţia b.Muchiile de forma a−a sau a→a se numesc bucle.Apariţiile multiple ale unei muchii ı̂n E se numesc muchiiparalele. Exemplu: b−c ı̂nE = [a−b, b−c , b−c , e−c , e−e, d−e, d−a, c−a]Un graf orientat se numeşte şi digraf (engl. directed graph).

Un pseudograf este un graf cu bucle şi muchii paralele.

Un multigraf este un graf fără bucle şi cu muchii paralele.

Un graf simplu este un graf fără bucle şi fără muchii paralele.

⇒ dacă G = (V ,E ) este graf simplu atunci E ⊆ V × V şi scriema→b ı̂n loc de 〈a, b〉 ∈ E .

⇒ cel mai adesea, vom studia grafuri simple.

Cursul 8

Grafuri ponderate

Graf ponderat (G ,w) unde

G = (V ,E ) este un graf

w : E → Runde w(e) este ponderea sau greutatea muchiei e ∈ E .

Dacă G este graf simplu iar e = x−y sau e = x→y , atunci scriemw(x , y) ı̂n loc de w(e).

Exemplu

a

e

b c

d

f

2

7

1

5

12

14

9

3w(a, b) = 3,w(a, e) = 4,w(b, c) = 2

w(c , b) = 9,w(c , f ) = 12,w(c , e) = 1

w(e, b) = 5,w(e, d) = 1,w(d , f ) = 7

Cursul 8

Vocabularul teoriei grafurilor

Ordinul unui graf = numărul de noduri

Mărimea unui graf = numărul de muchii

Mulţimea de vecini a unui nod x ∈ V :V (x) = {y | x−y ∈ E} dacă graful este neorientatV (x) = {y | x→y ∈ E} dacă graful este orientat

Dacă S ⊆ V atunci V (S) =⋃

x∈S V (x).

V [x ] = V (x) ∪ {x}x este nod terminal dacă are un singur vecin: |V (x)| = 1x este nod izolat dacă nu are vecini: |V (x)| = 0Dacă G este graf neorientat:

gradul lui x este deg(x) = |{y | x−y ∈ E}|+ |{y | y−x ∈ E}|secvenţa de grade a lui G este lista gradelor nodurilor din G , ı̂nordine descrescătoare.

Dacă G este digraf:gradul interior al lui x este deg−(x) = |{y | y→x ∈ E}|gradul exterior al lui x este deg+(x) = |{y | x→y ∈ E}|

Cursul 8

Vocabularul teoriei grafurilorExemplu

1

2

3

45

6 Mărimea: 6

Ordinul: 6

v V (v) V [v ] deg(v)

1 {1, 2, 5} {1, 2, 5} 42 {1, 3, 4} {1, 2, 3, 4} 33 {2, 4} {2, 3, 4} 24 {2, 3} {2, 3, 4} 25 {1} {1, 5} 16 ∅ {6} 0

Secvenţa de grade este [4, 3, 2, 2, 1, 0].Nodul 5 este terminal. Nodul 6 este izolat.

Cursul 8

Vocabularul teoriei grafurilorExemplu

1

2

3

45

6 Mărimea: 6

Ordinul: 7

v V (v) V [v ] deg−(v) deg+(v) deg(v)

1 {1, 2, 5} {1, 2, 5} 2 2 42 {1, 3, 4, 5} {1, 2, 3, 4, 5} 3 2 53 {2, 4} {2, 3, 4} 1 1 24 {2, 3} {2, 3, 4} 0 1 15 {1, 3} {1, 3, 5} 1 1 26 ∅ {6} 0 0 0

Secvenţa de grade este lista [5, 4, 2, 2, 1, 0].

Cursul 8

Grafuri izomorfe

Grafurile simple G = (V ,E ) şi H = (V ′,E ′) sunt izomorfe, şi scriemG ' H, dacă există o funcţie bijectivă f : V → V ′ astfel ı̂ncât

x−y ∈ E dacă şi numai dacă f (x)−f (y) ∈ E ′

x→y ∈ E dacă şi numai dacă f (x)→f (y) ∈ E ′

Remarcă. Două grafuri sunt izomorfe dacă putem redenumi nodurileprimului graf cu numele nodurilor celui de-al doilea graf ı̂n aşa fel ı̂ncâtmuchiile dintre noduri să rămână aceleaşi.De exemplu G ' H unde

G :

1

6

8

3

5

2

4

7

H:

a

i d

h

g b

nc

Cursul 8

Vocabularul teoriei grafurilorConectivitate (1)

Dacă G = (V ,E ) este graf neorientat atunci

Un drum sau cale de la x la y ı̂n G este o listă de noduriπ = [x1, x2, . . . , xn] astfel ı̂ncât n ≥ 2, x1 = x , xn = y şixi−xi+1 ∈ E pentru 1 ≤ i < n.

Lungimea drumului este n − 1.Dacă G = (V ,E ) este graf orientat atunci

Un drum sau cale de la x la y ı̂n G este o listă de noduriπ = [x1, x2, . . . , xn] astfel ı̂ncât n ≥ 2, x1 = x , xn = y şixi→xi+1 ∈ E pentru 1 ≤ i < n.

Lungimea drumului este n − 1.

Cursul 8

Vocabularul teoriei grafurilorConectivitate (2)

Scriem x y dacă există drum de la x la y , şix

π y dacă π este un drum de la x la y .

Un drum este

elementar dacă nu conţine de mai multe ori acelaşi nod,hamiltonian dacă este elementar şi conţine toate nodurile

grafului.simplu dacă nu conţine de mai multe ori aceeaşi muchie,

eulerian dacă este simplu şi conţine toate muchiilegrafului.

Un ciclu este un drum simplu de la un nod x la x .

Un ciclu [x1, . . . , xn, x1] este

hamiltonian dacă [x1, . . . , xn] este drum eulerian.eulerian dacă este drum eulerian.

Cursul 8

Vocabularul teoriei grafurilorConectivitate

1

2

3

45

[5, 1, 2, 3, 4, 2] este un drum simplu dar neelementar de lungime 5.[5, 1, 2, 4] şi [5, 1, 2, 3] sunt drumuri elementare de lungime 3.[2, 1, 5, 2, 3, 4, 2] este un ciclu neelementar de lungime 6.[2, 3, 4, 2] este un ciclu elementar de lungime 3.[1, 2, 5, 1, 4, 3, 2, 4] este un drum eulerian.[2, 5, 1, 4, 3, 2] este un ciclu hamiltonian.

1 2

3

4 5

are

drumul hamiltonian [3, 1, 2, 5, 4] şiciclul eulerian [5, 4, 5, 1, 3, 1, 2, 5].

Cursul 8

Vocabularul teoriei grafurilorConectivitate

1

2

3

45

[5, 1, 2, 3, 4, 2] este un drum simplu dar neelementar de lungime 5.[5, 1, 2, 4] şi [5, 1, 2, 3] sunt drumuri elementare de lungime 3.[2, 1, 5, 2, 3, 4, 2] este un ciclu neelementar de lungime 6.[2, 3, 4, 2] este un ciclu elementar de lungime 3.[1, 2, 5, 1, 4, 3, 2, 4] este un drum eulerian.[2, 5, 1, 4, 3, 2] este un ciclu hamiltonian.

1 2

3

4 5

are

drumul hamiltonian [3, 1, 2, 5, 4] şiciclul eulerian [5, 4, 5, 1, 3, 1, 2, 5].

Cursul 8

Vocabularul teoriei grafurilorComponente conexe

Componentele conexe sunt definite pentru grafuri neorientateG = (V ,E ).

Relaţia de conectivitate “ ” este o relaţie de echivalenţă

clasele de echivalenţă ale lui se numesc componente conexe alelui G .

Exemplu.1 7

2 34

5 6 8

9

are 3 componente conexe: {1, 2, 3, 4, 5}, {6, 8, 9} şi {7}.

Cursul 8

Vocabularul teoriei grafurilorComponente tare conexe

Componentele tare conexe, sau tari, sunt definite pentru grafurineorientate G = (V ,E ).

Conectivitatea tare

x ∼ct y :⇔ x y şi y x

este o relaţie de echivalenţă. Clasele de echivalenţă ale lui ∼ct senumesc componente tari ale lui G .

G este tare conex dacă are o singură componentă tare, adică dacăoricare două noduri din V sunt conectate tare.

Exemplu.

1 7

2 34

5 6 8

9

are 3 componente tari: {1, 2, 3, 4, 5}, {6, 8, 9} şi {7}.Cursul 8

Teoreme fundamentale ale Teoriei Grafurilor

Teorema 1. Într-un graf, suma gradelor nodurilor este egală cudublul numărului de muchii.∑

x∈V (G)

deg(x) = 2 · |E (G )|.

Teorema 2. Orice drum de la x la y conţine un drum elementarde la x la y .

Schiţă de demonstraţie:

Cursul 8

Clase de grafuriGrafuri complete (Kn), grafuri nule (En)

Graful complet Kn (n ≥ 1) are V = {1, 2, . . . , n} şiE = {i−j | 1 ≤ i < j ≤ n}.

K1 K2 K3 K4 K5

Graful nul En (n ≥ 1) are V = {1, 2, . . . , n} şi E = ∅.

E1 E2 E3 E4 E5

Cursul 8

Clase de grafuriGrafuri ciclice (Cn), grafuri bipartite complete (Km,n)

Graful ciclic Cn (n ≥ 1) are V = {1, 2, . . . , n} şiE = {i−j | 1 ≤ i ≤ n, j = 1 + (i mod n)}.

C1 C2 C3 C4 C5 C6

Pentru m, n > 0, graful bipartit complet Km,n areV = {xi | 1 ≤ i ≤ m} ∪ {yj | 1 ≤ j ≤ n} şiE = {xi−yj | 1 ≤ i ≤ m, 1 ≤ j ≤ n}

Cursul 8

Clase de grafuriCăi şi arbori

Calea Pn este graful cu V = {1, 2, . . . , n} şiE = {i−j | 1 ≤ i < n, j = i + 1}.

1 2 n − 1 n

Un arbore de ordinul n este un graf simplu conex cu n noduri şi fărăcicluri. Mulţimea acestor arbori se notează cu Tn.

Remarcă. Toţi arborii din Tn au n noduri şi n − 1 muchii.Exemplu. Arbori din clasa T5:

G1: G2: G3:

Cursul 8

Subgraf, subgraf parţial

Fie G = (V ,E ) un graf şi S ⊆ V .Subgraful indus de S ı̂n G este graful G ′ = (S ,E ′) undeE ′ = {e ∈ E |capetele lui e sunt ı̂n S}.G ′ este subgraf al lui G dacă G ′ = G [S ] pentru un S ⊆ V . În acestcaz, mai spunem şi că G ′ este conţinut ı̂n G .

G ′ = (V ′,E ′) este subgraf parţial al lui G dacă V ′ ⊆ V şi E ′ ⊆ E .

Exemplu. Fie G grafulu

ts

w z

y

xv

Subgraf:u

ts

y

xv

Subgraf parţial:u

ts

y

xv

Cursul 8

Subgraf, subgraf parţial

Fie G = (V ,E ) un graf şi S ⊆ V .Subgraful indus de S ı̂n G este graful G ′ = (S ,E ′) undeE ′ = {e ∈ E |capetele lui e sunt ı̂n S}.G ′ este subgraf al lui G dacă G ′ = G [S ] pentru un S ⊆ V . În acestcaz, mai spunem şi că G ′ este conţinut ı̂n G .

G ′ = (V ′,E ′) este subgraf parţial al lui G dacă V ′ ⊆ V şi E ′ ⊆ E .

Exemplu. Fie G grafulu

ts

w z

y

xv

Subgraf:u

ts

y

xv

Subgraf parţial:u

ts

y

xv

Cursul 8

Vocabularul teoriei grafurilorClică, subdiviziune

O n-clică (sau doar clică) a unui graf neorientat G este un subgrafal lui G izomorf cu Kn. De exemplu:

•

•

• •

•

G2

•

•

• •

•

G3

•

•

• •

•

G4

O subdiviziune a unui graf neorientat G este un graf obţinut prinuna sau mai multe inserări succesive de noduri noi pe muchiile luiG . De exemplu:

este subdiviziune a lui K2,2.

nu este subdiviziune a lui K2,2.

Cursul 8

Operaţii cu grafuri

Fie G = (V ,E ) un graf, x ∈ V , S ⊆ V şi T ⊆ E .

G − S este subgraful indus G [V − S ]

G − T este subgraful parţial (V ,E − T )

G \ S este graful (V ′,E ′) obţinut din contracţia nodurilor din S ı̂nun singur nod nou xS :

V ′ = (V − S) ∪ {xS}Dacă G este neorientat atunci

E ′ ={x−y | x , y ∈ V − S şi x−y ∈ E}∪{x−xS | există x−y ∈ E cu x ∈ V − S şi y ∈ S}.

Dacă G este digraf atunci

E ′ ={x→y | x , y ∈ V (G )− S şi x→y ∈ E}∪{x→xS | există x→y ∈ E cu x ∈ V − S şi y ∈ S}∪{xS→y | există x→y ∈ E cu x ∈ S şi y ∈ V − S}.

G \ e este graful G \ S unde S sunt capetele muchiei e.

Cursul 8

Operaţii cu grafuriExemple

1 2

3G1:4 5

1 7

2G2: 34

5 6 8

9

2

3

G1 − {1, 5}4

1 2

3

G1 − (1−5)4 5

x{1,5} 2

3

G1 \ {1, 5} = G1 − (1−5)4

1 7

34

5 6 8

9

G2 − {2}

1 7

2 34

5 6 8

9

G2 − {2→3, 6→3}

7

x{1,2,3,4,5}

6 8

9

G2\{1, 2, 3, 4, 5}

Cursul 8

Vocabularul teoriei grafurilorδ(G), ∆(G), α(G), ω(G)

Fie G = (V ,E ) un graf neorientat şi S ⊆ V .Gradul minim al lui G este δ(G ) = min{deg(x) | x ∈ V }Gradul maxim al lui G este ∆(G ) = max{deg(x) | x ∈ V }Mulţimea de noduri S este stabilă sau independentă dacă nuexistă nici o muchie ı̂ntre noduri din S .

Numărul de independenţă al lui G este α(G ) = max{|S | | Seste mulţime independentă ı̂n G}.Numărul de clică ω(G ) al lui G este ordinul maxim al uneiclici din G , adică ω(G ) = max{n | H este n-clică a lui G}.

Cursul 8

Vocabularul teoriei grafurilor

Exemple

ax

b

ycz

d

s

e

t

G1: G2:

1

2

3

4

5

67

δ(G1) = ∆(G1) = 3, α(G1) = 4, ω(G1) = 2.

δ(G2) = 2, ∆(G2) = 6, α(G2) = 3, ω(G2) = 4.

Cursul 8

Vocabularul teoriei grafurilorArticulaţii şi punţi

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

x ∈ V (G ) este nod de articulaţie (engl. cut vertex) dacăG − {x} nu este conex. Altfel spus, ştergerea lui x distrugeconectivitatea lui G .

e ∈ E (G ) este o punte (engl. bridge) dacă G − e nu esteconex. Altfel spus, ştergerea muchiei e distruge conectivitatealui G .

S ( V (G ) este o mulţime de articulaţie (engl. vertex cut set)a lui G dacă graful G − S nu este conex. Altfel spus,ştergerea nodurilor din S distruge conectivitatea lui G .

Cursul 8

Vocabularul teoriei grafurilorgrad de conectivitate, distanţă, excentricitate, centru, periferie, rază, diametru

Gradul de conectivitate κ(G ) al unui graf incomplet G este numărulminim de noduri ce trebuie eliminate din G pentru a-l deconecta,adică κ(G ) = min{|S | | S este mulţime de articulaţie a lui G}.Dacă k este un ı̂ntreg strict pozitiv, spunem că G este k-conex dacăk ≤ κ(G ).Distanţa d(x , y) de la x la y este cea mai mică lungime a unuidrum de la x la y .

Excentricitatea e(x) a nodului x este distanţa cea mai mare de la xla un nod ı̂n G , adică e(x) = max{d(x , y) | y ∈ V }.Centrul lui G este mulţimea nodurilor cu excentricitate minimă.

Periferia lui G este mulţimea nodurilor cu excentricitate maximă.

Raza lui G este excentricitatea unui nod din centrul lui G , adicăradius(G ) = min{e(x) | x ∈ V }.Diametrul lui G este excentricitatea unui nod de la periferia lui G ,adică diam(G ) = max{e(x) | x ∈ V }.

Cursul 8

Vocabularul teoriei grafurilorExemple

1 G1:

a b c

d e g

hf

are 3 puncte de articulaţie (cele ı̂ncercuite) şi 2 punţi (celeı̂ngroşate).

2 G2:

a b c

d e g

hf

nu are puncte de articulaţie şi nici punţi, dar are mulţimi dearticulaţie cu 2 noduri, de exemplu {c, e}, {f, g} sau {b, e}.Deci κ(G2) = 2.

Cursul 8

Vocabularul teoriei grafurilorExemple

G :

e

zr a

x

c u

v

s

d(x, c) = 2, d(r, z) = 4,

e(x) = e(e) = 2,

e(z) = e(z) = 4,

radius(G ) = 2,

diam(G ) = 4,

G are centrul {x, e},G are periferia {r, z}.

Cursul 8

Reprezentarea grafurilor pe calculator

1 Listă de noduri + listă de muchii

2 Liste de adiacenţă

3 Matrice de adiacenţă

4 Matrice de incidenţă

5 Matrice de ponderi

Cursul 8

Reprezentarea grafurilor1. Cu listă de noduri + listă de muchii

Exemplu

a

b c

d

e

Listă de noduri V = [a, b, c, d , e]Listă de muchii E = [a−b, a−c, a−d , b−c, c−e, d−e]Observaţii: a−b = b−a, a−c = c−a, etc.

muchia a−b ↔ mulţimea {a, b}

a

b c

d

e

Listă de noduri V = [a, b, c, d , e]Listă de arce E = [a→b, c→a, c→b, d→a, e→c, e→d ]Observaţii: a→b 6= b→a, a→c 6= c→a, etc.

arcul a→b ↔ perechea 〈a, b〉

Remarcă

Dacă nu există noduri izolate, nu este necesar să fie reţinută listade noduri V :

I V se poate calcula din E

Cursul 8

Reprezentarea grafurilor2. Cu liste de adiacenţă

Pentru fiecare nod u ∈ V se reţine lista de vecini a lui u.

Exemplu

a

b c

d

e

adj[a] = [b, c, d ]adj[b] = [a, c]adj[c] = [a, b, e]

adj[d ] = [a, e]adj[e] = [c, d ]

a

b c

d

e

adj[a] = [b]adj[b] = []adj[c] = [a, b]

adj[d ] = [a]adj[e] = [c, d ]

Cursul 8

Reprezentarea grafurilor3. Cu matrice de adiacenţă

Presupunem că G = (V ,E ) este un graf cu n noduri.

1 Fixăm o enumerare [x1, x2, . . . , xn] a nodurilor din V .2 Matricea de adiacenţă este AG = (aij) de dimensiune n× n cu

aij := numărul de muchii de la nodul xi la nodul xj .

Observaţii

1 Înainte de a construi AG din G , trebuie fixată o enumerare atuturor nodurilor: [x1, x2, . . . , xn]

2 Dacă G este neorientat, AG este matrice simetrică

3 Dacă G este graf simplu, AG conţine doar 0 şi 1

Cursul 8

Reprezentarea grafurilor cu matrice de adiacenţăExemple

G :a

b c

d

e

Enumerarea nodurilor: [a, b, c , d , e]

AG =

0 1 1 1 01 0 1 0 01 1 0 0 11 0 0 0 10 0 1 1 0

G :a

b c

d

e

Enumerarea nodurilor: [a, b, c , d , e]

AG =

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

Cursul 8

Reprezentarea digrafurilor4. Cu matrice de incidenţă

Presupunem că G = (V ,E ) este digraf.

1 Fixăm o enumerare V = [v1, . . . , vn] a nodurilor din V

2 Fixăm o enumerare E = [e1, . . . , ep] a muchiilor din E

Matricea de incidenţă MG = (mij) are dimensiunea n × p şi

mij =

1 dacă ej are sursa vi−1 dacă ej are destinaţia vi0 ı̂n toate celelalte cazuri.

Exemplu

Dacă V = [a, b, c , d , e], E = [e1, e2, e3, e4, e5, e6, e7, e8] şi

MG =

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

⇒e d

c

b

a

e 1e2

e 3

e4

e5e6

e8

e7

Cursul 8

Reprezentarea grafurilor simple ponderate5. Cu matrice de ponderi

Presupunem că G = ((V ,E ),w) este un graf simplu ponderat.

Fixăm o enumerare [x1, x2, . . . , xn] a nodurilor din V .

Matricea de ponderi WG = (wij) a lui (G ,w) este matricea dedimensiune n × n cu

wij =

0 dacă i = j ,w(xi , xj) dacă xi−xj ∈ E sau xi→xj ∈ E ,+∞ ı̂n celelalte cazuri.

Exemplu (Digraf ponderat cu enumerare de noduri [a, b, c , d , e, f ])

G : a

e

b c

d

f

2

7

1

5

12

14

9

3

⇒WG =

0 3 ∞ ∞ 4 ∞∞ 0 2 ∞ ∞ ∞∞ 9 0 ∞ 1 12∞ ∞ ∞ 0 ∞ 7∞ 5 ∞ 1 0 ∞∞ ∞ ∞ ∞ ∞ 0

Cursul 8

Reprezentarea grafurilorStudiu comparativ pentru un graf cu n noduri şi m muchii

I Reprezentarea cu listă de muchiiAdecvată pentru reprezentarea grafurilor simple fără noduriizolate, cu m� n2Complexitate spaţială (memorie ocupată): O(m)

I Reprezentarea cu liste de adiacenţăPermite enumerarea rapidă a vecinilor unui nodComplexitate spaţială (memorie ocupată): O(n + m)

I Reprezentarea cu matrice de adiacenţă AG = (aij) sau cumatrice de ponderi WG = (wij)

Test rapid de conectivitate directă ı̂ntre 2 noduri: O(1)

@(vi , vj) ∈ E dacă aij = 0 sau dacă wij = ∞Complexitate spaţială (memorie ocupată): O(n2)

- reprezentare neadecvată când m� n2

Reprezentarea cu matrice de incidenţă MGI Complexitate temporală: O(n ·m)

Cursul 8

Un Java API pentru lucrul cu grafuri

Pentru familiarizarea cu algoritmii fundamentali de lucru cu grafuri,vom folosi biblioteca de clase java algs4.jar.

Detalii despre ce oferă această bibliotecă găsiţi aici.

Sugestii de instalare şi utilizare pe laptop-ul personal:

Instalaţi/actualizaţi Eclipse IDE for Java Developers de aiciDescărcaţi algs4.jar de aici.Creaţi un proiect Java EduGraph.Creaţi package-ul ro.uvt.cs.graphs ı̂n cadrul proiectuluiEduGraph.Adăugati biblioteca externă algs4.jar:Properties→Java Build Path→Libraries→Add External JARs

Cursul 8

https://algs4.cs.princeton.edu/https://www.eclipse.org/downloads/packages/https://algs4.cs.princeton.edu/code/