Matrice di adiacenza e matrice di incidenza.

(1)

Matematica Discreta

Lezione del giorno 1 marzo 2010

Matrice di adiacenza e matrice di incidenza.

Poniamoci il problema di rappresentare un grafo (orientato o non orientato) in forma “digitale” per inserire per esempio la sua struttura come input in un programma da fare svolgere ad un computer.

Consideriamo prima il caso di un grafo non orientato, per esempio il grafo dei “ponti di Konisberg”, una cui rappresentazione nel piano è la seguente:

a 6 1 2

b

5 d

3 4

c 7

In tale grafo vi sono 4 vertici, etichettati con le lettere a,b,c,d, e 7 archi, etichettati con i numeri 1,2,3,4,5,6,7. E’ evidente che la struttura del grafo è determinata non dai “nomi” dei vertici e degli archi ma dalla conoscenza della coppia di vertici estremi di ognuno degli archi.

In base a tale osservazione, introduciamo il concetto di matrice di adiacenza di un grafo non orientato.

Sia dato un grafo non orientato con k vertici. Ordiniamo in modo arbitrario i vertici:

x

1

, x

2

, x

3

,……., x

k

Costruiamo 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 hanno come estremi il vertice x

i

(associato alla riga i) e il vertice x

j

(associato alla colonna j).

La matrice ottenuta (ad elementi numerici interi positivi o nulli) è detta appunto matrice di adiacenza del grafo non orientato.

Tale matrice naturalmente dipende dalla scelta dell’ordine in cui sono elencati i vertici, ma essa descrive pienamente la struttura del grafo e ovviamente si presta bene ad essere immessa come dato

“digitale” in un computer.

Esempio.

Nel grafo dei ponti, se consideriamo il seguente ordinamento dei 4 vertici: a,b,c,d, la matrice di adiacenza del grafo è la matrice 4x4:



 









 







0 1 1 1

1 0 2 0

1 2 0 2

1

0

2

0

(2)

Possiamo notare che tutti gli elementi della cosiddetta “diagonale principale” (\ da alto sinistra a basso destra) sono nulli: questo avverrà in tutte le matrici di adiacenza di un grafo non orientato, perché nella nostra definizione di grafo non orientato non sono consentiti i cappi, cioè archi in cui gli estremi coincidono.

Possiamo ancora notare che a coppie sono uguali gli elementi della forma a

ij

ed a

ji

(riga i colonna j e riga j colonna i) simmetrici rispetto alla diagonale principale (si dice anche che la matrice è una matrice simmetrica): questo avverrà in tutte le matrici di adiacenza di un grafo non orientato, perché l’elemento a

ij

indica il numero di archi che hanno come estremi il vertice x

i

(associato alla riga i) e il vertice x

j

(associato alla colonna j), mentre l’elemento a

ji

indica il numero di archi che hanno come estremi il vertice x

j

(associato alla riga j) e il vertice x

i

(associato alla colonna i), dunque questi numeri sono uguali.

Ovviamente si può operare il processo inverso: data una matrice quadrata kxk (ad elementi interi positivi o nulli) simmetrica e con gli elementi nella diagonale principale tutti nulli, si può costruire un grafo non orientato con k vertici, di cui essa è la matrice di adiacenza.

Esempio.

Data la seguente matrice 4x4 (ad elementi interi positivi o nulli, simmetrica e con gli elementi nella diagonale principale tutti nulli) :



 









 







0 0 1 1

0 0 2 3

1 2 0 1

1 3 1 0

possiamo costruire un grafo non orientato con k vertici, di cui essa è la matrice di adiacenza: se chiamiamo i 4 vertici del grafo con x

1

,x

2

,x

3

,x

4

(ordinatamente corrispondenti alle 4 righe e 4 colonne) una possibile rappresentazione nel piano del grafo è la seguente (in cui vi sono 8 archi 1,2,3,4,5,6,7,8) :

1 x

1

2 x

2

3 x

3

4 5

6 x

4

7 8

La matrice di adiacenza di un grafo non orientato fornisce anche informazioni sul grado dei vertici del grafo: infatti è ovvio che nella generica riga i (o colonna i, che è lo stesso) i valori numerici corrispondono al numero degli archi che hanno come estremi il vertice x

i

e uno fra i vertici x

1

,…, x

k

del grafo, quindi il grado del generico vertice x

i

(corrispondente alla riga i) coincide con la

somma dei valori numerici che si trovano nella riga i (o colonna i) della matrice di adiacenza

del grafo non orientato.

(3)

Un altro modo di rappresentare la struttura di un grafo non orientato è la cosiddetta matrice di incidenza.

Supponiamo che il grafo non orientato abbia k vertici ed r archi.

Ordiniamo in modo arbitrario i vertici:

x

1

, x

2

, x

3

,……., x

k

e gli archi:

a

1

, a

2

, a

3

,……., a

r

Costruiamo poi una matrice kxr (quindi con k righe, r colonne) in cui facciamo corrispondere ordinatamente le righe ai vertici del grafo (la prima riga al vertice x

1

, la seconda riga al vertice x

2

, e così via) e le colonne agli archi del grafo (la prima colonna all’arco a

1

, la seconda colonna all’arco a

2

, e così via).

In ogni casella della matrice, all’incrocio fra la riga i e la colonna j, poniamo il valore numerico 1 se il vertice x

i

(associato alla riga i) è uno degli estremi dell’arco a

j

(associato alla colonna j); in caso contrario poniamo nella casella il valore 0.

La matrice ottenuta (ad elementi numerici interi 0,1) è detta appunto matrice di incidenza del grafo non orientato.

Questo tipo di matrice (ad elementi numerici 0,1) è detta matrice booleana: dunque la matrice di incidenza di un grafo non orientato è una matrice booleana kxr dove k è il numero di vertici, r è il numero di archi del grafo. Ovviamente anche questa matrice dipende dalla scelta dell’ordinamento dei vertici e degli archi, ma fornisce pienamente la struttura del grafo.

Esempio.

Nel grafo dei ponti, rispetto all’ordinamento a,b,c,d dei 4 vertici è all’ordinamento 1,2,3,4,5,6,7 dei 7 archi, la matrice di incidenza è la seguente matrice booleana 4x7:



 









 







1 1 1 1 1 0 0

1 0 0 1 1 0 0

0 0 1 0 0 1 1

0 1 0 0 0 1 1

Nel secondo esempio di grafo non orientato visto prima (con 4 vertici ed 8 archi), la matrice di incidenza (rispetto all’ordinamento x

1

,x

2

,x

3

,x

4

dei vertici e 1,2,3,4,5,6,7,8 degli archi) è la seguente matrice booleana 4x8:



 









 







0 0 0 1 1 0 0 0

1 1 1 0 0 1 0 1

0 0 1 1 0 1 1 0

1 1 0 0 1 0 1 1

Si può notare che in ogni colonna della matrice di incidenza di un grafo non orientato vi saranno esattamente 2 valori uguali a 1 (e tutti gli altri valori uguali a 0): ciò corrisponde al fatto che l’arco corrispondente alla colonna ha esattamente 2 vertici come estremi (corrispondenti alle 2 righe delle caselle con valori 1).

Ovviamente anche in questo caso si può operare il processo inverso: data una matrice booleana kxr

tale che in ogni colonna vi siano esattamente 2 valori uguali a 1 (e tutti gli altri uguali a 0) , si può

costruire un grafo non orientato con k vertici ed r archi, di cui essa è la matrice di incidenza.

(4)

Anche la matrice di incidenza di un grafo non orientato fornisce informazioni sul grado dei vertici del grafo: infatti per costruzione nella generica riga i della matrice i valori uguali a 1 corrispondono agli archi che hanno come uno degli estremi il vertice x

i

(corrispondente alla riga i) quindi il grado del generico vertice x

i

(corrispondente alla riga i) coincide con il numero dei valori uguali a 1 che si trovano nella riga i della matrice di incidenza del grafo non orientato.

Nell’ultimo esempio il vertice x

1

ha grado 5 (perché nella riga 1 vi sono 5 valori uguali a 1) e così via.

Per dimostrare il prossimo risultato, introduciamo il cosiddetto principio del contare per righe e per colonne, il quale afferma che, data una qualunque matrice booleana, la somma del numero dei valori uguali a 1 nelle colonne coincide con la somma dei valori uguali a 1 nelle righe (principio ovvio perché ambedue le somme non sono altro che il numero totale dei valori uguali a 1 nella matrice).

Teorema. In un qualunque grafo non orientato, il numero di vertici di grado dispari é multiplo di 2 (quindi, se non é 0, é un numero naturale pari).

Dimostrazione: Siano x

1

,x

2

,...,x

k

i k vertici distinti del grafo, e siano a

1

,....,a

r

gli r archi distinti del grafo. Costruiamo la matrice kxr di incidenza del grafo con k righe e con r colonne, in cui facciamo corrispondere ordinatamente le righe ai vertici x

1

,x

2

,...,x

k

, e le colonne agli archi a

1

,....,a

r

.

Supponiamo di avere ordinato i vertici in modo che x

1

,x

2

,....,x

s

siano quelli di grado dispari, ed x

s+1

,...,x

k

siano gli altri, cioè quelli di grado multiplo di 2 (quindi 0 o un numero naturale).

Contiamo “per colonne” il numero di 1 nella matrice: abbiamo già notato sopra che in ogni colonna, per costruzione, vi sono esattamente 2 valori uguali ad 1, dunque la somma del numero degli 1 nelle r colonne é 2+2+...+2=2r (il doppio del numero r degli archi).

Contiamo poi “per righe” il numero di 1 nella matrice: abbiamo già notato sopra che in ogni riga, per costruzione, il numero di valori 1 é uguale al grado del vertice corrispondente alla riga, dunque, se indichiamo con g

1

,g

2

,...,g

k

rispettivamente i gradi dei vertici x

1

,x

2

,...,x

k

, la somma del numero degli 1 nelle r colonne é la somma dei gradi g

1

+g

2

+...+g

k

.

Eguagliando (per il principio del contare per righe e per colonne) si ha:

2r = g

1

+g

2

+...+g

k

(*)

Poiché per costruzione i gradi g

1

,g

2

,...,g

s

sono dispari, mentre i gradi g

s+1

,g

s+2

,...,g

k

sono multipli di 2, si ha:

g

1

=2h

1

+1, ..., g

s

=2h

s

+1, g

s+1

=2h

s+1

, ..., g

k

=2h

k

dove h

1

,...,h

s

,h

s+1

,....,h

k

sono opportuni numeri interi . Dall’eguaglianza (*) si ottiene allora:

2r= 2(h

1

+....+h

s

+h

s+1

+...+h

k

)+s s = 2(r-h

1

-....-h

s

-h

s+1

+...-h

r

)

dunque s (il numero dei vertici di grado dispari) é multiplo di 2, come si voleva dimostrare.

Osservazione: notiamo che, nel corso della dimostrazione precedente, abbiamo anche dimostrato (vedere l’eguaglianza (*)) il seguente risultato:

in un qualunque grafo non orientato la somma dei gradi dei vertici coincide con il doppio del

numero degli archi.