Richiami di matematica discreta: grafi e alberi

Paolo CamuratiDip. Automatica e Informatica

Politecnico di Torino

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 2

Grafi Definizione: G = (V,E)

V: insieme finito e non vuoto di vertici E: insieme finito di archi, che

definiscono una relazione binaria su V Grafi orientati/non orientati:

•orientati: arco = coppia ordinata di vertici (u, v) E e u, v V

•non orientati: arco = coppia non ordinata di vertici (u, v) E e u, v V

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 3

Grafi come modelli

Dominio Vertice Arco

comunicazioni telefono, computer fibra ottica, cavo

circuiti porta, registro, processore

filo

meccanica giunto molla

finanza azioni, monete transazioni

trasporti aeroporto, stazione corridoio aereo, linea ferroviaria

giochi posizione sulla scacchiera

mossa lecita

social networks persona amicizia

reti neurali neurone sinapsi

composti chimici

molecola legame

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 4

Esempio: grafo orientato

d

a

e f

b c

Cappio

G={V, E}V={a, b, c, d, e, f}E={(a,b),(b,b),(b,d),(b,e), (d,a),(d,e),(e,d),(f,c)}

NB: in alcuni contesti i cappi possono essere vietati.Se il contesto ammette i cappi, ma il grafo ne è privo, esso si dice SEMPLICE.

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 5

Esempio: grafo non orientato

d

a

e f

b cG={V, E}V={a, b, c, d, e, f}E={(a,b),(b,b)(b,d),(b,e),(c,f)}

Cappio

NB: in alcuni contesti i cappi possono essere vietati.Se il contesto ammette i cappi, ma il grafo ne è privo, esso si dice SEMPLICE.

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 6

Incidenza e adiacenza

Arco (a, b): incidente da vertice a incidente in vertice b incidente sui vertici a e b

Vertici a e b adiacenti:a b (a, b) E

a b

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 7

Grado di un vertice

grafo non orientato: degree(a) = numero di archi incidenti

grafo orientato: in_degree(a)=numero di archi

entranti out_degree(a)=numero di archi

uscenti degree(a)=in_degree(a) +

out_degree(a).

adegree(a) = 3

a

in_degree(a) = 2out_degree(a) = 1degree(a) = 3

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 8

Cammini e raggiungibilità

Cammino p: u p u' in G=(V,E):

(v0,v1,v2,…,vk)

u=v0, u'=vk, i = 1,2,…,k (vi-1,vi) E.

k = lunghezza del cammino. u' è raggiungibile da u p: u p u'

cammino p semplice: (v0,v1,v2,…,vk) p distinti.

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 9

Esempio

d

a

c

bG = (V, E)p: a p d : (a, b), (b, c), (c, d) k = 3d è raggiungibile da ap semplice.

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 10

Cicli

Ciclo = cammino in cui v0=vk.

Ciclo semplice = cammino semplice in cui v0=vk.

Cappio = ciclo di lunghezza 1.Un grafo senza cicli = aciclico.

d

a

e

b

ciclo, k=4

cappio

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 11

Connessione nei grafi non orientati

Grafo non orientato connesso: vi,vj V p vi p vj

Componente connessa: sottografo connesso massimale (= sottoinsiemi per cui vale la proprietà che lo includono). Grafo non orientato connesso: una sola componente connessa.

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 12

Connessione nei grafi orientati

Grafo orientato fortemente connesso: vi,vj V p, p’ vi p vj e vj p’ vi

Componente fortemente connessa: sottografo fortemente connesso massimale. Grafo orientato fortemente connesso: una sola componente fortemente connessa.

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 13

Esempio

a

e

b

f

c

g

d

h

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 14

Grafi densi/sparsi

Dato grafo G = (V, E)|V| = cardinalità dell’insieme V |E| = cardinalità dell’insieme E

grafo denso: |E| |V|2

grafo sparso: |E| << |V|2

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 15

Grafo completo

Definizione:vi, vj V (vi,vj) E

grafo completo non orientato:|E| = |V|(|V|-1)/2 archi

grafo completo orientato:|E| = |V|(|V|-1) archi

a

c

b

d

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 16

Grafo bipartito

Definizione:Grafo non orientato in cui l’insieme V può essere partizionato in 2 sottoinsiemi V1 e V2, tali per cui (vi,vj) E

vi V1 && vj V2

||vj V1 && vi V2

a

b

e

f

c

d

g

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 17

Grafo pesato

w : E R {-, + } w(u,v) = peso dell’arco (u, v)

a

e

b

f

c

g

d

h

5

41

3

7

8

3

1

2

4

9

10

2

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 18

Alberi non radicati (o liberi)Albero non radicato (o libero) = grafo non orientato, connesso, aciclico

Foresta = grafo non orientato, aciclico

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 19

Proprietà

G = (V, E) grafo non orientato E archi, V nodi: G = albero non radicato ogni coppia di nodi connessa da un unico

cammino semplice G connesso, la rimozione di un arco lo

sconnette G connesso e E = V - 1 G aciclico e E = V - 1 G aciclico, l’aggiunta di un arco introduce un

ciclo.

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 20

Alberi radicati

nodo r detto radice relazione di parentela

y antenato di x se y appartiene al cammino da r a x. x discendente di y

antenato proprio se x ypadre/figlio: nodi adiacenti

radice: no padre foglie no figli

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 21

Esempio

r

b

y a

x

y antenato di xx discendente di ya padre di bb figlio di a

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 22

Proprietà di un albero T grado(T) = numero max di figli profondità(x) = lunghezza del

cammino da r a x altezza(T) = profondità massima.

altezza h = 3

profondità = 0

profondità = 1

profondità = 2

profondità = 3

grado 3

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 23

Rappresentazione di alberi

Rappresentazione di un nodo di un albero di grado(T) = kpuntatore al padre, chiave, k puntatori ai k figli

Inefficiente se solo pochi nodi hanno davvero grado k (spazio per tutti i k puntatori allocato, ma molti a NULL).

al padre

k puntatori ai k figli, eventualmente a NULL

chiave……

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 24

Rappresentazione left-child right-sibling

Rappresentazione di un nodo di un albero di grado(T) = kpuntatore al padre, chiave, 1 puntatore al figlio sinistro, 1 puntatore al fratello a destra

Efficiente: sempre solo 2 puntatori, indipendentemente dal grado dell’albero

al padre

al primo dei fratelli a destra

al primo a sinistra dei figli

chiave

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 25

NULL

NULL

NULL

NULL NULL NULL NULL NULL NULL

NULL

NULL

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 26

Alberi binariDefinizione ricorsiva:T:

insieme di nodi vuoto radice, sottoalbero sinistro,

sottoalbero destro.r

left right

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 27

Albero binario completo

Ogni nodo: o foglia o grado = 2

Albero binario completo di altezza h: numero di foglie 2h

numero di nodi = 0 i h 2i = 2h+1 –1

h = 38 foglie15 nodi

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 28

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 29

Albero binario bilanciato

Tutti i cammini radice-foglie sono di ugual lunghezza

Se T è completo, allora T è bilanciato.

A.A. 2013/1404 Richiami di matematica discreta - grafi e

alberi 30

Albero binario quasi bilanciato La lunghezza di tutti i cammini radice-

foglie differisce al massimo di 1.

Riferimenti

Grafi: Cormen 5.4 Sedgewick Part 5 17.1

Alberi: Cormen 5.5 Sedgewick 5.4

A.A. 2013/14 03 Ordinamento iterativo 31