Matematica Discreta
Lezione del giorno 14 dicembre 2011
Vogliamo ora illustrare un algoritmo per decidere, dati 2 vertici di un grafo non orientato, se esista o no un cammino fra di essi.
A questo scopo introduciamo un’operazione di prodotto fra matrici.
Prodotto righe per colonne di matrici
Siano date 2 matrici M,N aventi valori numerici nelle loro caselle, e supponiamo che M sia una 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=
?
?
?
?
?
?
?
?
Per calcolare per esempio l’elemento c
12all’incrocio della riga 1 e della colonna 2 di MxN, si considera il “prodotto” della riga 1 di M per la colonna 2 di N, ottenuto dalla somma dei prodotti degli elementi della riga 1 di M per quelli della colonna 2 di N, ottenendo:
c
12=1•1+0•(-1)+(-2)•2= -3.
Analogamente si calcolano gli altri 7 elementi della matrice prodotto MxN.
Potenza di una matrice quadrata
Se M è una matrice numerica quadrata nxn (quindi con eguale numero di righe e di colonne),
possiamo calcolare il prodotto righe per colonne MxM ottenendo ancora una matrice quadrata nxn,
indicata con M
2e detta potenza di base M ed esponente 2. Analogamente possiamo calcolare il
prodotto righe per colonne M
2xM ottenendo una matrice nxn, indicata con M
3e detta potenza di
base M ed esponente 3. Iterando il procedimento, per ogni naturale n>2 possiamo calcolare il
prodotto righe per colonne M
n-1xM ottenendo ancora una matrice nxn, indicata con M
ne detta
potenza di base M ed esponente n. Convenzionalmente porremo M
1=M.
Teorema. Sia dato un grafo non orientato con r vertici e con matrice di adiacenza M (matrice quadrata rxr). Siano poi v,w due generici vertici (anche coincidenti fra loro) del grafo.
Allora:
per ogni numero naturale n, il numero di cammini di lunghezza n aventi per estremi i vertici v, w coincide con l’elemento della matrice potenza M
nall’incrocio fra la riga corrispondente al vertice v e la colonna corrispondente al vertice w.
(daremo di questo Teorema la dimostrazione in seguito).
Supponendo vero il Teorema, facciamo un esempio:
Esempio: Consideriamo il grafo non orientato con 4 vertici x
1,x
2,x
3,x
4che (rispetto a tale ordine dei vertici) ha come matrice di adiacenza la seguente matrice 4x4:
M=
0 0 1 1
0 0 2 2
1 2 0 1
1 2 1 0
Se vogliamo per esempio calcolare il numero di cammini di lunghezza 2 dal vertice x
1al vertice x
3, secondo il Teorema dobbiamo individuare l’elemento in riga 1 e colonna 3 della matrice potenza di M ad esponente 2:
M
2= MxM =
2 4 1 1
4 8 2 2
1 2 6 5
1 2 5 6
e tale elemento è uguale a 2. Possiamo trovare esplicitamente questi 2 cammini rappresentando nel piano il grafo:
1
x
1x
2x
32 3
4 5 6 x
47
I 2 cammini di lunghezza 2 da x
1a x
3si ottengono percorrendo l’arco 2 e l’arco 3 oppure l’arco 2 e l’arco 6.
Se vogliamo invece calcolare il numero di cammini di lunghezza 2 dal vertice x
3al vertice x
4,
secondo il Teorema dobbiamo individuare l’elemento in riga 3 e colonna 4 della matrice potenza di
M ad esponente 3:
M
3= M
2xM =
2 4 11 11
4 8 22 22
11 22 10 11
11 22 11 10
