0....30..320.2020

(1)

Matematica Discreta

Lezione del giorno 11 gennaio 2012

Se viceversa conosciamo la matrice di incidenza (è una matrice booleana kxr, dove ogni colonna contiene esattamente 2 valori uguali a 1) possiamo costruire la matrice 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:



 









 







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:

(2)



 









 







0 3 3 2

. 3 0 2 0

3 2 0 2

2 0 2 0

Matrice di adiacenza e di incidenza nel caso di un grafo orientato.

La matrice di adiacenza si può anche definire per un grafo non orientato, ma in tale caso si deve tenere conto che ogni arco ha un verso dal vertice di origine (“coda”) al vertice di arrivo (“testa”).

Dato un grafo orientato con r vertici definiamo matrice di adiacenza del grafo la matrice quadrata rxr in cui i vertici corrispondono ordinatamente a righe e colonne, e in cui in ogni casella all’incrocio fra una riga e una colonna inseriamo il numero degli archi che hanno coda nel vertice corrispondente alla riga e testa nel vertice corrispondente alla colonna.

Ovviamente nel caso orientato la matrice di adiacenza non è in genere più simmetrica (se esiste un arco da v verso w non è detto che ne esista uno da w verso v). Inoltre le caselle della diagonale principale possono contenere valori non nulli, perché sono consentiti i cappi.

Esempio:

Dato il grafo orientato con 4 vertici x

1

, x

2

, x

3

, x

4

e 7 archi:

x

1

1 x

2

2 x

3

3 4 5

7 x

4

6 la sua matrice di adiacenza 4x4 (rispetto all’ordine x

1

, x

2

, x

3

, x

4

dei vertici) è la seguente:



 









 







1 0 1 0

0 1 0 0

0 2 0 1

1 0 0 0

Si dimostra facilmente che continuano a valere risultati simili a quelli ottenuti nel caso di grafi orientati. Per esempio:

in un grafo orientato con r vertici e matrice di adiacenza M, fissati 2 vertici v, w

j

, per ogni numero naturale n il valore nella riga di v e colonna di w della matrice potenza M

ⁿ

rappresenta il numero di cammini di lunghezza n che hanno v come vertice iniziale del cammino e w come vertice finale del cammino (dunque se tale elemento è 0 si può concludere che esiste qualche cammino di lunghezza n che ha v come vertice iniziale del cammino e w come vertice finale del cammino).

Anche la matrice di incidenza si può definire nel caso di un grafo orientato privo di cappi (d’altra parte omettere i cappi in un grafo orientato non cambia sostanzialmente la struttura del grafo).

Se r è il numero dei vertici, k il numero degli archi del grafo orientato privo di cappi, la matrice di

incidenza è una matrice rxk in cui i vertici corrispondono ordinatamente alle righe e gli archi alle

colonne, in cui in ogni casella all’incrocio fra una riga e una colonna inseriamo il valore +1 se il

(3)

vertice corrispondente alla riga è la coda dell’arco corrispondente alla colonna, il valore -1 se il vertice corrispondente alla riga è la testa dell’arco corrispondente alla colonna, il valore 0 se il vertice corrispondente alla riga non è estremo dell’arco corrispondente alla colonna.

Esempio: Dato il grafo orientato senza cappi con 4 vertici x

1

, x

2

, x

3

, x

4

e 5 archi 1,2,3,4,5:

x

1

1 x

2

2 x

3

3 4

5 x

4

la sua matrice di adiacenza 4x4 (rispetto all’ordine x

1

, x

2

, x

3

, x

4

dei vertici e all’ordine 1,2,3,4,5 degli archi)) è la seguente matrice 4x5:

1 0 1 0 0

1 1 0 1 1

0 1 0 0 1

0 0 1 1 0

 

 

     

 

   

 

 

 

Notare che nel caso di un grafo orientato la matrice di incidenza non è più booleana, e in ogni

colonna vi sono esattamente 2 valori diversi da 0 che coincidono con +1 e -1,