Matematica Discreta Lezione del giorno 11 marzo 2009 Teorema. Sia dato un grafo (orientato o no) con r vertici x

Matematica Discreta

Lezione del giorno 11 marzo 2009

Teorema. Sia dato un grafo (orientato o no) con r vertici x

1

, x

2

, …., x

r

e con matrice di adiacenza M (matrice quadrata rxr).

Supponiamo che, nella costruzione della matrice di adiacenza M, ogni vertice generico x

i

sia associato alla riga i e alla colonna i di M.

Fissiamo un naturale n e due vertici x=x

i

, y=x

j

(non necessariamente distinti) nel grafo. Allora:

l’elemento c

ij

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

ⁿ

rappresenta il numero di cammini di lunghezza n dal vertice x=x

i

al vertice y=x

j

.

Dimostrazione:

Dimostriamo la tesi applicando il principio di induzione. Per n=1 l’implicazione la tesi è vera perché l’elemento c

ij

nella matrice M

¹

=M rappresenta (per costruzione della matrice di adiacenza) il numero degli archi (e quindi dei cammini di lunghezza 1) dal vertice x=x

i

al vertice y=x

j

.

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

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

rappresenta il numero di cammini di lunghezza k+1 dal vertice x=x

i

al vertice y=x

j

. Un generico cammino di lunghezza k+1 dal vertice x=x

i

al vertice y=x

j

toccherà (prima dell’ultimo vertice y=x

j

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

1

, x

2

, …., x

r

.

Se costruiamo i seguenti insiemi:

X

1

= insieme dei cammini di lunghezza k+1 dal vertice x=x

i

al vertice y=x

j

che hanno x

1

come penultimo vertice;

X

2

= insieme dei cammini di lunghezza k+1 dal vertice x=x

i

al vertice y=x

j

che hanno x

2

come penultimo vertice;

...

...

X

r

= insieme dei cammini di lunghezza k+1 dal vertice x=x

i

al vertice y=x

j

che hanno x

r

come penultimo vertice

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

i

al vertice y=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 dal vertice x=x

i

al vertice y=x

j

che ha x

1

come penultimo vertice, si ottiene percorrendo un cammino di lunghezza k dal vertice x=x

i

al vertice x

1

e poi un arco dal vertice x

1

al vertice y=x

j

. 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 dal vertice x=x

i

al vertice x

1

; il numero degli archi dal vertice x

1

al vertice y=x

j

.

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 a

i1

b

1j

+ a

i2

b

2j

+ ……. +a

ir

b

rj

, e tale somma, come visto sopra, coincide proprio con c

ij

,

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

Esempio: considerato il grafo orientato della lezione precedente la cui matrice di adiacenza è la matrice 4x4

M=



 









 







1 0 1 0

0 1 0 0

0 2 0 1

1 0 0 0

calcoliamo le potenze di M con esponente 2,3,4:

M

²

= MxM =



 









 







1 2 1 1

0 1 0 0

1 2 0 0

1 0 1 0

M

³

= M

²

xM =



 









 







2 4 1 1

0 1 0 0

1 2 1 0

1 2 1 1

M

⁴

= M

³

xM =



 









 







3 6 2 1

0 1 0 0

1 4 1 1

2 4 1 1

Poiché (per esempio) nella matrice M

³

l’elemento in riga 4 e colonna 3 é 4, il Teorema precedente assicura che sono 4 in tutto i possibili cammini di lunghezza 3 dal vertice x

4

al vertice x

3

. Tali 4 cammini si possono facilmente trovare in modo esplicito: il primo e il secondo cammino si ottengono percorrendo il cappio di x

4

, l’arco da x

4

a x

2

, e infine uno (a scelta) dei 2 archi da da x

2

a x

3

; il terzo e il quarto cammino si ottengono percorrendo l’arco da x

4

a x

2

, uno (a scelta) dei 2 archi da da x

2

a x

3

, e il cappio di x

3

.

Notiamo che l’elemento in riga 3 e colonna 4 in M

³

é invece 0, dunque non esistono cammini di lunghezza 3 da x

3

a x

4

: tale mancanza di simmetria é dovuta al fatto che il grafo é orientato.

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

i

, y=x

j

in un grafo con matrice di adiacenza M, e fissato un numero naturale n, se esiste o non esiste almeno un cammino di lunghezza n dal vertice x al vertice y: basta calcolare la potenza M

ⁿ

e verificare se l’elemento nella riga i e colonna j é non nullo.

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

i

, y=y

j

, (e non fissiamo la lunghezza del cammino) come decidere se esiste almeno un cammino (di lunghezza opportuna) dal vertice x al vertice y ?

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, dal vertice x al vertice y); 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 dal vertice x al vertice y) e così via,

calcolando le successive potenze M

³

, M

⁴

,... per verificare se esiste un cammino di lunghezza

3,4,.... dal vertice x al vertice y. 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.

Fortunatamente può essere utile il seguente:

Teorema. Sia dato un grafo (orientato o no) e sia r il numero di vertici del grafo. Fissati nel grafo due vertici x, y si ha:

se esiste almeno un cammino dal vertice x al vertice y, allora certamente esiste un cammino dal vertice x al vertice y di lunghezza <r.

Dimostrazione:

Ragioniamo per assurdo: supponiamo che esista almeno un cammino dal vertice x al vertice y, ma che tutti i cammini dal vertice x al vertice y abbiano lunghezza r.

Poiché le lunghezze di tutti questi cammini sono numeri naturali, per il principio del minimo esiste un cammino dal vertice x al vertice y di lunghezza minima, e sia s tale lunghezza minima: per assurdo é sr.

Osserviamo che, essendo s la lunghezza, il numero di vertici toccati dal cammino é s+1>r, e poichè r é il numero dei vertici distinti del grafo, si deduce che almeno due vertici toccati dal cammino coincidono. Se i vertici toccati ordinatamente dal cammino sono x=v

1

,v

2

,...,y=v

s+1

e se v

i

,v

j

sono 2 fra tali vertici che coincidano fra loro, “tagliando” il settore del cammino compreso fra v

i

e v

j

si otterrebbe un cammino dal vertice x al vertice y di lunghezza <s, contraddizione perché s é la lunghezza minima di un cammino dal vertice x al vertice y.

Dal Teorema precedente segue che, dati 2 vertici x,y in un grafo con r vertici distinti, se non esiste un cammino dal vertice x al vertice y di lunghezza <r, allora non esiste nessun cammino dal vertice x al vertice y.

L’algoritmo precedente si può allora raffinare come segue: fissati i vertici x=x

i

, y=y

j

, si calcolano solo le potenze della matrice di adiacenza M con esponente 1,2,....,r-1 (cioé con esponente <r), e in ognuna di esse si verifica se l’elemento nella riga i e colonna j é non nullo; se in una almeno di tali matrici tale elemento é non nullo, si conclude che esiste almeno un cammino dal vertice x al vertice y (la lunghezza di tale cammino coincide con l’esponente di M); se invece in ognuna di tali matrici tale elemento é nullo, si conclude che non esiste nessun cammino dal vertice x al vertice y.

Si può anche compattare l’algoritmo precedente mediante il concetto di somma di matrici: date due matrici M,N entrambe con n righe ed m colonne, la loro somma N+M é la matrice in cui l’elemento generico in riga i e colonna j é ottenuto dalla somma dei 2 elementi di M ed N nella stessa posizione.

Esempio: date le matrici 2x3

M= _



 





1 4 3

3 2

1 N= _



 





2 1 5

1 5 2

la loro somma é la matrice:

M+N= _



 

















2 1 1 4 5 3

1 3 5 2 2

1 = _



 





3 5 8

4 7 3

Se allora nell’algoritmo precedente consideriamo la somma delle matrici:

N=M+M

²

+M

³

+...+M

^r-1

(dove r é il numero di vertici distinti del grafo, ed M é la sua matrice di adiacenza) e se in N l’elemento nella riga i e colonna j é non nullo, si conclude che esiste almeno un cammino dal vertice x al vertice y; se tale elemento é nullo, si conclude che non esiste nessun cammino dal vertice x al vertice y.

Esempio: nell’esempio (già considerato) del grafo non orientato con 4 vertici distinti x

1

, x

2

, x

3

, x

4

x

1

x

2

x

3

x

4

con matrice di adiacenza 4x4:

M=



 









 







0 0 1 1

0 0 2 2

1 2 0 1

1 2 1 0

se calcoliamo le potenze di M con esponente 1,2,3 e sommiamo otteniamo:

M

¹

=M=



 









 







0 0 1 1

0 0 2 2

1 2 0 1

1 2 1 0

; M

²

=MxM=



 









 







2 4 1 1

4 8 2 2

1 2 6 5

1 2 5 6

; M

³

=M

²

xM=



 









 







2 4 11 11

4 8 22 22

11 22 10 11

11 22 11 10

N=M+M

²

+M

³

=



 









 







4 8 14 14

8 16 26 26

14 26 16 17

14 26 17 16

Poiché nella matrice somma tutti gli elementi sono non nulli, si può concludere che comunque due vertici x,y esiste sempre un cammino da x a y, dunque in questo caso il grafo é connesso.

In generale un grafo orientato (con r vertici e matrice di adiacenza M) sarà connesso se e solo se la matrice N=M+M

²

+M

³

+...+M

^r-1

ha tutti gli elementi non nulli.

Matrici booleane e principio del contare per righe e per colonne.

Una matrice ad elementi numerici é detta booleana (dal matematico Boole) o binaria se i suoi elementi sono solo 0,1.

Data una matrice booleana M con n righe ed m colonne, é evidente il seguente principio (detto del

“contare per righe e per colonne”): se si conta il numero degli 1 in ognuna delle n righe e si sommano i risultati, oppure se si conta il numero degli 1 in ognuna delle m colonne e si sommano i risultati, si ottiene lo stesso numero (che ovviamente coincide con il numero totale di 1 presenti nella matrice).

Da tale principio così semplice si possono dedurre risultati interessanti, come il seguente:

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

Dimostrazione: Siano x

1

,x

2

,...,x

r

i vertici distinti del grafo, e siano poi a

1

,....,a

t

gli archi distinti del

grafo. Costruiamo una matrice booleana con t righe e con r colonne (detta talvolta matrice di

incidenza del grafo) in cui facciamo corrispondere ordinatamente le righe agli archi a

1

,....,a

t

del

grafo, e le colonne ai vertici x

1

,x

2

,...,x

r

del grafo: in ogni casella della matrice, all’incrocio fra la

riga i e la colonna j, poniamo il valore 1 se l’arco a

i

(corrispondente alla riga i) ha come estremo il vertice x

j

(corrispondente alla colonna j) mentre poniamo il valore 0 in caso contrario.

Contiamo “per righe” il numero di 1 nella matrice: in ogni riga, per costruzione, vi sono esattamente 2 valori uguali ad 1 (quelli nelle colonne corrispondenti ai 2 vertici estremi distinti dell’arco corrispondente alla riga, ricordando che i cappi nella nostra definizione di grafo non orientato non sono consentiti), e dunque la somma del numero degli 1 nelle t righe é 2+2+...+2=2t (il doppio del numero t degli archi).

Contiamo poi “per colonne” il numero di 1 nella matrice: in ogni colonna, per costruzione, il numero di valori 1 é uguale al numero di archi che hanno come estremo il vertice corrispondente alla colonna, dunque é uguale al grado di tale vertice. Se indichiamo con g

1

,g

2

,...,g

r

rispettivamente i gradi dei vertici x

1

,x

2

,...,x

r

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

1

+g

2

+...+g

r

.

Eguagliando si ha:

2t = g

1

+g

2

+...+g

r

Come si voleva dimostrare.