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

(1)

Matematica Discreta

Lezione del giorno 10 gennaio 2012 Matrice di incidenza.

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

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

Ordiniamo in modo arbitrario i vertici:

v

1

, v

2

, v

3

,……., v

r

e gli archi:

a

1

, a

2

, a

3

,……., a

k

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

1

, la seconda riga al vertice v

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 v

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, quindi booleana) è detta appunto matrice di incidenza del grafo non orientato.

Riassumendo: la matrice di incidenza di un grafo non orientato è una matrice booleana rxk dove r è il numero di vertici, k è il numero di archi, e i cui i valori 0,1 nelle caselle sono inseriti secondo la regole detta sopra.

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:

a 6 1 2

b

5 d

3 4

c 7

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 0 0 0 0

1 0 0 1 1 0 0

0 0 1 1 1 1 1

0

1

0

1

(2)

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 (come per la matrice di adiacenza) si può operare il processo inverso, ricavando il grafo non orientato a partire dalla sua matrice di incidenza: data una matrice booleana rxk 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 r vertici, k archi, di cui essa è la matrice di incidenza (basta utilizzare le informazioni su archi e vertici contenute nella matrice).

Anche la matrice di incidenza di un grafo non orientato (come la matrice di adiacenza) 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 v

i

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

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’ esempio del grafo dei ponti il vertice b (corrispondente alla riga 2) ha grado 5 (perché nella riga 2 vi sono 5 valori uguali a 1) e così via per gli altri vertici.

Da queste considerazioni deduciamo un interessante risultato :

Teorema. In un qualunque grafo non orientato, la somma dei gradi dei vertici coincide con il doppio del numero degli archi.

Dimostrazione: Costruiamo la matrice booleana di incidenza del grafo non orientato e contiamo la somma dei valori della matrice per righe e per colonne.

Contando per righe: in ogni riga il numero di 1 corrisponde al grado del vertice corrispondente alla riga, quindi, sommando, si ottiene come totale la somma dei gradi dei vertici.

Contando per colonne: in ogni colonna vi sono esattamente 2 valori =1, quindi, sommando, si ottiene come totale il doppio del numero delle colonne, cioè il doppio del numero degli archi.

Applicando il principio del contare per righe e per colonne si ottiene la tesi.

Dal Teorema precedente deriva una conseguenza notevole:

Corollario. In un qualunque grafo non orientato, il numero di vertici di grado dispari è pari (per convenzione consideriamo pari anche il numero 0, come multiplo di 2 nella forma 20).

Dimostrazione: Siano v

1

,v

2

,...,v

r

gli r vertici del grafo, e siano a

1

,....,a

k

i k archi del grafo.

Supponiamo di avere ordinato i vertici in modo che v

1

,v

2

,....,v

s

siano quelli di grado dispari, e v

s+1

,...,v

r

siano quelli di grado pari.

Se g

1

,g

2

,...,g

s

,g

s+1

,….,g

r

sono rispettivamente i gradi dei vertici v

1

,v

2

,...,v

s

,v

s+1

,…..,v

r

, per il teorema precedente si ha:

2k = g

1

+g

2

+...+g

s

+g

s+1

+…..+g

r

(*)

Poiché per costruzione i gradi g

1

,g

2

,...,g

s

sono dispari, mentre i gradi g

s+1

,g

s+2

,...,g

r

sono pari, si ha:

g

1

=2h

1

+1, ..., g

s

=2h

s

+1, g

s+1

=2h

s+1

, ..., g

r

=2h

r

dove h

1

,...,h

s

,h

s+1

,....,h

r

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

2r= 2(h

1

+....+h

s

+h

s+1

+...+h

r

)+s

s = 2(k-h

1

-....-h

s

-h

s+1

+...-h

r

)

(3)

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

Abbiamo introdotto nelle ultime lezioni due strumenti matematici che possono rappresentare pienamente la struttura di un grafo non orientato: la matrice di adiacenza e la matrice di incidenza.

Vediamo ora come sia possibile ricavare ognuna delle due matrici dall’altra..

Supponiamo per esempio di conoscere la matrice di adiacenza: è una matrice quadrata rxr ad elementi interi 0, simmetrica e con la diagonale principale con elementi tutti nulli, ed inoltre il numero r di righe e colonne coincide con il numero di vertici del grafo.

Possiamo allora costruire la matrice di incidenza nel modo seguente:

- sappiamo che r é il numero dei vertici, e la somma degli elementi numerici di ogni riga della matrice di adiacenza è il grado del vertice corrispondente; inoltre il numero k degli archi può essere ricavato dal Teorema precedente (la somma dei gradi dei vertici coincide con il doppio del numero degli archi); dunque per calcolare k=numero degli archi, divideremo per 2 la somma dei gradi dei vertici (ottenuta sommando tutti i valori numerici della matrice) oppure (visto che la matrice è simmetrica) calcoleremo k 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 dei vertici è 5.

Il numero k 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:

(4)

 





 





. . . . . . . . . . 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

1