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