Matematica Discreta
Lezione del giorno 9 marzo 2009
Problema: costruire un algoritmo che, fissati due vertici v, w in un grafo (orientato o non orientato) permetta di calcolare il numero di cammini da v a w.
A tale scopo introduciamo il concetto di matrice di adiacenza di un grafo.
Sia dato un grafo (orientato o non orientato) con n vertici. Ordiniamo in modo arbitrario i vertici:
x
1, x
2, x
3,……., x
kCostruiamo poi una matrice quadrata kxk (quindi con k righe, k colonne) in cui facciamo corrispondere ordinatamente le righe e le colonne ai vertici del grafo (la prima riga e la prima colonna al vertice x
1, la seconda riga e la seconda colonna al vertice x
2, e così via)
In ogni casella della matrice, all’incrocio fra la riga i e la colonna j, poniamo il valore numerico che indica il numero di archi che vanno dal vertice x
i(associato alla riga i) al vertice x
j(associato alla colonna j).
La matrice ottenuta è detta appunto matrice di adiacenza del grafo.
Essa naturalmente dipende dalla scelta dell’ordine in cui sono elencati i vertici.
La matrice di adiacenza é anche uno dei modi più efficienti per memorizzare un grafo in un computer: essa descrive pienamente la struttura del grafo.
Esempi.
Dato il seguente grafo non orientato con 4 vertici {x
1, x
2, x
3, x
4} e 7 archi:
x
1x
2x
3x
4la sua matrice di adiacenza 4x4 (rispetto all’ordine x
1, x
2, x
3, x
4dei vertici) è la seguente:
0 0 1 1
0 0 2 2
1 2 0 1
1 2 1 0
Notiamo che la diagonale è tutta formata da valori 0: i valori nella diagonale corrispondono agli archi che uniscono un vertice con sé stesso, e in un grafo non orientato non sono permessi cappi.
Si può osservare che in un grafo orientato ogni arco (non avendo un verso) collega reciprocamente i
due vertici estremi, quindi nelle matrice di adiacenza il valore numerico nella casella di riga i e
colonna j coincide con quello nella casella di riga j e colonna i (ossia la matrice di adiacenza di un
grafo orientato è simmetrica rispetto alla diagonale “principale” che va da alto-sinistra a basso-
destra). Nell’esempio precedente si nota appunto tale simmetria rispetto alla diagonale principale:
0 0 1 1
0 0 2 2
1 2 0 1
1 2 1 0
Dato invece, per esempio, il grafo orientato con 4 vertici x
1, x
2, x
3, x
4e 7 archi:
x
1x
2x
3x
4la sua matrice di adiacenza 4x4 (rispetto all’ordine x
1, x
2, x
3, x
4dei vertici) è la seguente:
1 0 1 0
0 1 0 0
0 2 0 1
1 0 0 0
(possiamo notare che essa non è simmetrica rispetto alla diagonale principale).
Ovviamente la matrice di adiacenza fornisce informazioni solo sull’esistenza di archi fra vertici, e non in modo diretto sull’esistenza di cammini: illustreremo ora un algoritmo che risolve tale problema.
Prodotto righe per colonne di matrici
Siano date 2 matrici M,N aventi come elementi nelle caselle dei valori numerici, e supponiamo che M sia un matrice nxm, ed N una matrice mxt (notare che il numero di colonne di M coincide con il numero di righe di N).
Siano a
ijil generico elemento di M (all’incrocio fra riga i e colonna j) e b
ijl’analogo elemento di N.
Definiremo ora una nuova matrice nxt, detta prodotto righe per colonne di M per N (e indicata con MxN). Per costruire il generico elemento c
ij(in riga i e colonna j) della matrice prodotto MxN procediamo in questo modo: fissiamo la generica riga i della matrice M
a
i1, a
i2, …………., a
ime la generica colonna j della matrice N b
1j, b
2j, …………, b
mje consideriamo il numero ottenuto moltiplicando ordinatamente gli elementi della riga di M per quelli della colonna di N e sommando i risultati: tale numero (detto prodotto della riga i di M per la colonna j di N) sarà il generico elemento c
ijdella matrice MxN all’incrocio fra riga i e colonna j.
Dunque:
cij = a
i1b
1j+ a
i2b
2j+ ……. +a
imb
mjEsempio: siano date le seguenti matrici rispettivamente 2x3 e 3x4:
M=
1 1 2
2 0
1
N=
3 0 2 1
3 1 1 4
0 1 1 2
Il prodotto righe per colonne MxN sarà una matrice 2x4:
MxN=
?
?
?
?
?
?
?
?
