0011001011011010Notiamo che la diagonale è tutta formata da valori 0 (perché in un grafo non orientato non sonopermessi cappi).Dato il grafo orientato con 4 vertici x

(1)

Matematica Discreta I

Lezioni del giorno 17 dicembre 2007

Problema: costruire un algoritmo che, fissati due vertici v, w in un grafo (orientato o non orientato) permetta di stabilire se esiste o non esiste un cammino da v a w.

A tale scopo introduciamo il concetto di matrice di adiacenza di un grafo.

Sia dato un grafo (orientato o non orientato) con n 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 1 se esiste un arco dal vertice x

i

(associato alla riga i) al vertice x

j

(associato alla colonna j); poniamo invece il valore 0 se tale arco non esiste.

La matrice ottenuta è detta appunto matrice di adiacenza del grafo.

Essa naturalmente dipende dalla scelta dell’ordine in cui sono elencati i vertici.

Esempi.

Dato il grafo non orientato con 4 vertici x

1

, x

2

, x

3

, x

4

:

x

1

x

2

x

3

x

4

la sua matrice di adiacenza 4x4 (rispetto all’ordine x

1

, x

2

, x

3

, x

4

dei vertici) è la seguente:

















0 0 1 1

0 0 1 0

1 1 0 1

1 0 1 0

Notiamo che la diagonale è tutta formata da valori 0 (perché in un grafo non orientato non sono permessi cappi).

Dato il grafo orientato con 4 vertici x

1

, x

2

, x

3

, x

4

:

x

1

x

2

x

3

x

4

la sua matrice di adiacenza 4x4 (rispetto all’ordine x

1

, x

2

, x

3

, x

4

dei vertici) è la seguente:

(2)

















1 0 0 0

0 1 0 0

1 1 0 1

1 0 0 0

Ovviamente la matrice di adiacenza fornisce informazioni solo sull’esistenza di archi fra vertici, e non in modo diretto sull’esistenza di cammini.

Prodotto righe per colonne di matrici

Siano date 2 matrici M,N aventi come elementi nelle caselle dei valori numerici, e supponiamo che M sia un matrice nxm, ed N una matrice mxt (notare che il numero di colonne di M coincide con il numero di righe di N).

Siano a

ij

il generico elemento di M (all’incrocio fra riga i e colonna j) e b

ij

l’analogo elemento di N.

Definiremo ora una nuova matrice nxt, detta prodotto righe per colonne di M per N (e indicata con MxN): fissiamo la generica riga i della matrice M

a

i1

, a

i2

, …………., a

im

e la generica colonna j della matrice N b

1j

, b

2j

, …………, b

mj

e consideriamo il numero reale ottenuto moltiplicando ordinatamente gli elementi della riga di M per quelli della colonna di N e sommando i risultati: tale numero sarà il generico elemento c

ij

della matrice MxN all’incrocio fra riga i e colonna j. Dunque:

cij = a

i1

b

1j

+ a

i2

b

2j

+ ……. +a

im

b

mj

Esempio: siano date le seguenti matrici rispettivamente 2x3 e 3x4:

M=

_



 







 1 1 2

2 0

1

N=



















3 0 2 1

3 1 1 4

0 1 1 2

Il prodotto righe per colonne MxN sarà una matrice 2x4:

MxN=

_



 





?

Per calcolare per esempio l’elemento c

12

all’incrocio della riga 1 e della colonna 2 di MxN, si considera la somma dei prodotti degli elementi della riga 1 di M per quelli della colonna 2 di N, ottenendo c

12

=1•1+0•(-1)+(-2)•2= -3. Analogamente si calcolano gli altri 7 elementi della matrice prodotto.

Matrici booleane e prodotto booleano

Una matrice M è detta booleana (o binaria) se contiene solo valori 0 o 1 nelle caselle.

Per esempio la matrice di adiacenza di un grafo è booleana.

Date 2 matrici booleane M,N tali che M sia una matrice nxm ed N sia una matrice mxt, definiamo

prodotto booleano MxN la matrice booleana ottenuta calcolando il prodotto righe per colonne di M

per N, con le usuali regole per l’aritmetica dei numeri tranne che per la seguente regola: 1+1=1 (se

facessimo valere la normale regola 1+1=2 la matrice prodotto non sarebbe più booleana).

(3)

Nota: in pratica per la somma dei numeri si usano le regole 0+0=0, 1+0=1, 0+1=1, 1+1=1. Si può notare che queste regole corrispondono alla tavola di verità della operazione logica OR.

Se M è una matrice booleana quadrata nxn, possiamo calcolare il prodotto booleano MxM ottenendo una matrice quadrata nxn, indicata con M

²

e detta potenza booleana di base M ed esponente 2. Analogamente possiamo calcolare il prodotto booleano M

²

xM ottenendo una matrice booleana nxn, indicata con M

³

e detta potenza booleana di base M ed esponente 3. Iterando il procedimento, per ogni naturale n>2 possiamo calcolare il prodotto booleano M

^n-1

xM ottenendo ancora una matrice booleana nxn, indicata con M

ⁿ

e detta potenza booleana di base M ed esponente n. Convenzionalmente porremo M

¹

=M.

Siamo ora in grado di dimostrare il teorema che fornisce una condizione necessaria e sufficiente per l’esistenza di un cammino di lunghezza fissata fra 2 vertici.

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

1

, x

2

, …., x

k

e con matrice di adiacenza M (matrice booleana quadrata kxk).

Supponiamo che per costruire la matrice di adiacenza M ogni vertice generico x

i

sia associato alla riga i e alla colonna i.

Fissiamo un naturale n e due vertici x

i

, x

j

nel grafo. Allora:

esiste un cammino di lunghezza n dal vertice x

i

al vertice x

j

 l’elemento c

ij

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

ⁿ

è uguale a 1.

Dimostrazione:

(): Ragioniamo con il principio di induzione. Per n=1 l’implicazione () è vera perché se c

ij

=1 nella matrice M

1

=M, essendo M la matrice di adiacenza, esisterà un arco da x

i

a x

j

quindi un cammino di lunghezza 1 da da x

i

a x

j

.

Supponiamo l’implicazione () vera per n e dimostriamola vera per n+1. Per ipotesi si ha c

ij

=1, dove c

ij

è l’elemento in riga i e colonna j nella matrice M

ⁿ⁺¹

: la tesi è che esiste un cammino di lunghezza n+1 dal vertice x

i

al vertice x

j.

Essendo M

ⁿ⁺¹

=M

ⁿ

xM (prodotto booleano righe per colonne), se la riga i di M

ⁿ

è a

i1

, a

i2

, ……., a

ik

, e se la colonna j di M è b

1j

, b

2j

, …………, b

kj

, si ha 1=c

ij

= a

i1

b

1j

+ a

i2

b

2j

+ ……. +a

ik

b

kj

, dunque almeno uno degli addendi della somma (per esempio l’addendo a

ir

b

rj

) è non nullo, quindi a

ir

b

rj

=1 ossia a

ir

=b

rj

=1. Poiché supponiamo vera per n l’implicazione () , da a

ir

=1 (nella matrice M

ⁿ

) segue che esiste un cammino di lunghezza n dal vertice x

i

al vertice x

r

; ma da b

rj

=1 (nella matrice di adiacenza M) segue che esiste un arco dal vertice x

r

al vertice x

j

.

Allora, percorrendo di seguito il cammino di lunghezza n dal vertice x

i

al vertice x

r

e l’ arco dal vertice x

r

al vertice x

j

, otteniamo in totale un cammino di lunghezza n+1 dal vertice x

i

al vertice x

j

, cioè la tesi.

(): si segue un ragionamento simile a quello precedente, invertendo i passaggi logici.

Esempio: nel grafo orientato seguente

1 2 3 x

1

x

2

x

3

x

4

4 5 6

la cui matrice di adiacenza è la matrice 4x4

(4)

M=

















1 0 0 0

0 1 0 1

0 0 1 0

verifichiamo se esiste un cammino di lunghezza 3 dal vertice x

1

al vertice x

3

. Per il Teorema precedente si tratta di verificare se nella matrice potenza booleana M

³

il valore c

13

è =1.

Calcoliamo le successive potenze booleane di M.

M

²

= MxM =

















1 0 0 0

1 0 1 0

0 1 0 1

M

³

= M

²

xM =

















1 0 0 0

1 1 0 1

1 0 1 0

Poiché in M

3

si ha c

13

=0, non esisterà un cammino di lunghezza 3 dal vertice x

1

al vertice x

3

(notare che esiste un cammino di lunghezza 2 dal vertice x

1

al vertice x

3

, perché nella matrice M

²

si ha c

13

=1).

Invece, essendo c

12

=1 nella matrice M

³

, esisterà un cammino di lunghezza 3 dal vertice x

1

al vertice x

2

e in effetti non è difficile costruire un esempio di tale cammino nel grafo:

v

1

v

2

v

1

v

2