Matematica Discreta Lezione del giorno 20 dicembre 2011

(1)

Matematica Discreta

Lezione del giorno 20 dicembre 2011

Dimostriamo ora il Teorema enunciato nella lezione precedente:

Teorema. Sia dato un grafo non orientato con r vertici e con matrice di adiacenza M (matrice quadrata rxr). Siano poi v,w due generici vertici (anche coincidenti fra loro) del grafo.

Allora:

per ogni numero naturale n, il numero di cammini di lunghezza n aventi per estremi i vertici v, 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:

Dimostriamo la tesi applicando il principio di induzione .

Per n=1 la tesi del Teorema è vera perché (per costruzione della matrice di adiacenza) il numero degli archi (e quindi dei cammini di lunghezza 1) con estremi i vertici v,w coincide con l’elemento della matrice potenza M

¹

=M all’incrocio fra la riga di v e la colonna di w.

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

Supponiamo che l’ordine degli r vertici (rispetto al quale è costruita la matrice di adiacenza) sia:

x

1

,x

2

,…..,x

r

e supponiamo che il vertice v corrisponda alla riga i di M e il vertice w corrisponda alla colonna j di M (quindi v=x

i

, w=xj).

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

è uguale al numero di cammini di lunghezza k+1 con estremi i vertici v=x

i

, w=xj.

Un generico cammino di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

toccherà (prima dell’ultimo vertice w=x

j

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

1

, x

2

, …., x

r

del grafo.

Se costruiamo i seguenti insiemi:

X

1

= insieme dei cammini di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

che hanno x

1

come penultimo vertice;

X

2

= insieme dei cammini di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

che hanno x

2

come penultimo vertice;

...

X

r

= insieme dei cammini di lunghezza k+1 con estremi i vertici v=x

i

, w=x

j

che hanno x

r

come penultimo vertice

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

i

al vertice w=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 con estremi i vertici v=x

i

, w=x

j

che ha x

1

come penultimo vertice, si ottiene percorrendo un cammino di lunghezza k con estremi i vertici v=x

i

, w=x

1

(prima scelta) e poi un arco con estremi i vertici x

1

, w=x

j

(seconda scelta). 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 con estremi i vertici v=x

i

e x

1

; il numero degli archi con estremi i vertici x

1

e w=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

(2)

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 delle cardinalità degli insiemi quindi sarà uguale alla somma:

a

i1

b

1j

+ a

i2

b

2j

+ ……. +a

ir

b

rj

= c

ij

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

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

i

, w=x

j

in un grafo non orientato con matrice di adiacenza M, e fissato un numero naturale n, se esiste o non esiste almeno un cammino di lunghezza n con estremi i vertici v, w: basta calcolare la potenza M

ⁿ

e considerare l’elemento nella riga i e colonna j (se tale elemento é non nullo, esiste almeno un cammino di lunghezza n con estremi i vertici v, w, se invece è =0 tale cammino non esiste).

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

i

, w=x

j

, (e non fissiamo la lunghezza del cammino) come decidere se esiste almeno un cammino (di lunghezza non prefissata) con estremi i vertici v, w ?

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, con estremi i vertici v, w); 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 con estremi i vertici v, w) e così via, calcolando le successive potenze M

³

, M

⁴

,... per verificare se esiste un cammino di lunghezza 3,4,.... con estremi i vertici v, w.

L’evidente difetto di tale ragionamento é che, se a priori non esistesse nessun cammino dal vertice x al vertice y, l’algoritmo illustrato non avrebbe mai termine, perché troveremmo sempre un valore 0 nell’elemento in riga i e colonna j della matrice potenza M

ⁿ

, e non sapremmo quando fermare il procedimento per concludere con certezza che appunto non esiste nessun cammino con estremi i vertici v, w.

Per risolvere tale problema può essere utile il seguente:

Teorema. Sia dato un grafo non orientato e sia r il numero di vertici del grafo. Fissati nel grafo due vertici v, w si ha:

se esiste qualche cammino dal vertice v al vertice w, allora esiste certamente qualche cammino dal vertice v al vertice w che abbia lunghezza <r.

Dimostrazione:

Ragioniamo per assurdo: supponiamo che esista qualche cammino dal vertice v al vertice w, ma che non esista nessun cammino dal vertice v al vertice w che abbia lunghezza <r . Sia allora S l’insieme (non vuoto) delle lunghezze di tutti i possibili cammini da v a w. Per l’Assioma del minimo esiste in S un minimo s: tale s sarà dunque la lunghezza minima di un cammino da v a w. Poiché (per assurdo) non esistono cammini di lunghezza <r dal vertice v al vertice w, sarà certamente s  r.

Se consideriamo un cammino di lunghezza s da v a w, osserviamo che il numero di vertici toccati

dal cammino é s+1 (perché tale numero è sempre di 1 unità superiore al numero di archi percorsi

nel cammino). Da s  r segue s+1>r, dunque il cammino tocca un numero di vertici maggiore del

numero totale r dei vertici distinti del grafo: si deduce che almeno due vertici toccati dal cammino

coincidono. Se i vertici toccati ordinatamente dal cammino sono v=v

1

,v

2

,...,w=v

s+1

e se v

i

,v

j

sono

2 fra tali vertici che coincidono fra loro, “cancellando” il settore del cammino compreso fra v

i

e v

j

si

otterrebbe un cammino dal vertice v al vertice w di lunghezza <s, contraddizione perché s é la

lunghezza minima di un cammino dal vertice v al vertice w.

(3)

L’algoritmo illustrato sopra (per verificare se esiste qualche cammino dal vertice v a l vertice w) si può allora migliorare come segue: fissati i vertici v=x

i

, w=x

j

, si calcolano solo le potenze della matrice di adiacenza M con esponente 1,2,....,r-1 (cioé con esponente <r dove r è il numero dei vertici del grafo), 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 v al vertice w (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 v al vertice w (perché non ne esiste nessuno di lunghezza <r).

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 è sempre il numero di vertici distinti del grafo, ed M é la sua matrice di adiacenza) e se nella matrice N l’elemento nella riga i e colonna j é non nullo, si conclude che esiste almeno un cammino dal vertice v al vertice w; se tale elemento é nullo, si conclude che non esiste nessun cammino dal vertice v al vertice w.

Questo algoritmo può anche essere utilizzato per verificare se il grafo non orientato è connesso: la proprietà che per ogni coppia di vertici esiste almeno un cammino che li collega sarà equivalente alla proprietà che la matrice N=M+M

²

+M

³

+...+M

^r-1

ha tutti gli elementi non nulli.

Esempio.

Consideriamo il grafo non orientato già visto in una delle lezioni precedenti:

1 x

1

x

2

x

3

2 3

4 5 6 x

4

7 con matrice di adiacenza (rispetto all’ordine x

1

,x

2

,x

3

,x

4

dei vertici):

(4)

M =



 









 







0 0 1 1

0 0 2 2

1 2 0 1

1 2 1 0

Si ha:

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

dunque:

N = M+M

²

+M

³

=



 









 







4 8 14 14

8 16 26 26

14 26 16 17

14 26 17 16

Poiché la matrice N ha tutti gli elementi non nulli, possiamo concludere che il grafo è connesso,

come d’altronde era già evidente dalla sua rappresentazione planare.