Matematica Discreta Lezione del giorno 4 marzo 2010

(1)

Matematica Discreta

Lezione del giorno 4 marzo 2010

Dimostriamo 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 n un numero naturale, e v,w due vertici (anche coincidenti) del grafo.

Allora:

il numero di cammini di lunghezza n dal vertice v al vertice 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 al predicato nella variabile n:

P(n) = “il numero di cammini di lunghezza n fra 2 vertici coincide con l’elemento della matrice potenza M

ⁿ

all’incrocio fra la riga e la colonna corrispondenti ai 2 vertici”.

Per n=1 il predicato è vero perché (per costruzione della matrice di adiacenza) il numero degli archi (e quindi dei cammini di lunghezza 1) fra 2 vertici coincide con l’elemento della matrice potenza M

¹

=M all’incrocio fra la riga e la colonna corrispondenti ai 2 vertici.

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

i

al vertice w=xj.

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

i

al vertice 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

.

Se costruiamo i seguenti insiemi:

X

1

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

i

al vertice w=x

j

che hanno x

1

come penultimo vertice;

X

2

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

i

al vertice w=x

j

che hanno x

2

come penultimo vertice;

...

X

r

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

i

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

i

al vertice w=x

j

che ha x

1

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

i

al vertice x

1

e poi un arco dal vertice x

1

al vertice w=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 v=x

i

al vertice x

1

; il numero degli archi dal vertice x

1

al vertice 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

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

.

(2)

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.

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

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