2411482212651256  0011002212011210 

(1)

Lezione del giorno 12 aprile 2011

Dimostreremo che, se M è la matrice di adiacenza di un grafo non orientato, la matrice potenza M

ⁿ

di base M ed esponente n (calcolata con il prodotto righe per colonne) contiene le informazioni sui cammini di lunghezza n fra 2 qualunque vertici del grafo, come mostra il seguente:

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

ⁿ

all’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

4

che (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

1

al 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

²

= 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

1

x

2

x

3

2 3

4 5 6 x

4

7 I 2 cammini di lunghezza 2 da x

1

a x

3

si ottengono percorrendo l’arco 2 e l’arco 3 oppure l’arco 2 e

l’arco 6.

(2)

Se vogliamo invece calcolare il numero di cammini di lunghezza 2 dal vertice x

3

al 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

³

= M

²

xM =

















2 4 11 11

4 8 22 22

11 22 10 11

11 22 11 10

e tale elemento è uguale a 4. Esplicitamente i 4 cammini di lunghezza 3 da x

3

a x

4

si ottengono percorrendo gli archi 3,2,4 oppure 6,2,4 oppure 1,2,5 oppure 7,2,5.

Dimostriamo ora il Teorema enunciato sopra:

Dimostrazione:

Dimostriamo la tesi applicando il principio di induzione .

Per n=1 la tesi del Teorema è vera perché (per costruzione della matrice di adiacenza) il numero degli archi (e quindi dei cammini di lunghezza 1) con estremi i vertici v,w coincide con l’elemento della matrice potenza M

¹

=M all’incrocio fra la riga di v e la colonna di w.

Supponiamo la tesi vera per n=k e dimostriamola vera per n=k+1.

Supponiamo che l’ordine degli r vertici (rispetto al quale è costruita la matrice di adiacenza) sia:

x

1

,x

2

,…..,x

r

e supponiamo che il vertice v corrisponda alla riga i di M e il vertice w corrisponda alla colonna j di M (quindi v=x

i

, w=xj).

Essendo M

^k+1

=M

^k

xM (prodotto righe per colonne), se la riga i di M

^k

è a

i1

, a

i2

, ……., a

ir

, e se la colonna j di M è b

1j

, b

2j

, …………, b

rj

, l’elemento c

ij

(in riga i e colonna j) della matrice potenza M

^k

é dato dalla formula:

c

ij

= a

i1

b

1j

+ a

i2

b

2j

+ ……. +a

ir

b

rj

.

La tesi é che c

ij

è uguale al numero di cammini di lunghezza k+1 con estremi i vertici v=x

i

, w=xj.

Un generico cammino di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

toccherà (prima dell’ultimo vertice w=x

j

) un penultimo vertice del grafo, che sarà uno degli r vertici x

1

, x

2

, …., x

r

del grafo.

Se costruiamo i seguenti insiemi:

X

1

= insieme dei cammini di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

che hanno x

1

come penultimo vertice;

X

2

= insieme dei cammini di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

che hanno x

2

come penultimo vertice;

...

X

r

= insieme dei cammini di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

che hanno x

r

come penultimo vertice

per contare tutti i cammini di lunghezza k+1 dal vertice v=x

i

al vertice w=x

j

basterà sommare le cardinalità degli insiemi X

1

,X

2

,....,X

r

.

Calcoliamo la cardinalità di X

1

: un generico cammino di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

che ha x

1

come penultimo vertice, si ottiene percorrendo un cammino di lunghezza k con estremi i vertici v=x

i

, w=x

1

(prima scelta) e poi un arco con estremi i vertici x

1

, w=x

j

(seconda scelta). Per il principio delle scelte multiple, per calcolare la cardinalità di X

1

basta moltiplicare i due seguenti numeri:

il numero dei cammini di lunghezza k con estremi i vertici v=x

i

, w=x

1

;

il numero degli archi con estremi i vertici x

1

, w=x

j

.

(3)

Essendo per ipotesi la tesi vera per n=k, il primo numero coincide con l’elemento in riga i e colonna 1 della matrice M

^k

(che é l’elemento a

1i

) mentre (per costruzione della matrice di adiacenza) il secondo numero coincide con l’elemento in riga 1 e colonna j della matrice M (che é l’elemento b

1j

): dunque la cardinalità di X

1

é il prodotto a

i1

b

1j

.

Con ragionamenti analoghi si ha che la cardinalità di X

2

é il prodotto a

i2

b

2j

, e così via fino a ottenere che la cardinalità di X

r

é il prodotto a

ir

b

2r

.

Per quanto detto sopra, il numero dei cammini di lunghezza k+1 dal vertice x=x

i

al vertice y=x

j

sarà la somma delle cardinalità degli insiemi quindi sarà uguale alla somma:

a

i1

b

1j

+ a

i2

b

2j

+ ……. +a

ir

b

rj

= c

ij

dunque la tesi é vera anche per n=k+1.

Il teorema precedente ci fornisce anche un algoritmo per decidere, fissati due vertici v=x

i

, w=x

j

in un grafo non orientato con matrice di adiacenza M, e fissato un numero naturale n, se esiste o non esiste almeno un cammino di lunghezza n con estremi i vertici v, w: basta calcolare la potenza M

ⁿ

e considerare l’elemento nella riga i e colonna j (se tale elemento é non nullo, esiste almeno un cammino di lunghezza n con estremi i vertici v, w, se invece è =0 tale cammino non esiste).

Resta però insoluto un problema più generale: se fissiamo solo i 2 vertici v=x

i

, w=x

j

, (e non fissiamo la lunghezza del cammino) come decidere se esiste almeno un cammino (di lunghezza non prefissata) con estremi i vertici v, w ?

Un possibile algoritmo che risolva questo problema potrebbe essere il seguente: si verifica se nella matrice di adiacenza M l’elemento nella riga i e colonna j é non nullo (in tale caso si conclude che esiste un cammino di lunghezza 1, cioé un arco, con estremi i vertici v, w); se tale elemento é 0, si calcola M

²

e si verifica se nella matrice M

²

l’elemento nella riga i e colonna j é non nullo (in tale caso si conclude che esiste un cammino di lunghezza 2 con estremi i vertici v, w) e così via, calcolando le successive potenze M

³

, M

⁴

,... per verificare se esiste un cammino di lunghezza 3,4,.... con estremi i vertici v, w.

L’evidente difetto di tale algoritmo é che, se a priori non esistesse nessun cammino dal vertice x al vertice y, esso non avrebbe mai termine, perché troveremmo sempre un valore 0 nell’elemento in riga i e colonna j della matrice potenza M

ⁿ