E’ possibile ricavare la matrice di adiacenza di un grafo non orientato conoscendo la sua matrice di incidenza e viceversa.

(1)

Matematica Discreta

Lezione del giorno 3 marzo 2010

E’ possibile ricavare la matrice di adiacenza di un grafo non orientato conoscendo la sua matrice di incidenza e viceversa.

Se per esempio conosciamo la matrice di adiacenza (matrice quadrata kxk ad elementi interi 0, simmetrica e con la diagonale principale con elementi tutti nulli) possiamo costruire quella di incidenza nel modo seguente:

- sappiamo che k é il numero dei vertici, e la somma degli elementi numerici di ogni riga è il grado del vertice corrispondente; inoltre il numero r degli archi potrà essere ricavato dal risultato ottenuto nella lezione precedente (la somma dei gradi dei vertici coincide con il doppio del numero degli archi); dunque per calcolare r divideremo per 2 la somma dei gradi dei vertici (ottenuta sommando tutti i valori numerici della matrice) oppure (visto che la matrice è simmetrica) calcoleremo r sommando i valori numerici della matrice al di sopra (o al di sotto) della diagonale principale - costruiamo una matrice booleana rxk inserendo valori 0,1 nelle caselle nel modo seguente:

esaminando i valori numerici della matrice di adiacenza al di sopra (o al di sotto) della diagonale principale, per ognuno di tali valori t fissiamo t colonne della matrice booleana e inseriamo in ogni colonna 2 valori uguali a 1 nelle 2 righe corrispondenti agli indici di riga e colonna del valore t nella matrice di adiacenza, inserendo poi tutti valori uguali a 0 nelle restanti caselle della colonna.

Esempio.

Data la seguente matrice simmetrica 5x5 e con la diagonale principale con elementi tutti nulli:













0 1 0 0 1

1 0 2 1 0

0 2 0 2 3

0 1 2 0 1

1 0 3 1 0

Supponiamo che essa rappresenti la matrice di adiacenza di un grafo non orientato, e costruiamo la relativa matrice di incidenza.

Il numero r degli archi è la somma degli elementi al di sopra della diagonale principale:

r = 1+3+0+1+2+1+0+2+0+1=11

quindi la matrice booleana da costruire sarà un matrice 5x11:













. . . . . . . . . . .

Esaminiamo i valori numerici della matrice di adiacenza al di sopra della diagonale principale:

- il valore 1 (in riga 1 e colonna 2) implica l’esistenza di 1 arco fra il primo e il secondo vertice, per

cui fissiamo una colonna nella matrice booleana (la prima per esempio) in cui inseriamo 2 valori 1

nelle righe 1,2 e valori 0 altrove:

(2)



 





0 . . . . . . . . . . . . . . 0

. . . . . . . . . . 0

. . . . . . . . . . 1

- il valore 3 (in riga 1 e colonna 3) implica l’esistenza di 3 archi fra il primo e il terzo vertice, per cui fissiamo 3 colonne nella matrice booleana (la seconda, la terza e la quarta per esempio) e in ognuna di esse inseriamo 2 valori 1 nelle righe 1,3 e valori 0 altrove:













. . . . . . . 0 0 0 0

. . . . . . . 1 1 1 0

. . . . . . . 0 0 0 1

. . . . . . . 1 1 1 1

Così procedendo possiamo ottenere alla fine la seguente matrice di incidenza:













1 0 0 0 0 0 1 0 0 0 0

1 1 1 1 0 0 0 0 0 0 0

0 1 1 0 1 1 0 1 1 1 0

0 0 0 1 1 1 0 0 0 0 1

0 0 0 0 0 0 1 1 1 1 1

---

Se viceversa conosciamo la matrice di incidenza (matrice booleana kxr, dove ogni colonna contiene esattamente 2 valori uguali a 1) possiamo costruire quella di adiacenza nel modo seguente:

- sappiamo che k é il numero dei vertici, dunque dobbiamo costruire una matrice quadrata kxk ad elementi interi 0 che sia simmetrica e con la diagonale principale con elementi tutti nulli

- essendo la matrice simmetrica, basta determinare i valori numerici al di sopra della diagonale principale: ogni valore in riga i e colonna j si otterrà calcolando il numero di colonne della matrice di incidenza che presentano i 2 valori uguali a 1 esattamente nelle righe i,j.

Esempio.

Data la seguente matrice booleana 4x12 dove ogni colonna contiene esattamente 2 valori uguali a 1:

















1 1 1 1 1 1 1 0 0 0 1 0

0 1 1 1 0 0 0 1 1 0 0 0

0 0 0 0 1 1 1 1 1 1 0 1

1 0 0 0 0 0 0 0 0 1 1 1

Supponiamo che essa rappresenti la matrice di incidenza di un grafo non orientato, e costruiamo la relativa matrice di adiacenza.

Sarà una matrice quadrata 4x4 simmetrica e con la diagonale principale con elementi tutti nulli:

(3)

















0 . . .

. 0 . .

. . 0 .

. . . 0

L’elemento in riga 1 e colonna 2 coincide con il numero di colonne della matrice di incidenza che presentano i 2 valori uguali a 1 esattamente nelle righe 1,2: tali colonne sono in numero di 2 (sono la prima e terza):

















0 . . .

. 0 . .

. . 0 .

. . 2 0

Con calcoli simili si trovano gli elementi al di sopra della diagonale principale:

















0 . . .

. 3 0 . .

3 2 0 .

2 0 2 0

Infine si completa la matrice con gli elementi simmetrici rispetto alla diagonale, ottenendo la matrice di incidenza:

















0 3 3 2

. 3 0 2 0

3 2 0 2

2 0 2 0

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 come elementi nelle caselle dei valori numerici, 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

ij

il generico elemento di M (all’incrocio fra riga i e colonna j) e b

ij

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

im

e la generica colonna j della matrice N b

1j

, b

2j

, …………, b

mj

e 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

ij

della matrice MxN all’incrocio fra riga i e colonna j.

Dunque:

(4)

cij = a

i1

b

1j

+ a

i2

b

2j

+ ……. +a

im

b

mj

Esempio: 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

12

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

²

e detta potenza di base M ed esponente 2. Analogamente possiamo calcolare il prodotto righe per colonne M

²

xM ottenendo una matrice nxn, indicata con M

³

e 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-1

xM ottenendo ancora una matrice nxn, indicata con M

ⁿ

e detta potenza di base M ed esponente n. Convenzionalmente porremo M

¹

=M.

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 n un numero naturale, e v,w due vertici (anche coincidenti) del grafo.

Allora:

il numero di cammini di lunghezza n dal vertice v al vertice 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.

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

(5)

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.

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