Richiami di matematica discreta: grafi e alberi Paolo Camurati Dip. Automatica e Informatica...

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


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


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.


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.


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


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


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.


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.


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


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.


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.


alberi 13

Esempio

a

e

b

f

c

g

d

h


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


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


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


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


alberi 18

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

Foresta = grafo non orientato, aciclico


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.


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


alberi 21

Esempio

r

b

y a

x

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


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


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……


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


alberi 25

NULL

NULL

NULL

NULL NULL NULL NULL NULL NULL

NULL

NULL


alberi 26

Alberi binariDefinizione ricorsiva:T:

insieme di nodi vuoto radice, sottoalbero sinistro,

sottoalbero destro.r

left right


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


alberi 28


alberi 29

Albero binario bilanciato

Tutti i cammini radice-foglie sono di ugual lunghezza

Se T è completo, allora T è bilanciato.


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

Richiami di matematica discreta: grafi e alberi Paolo Camurati Dip. Automatica e Informatica...

Documents

Transcript of Richiami di matematica discreta: grafi e alberi Paolo Camurati Dip. Automatica e Informatica...