Matematica Discreta Lezione del giorno 29 marzo 2011

(1)

Matematica Discreta

Lezione del giorno 29 marzo 2011

L’ultimo risultato dimostrato nella scorsa lezione è stato il seguente:

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

Da tale risultato deriva una conseguenza interessante:

Teorema. In un qualunque grafo non orientato, il numero di vertici di grado dispari è un multiplo di 2 della forma 2t, dove t è un intero 0 (quindi è =0 oppure è un numero naturale pari 2,4,6,….) Dimostrazione: Siano x

1

,x

2

,...,x

k

i k vertici distinti del grafo, e siano a

1

,....,a

r

gli r archi distinti del grafo. Supponiamo di avere ordinato i vertici in modo che x

1

,x

2

,....,x

s

siano quelli di grado dispari, ed x

s+1

,...,x

k

siano gli altri, cioè quelli di grado multiplo di 2 (quindi di grado 0 oppure un numero naturale pari).

Contiamo “per colonne” il numero di 1 nella matrice: abbiamo già notato sopra che in ogni colonna, per costruzione, vi sono esattamente 2 valori uguali ad 1, dunque la somma del numero degli 1 nelle r colonne é 2+2+...+2=2r (il doppio del numero r degli archi).

Se g

1

,g

2

,...,g

k

sono rispettivamente i gradi dei vertici x

1

,x

2

,...,x

k

,per il teorema precedente si ha:

2r = g

1

+g

2

+...+g

k

(*)

Poiché per costruzione i gradi g

1

,g

2

,...,g

s

sono dispari, mentre i gradi g

s+1

,g

s+2

,...,g

k

sono multipli di 2, si ha:

g

1

=2h

1

+1, ..., g

s

=2h

s

+1, g

s+1

=2h

s+1

, ..., g

k

=2h

k

dove h

1

,...,h

s

,h

s+1

,....,h

k

sono opportuni numeri interi 0.

Dall’eguaglianza (*) si ottiene allora:

2r= 2(h

1

+....+h

s

+h

s+1

+...+h

k

)+s s = 2(r-h

1

-....-h

s

-h

s+1

+...-h

r

)

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

Abbiamo introdotto, nella lezione scorsa, 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 ognuuna delle due matrici dall’altra..

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

Possiamo allora costruire la matrice di incidenza nel modo seguente:

- sappiamo che k é il numero dei vertici, e la somma degli elementi numerici di ogni riga è il grado del vertice corrispondente; inoltre il numero r degli archi potrà essere ricavato dal risultato ottenuto nella lezione precedente (la somma dei gradi dei vertici coincide con il doppio del numero degli archi); dunque per calcolare r divideremo per 2 la somma dei gradi dei vertici (ottenuta sommando tutti i valori numerici della matrice) oppure (visto che la matrice è simmetrica) calcoleremo r sommando i valori numerici della matrice al di sopra (o al di sotto) della diagonale principale - costruiamo una matrice booleana kxr 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.

(2)

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













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

(3)













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

---

Se viceversa conosciamo la matrice di incidenza (è una matrice booleana kxr, dove ogni colonna contiene esattamente 2 valori uguali a 1) possiamo costruire la matrice di adiacenza nel modo seguente:

- sappiamo che k é il numero dei vertici, dunque dobbiamo costruire una matrice quadrata kxk ad elementi interi 0 che sia simmetrica e con la diagonale principale con elementi tutti nulli

- essendo la matrice simmetrica, basta determinare i valori numerici al di sopra della diagonale principale: ogni valore in riga i e colonna j si otterrà calcolando il numero di colonne della matrice di incidenza che presentano i 2 valori uguali a 1 esattamente nelle righe i,j.

Esempio.

Data la seguente matrice booleana 4x12 dove ogni colonna contiene esattamente 2 valori uguali a 1:

















1 1 1 1 1 1 1 0 0 0 1 0

0 1 1 1 0 0 0 1 1 0 0 0

0 0 0 0 1 1 1 1 1 1 0 1

1 0 0 0 0 0 0 0 0 1 1 1

Supponiamo che essa rappresenti la matrice di incidenza di un grafo non orientato, e costruiamo la relativa matrice di adiacenza.

Sarà una matrice quadrata 4x4 simmetrica e con la diagonale principale con elementi tutti nulli:

















0 . . .

. 0 . .

. . 0 .

. . . 0

L’elemento in riga 1 e colonna 2 coincide con il numero di colonne della matrice di incidenza che presentano i 2 valori uguali a 1 esattamente nelle righe 1,2: tali colonne sono in numero di 2 (sono la prima e terza):

















0 . . .

. 0 . .

. . 0 .

. . 2 0

Con calcoli simili si trovano gli elementi al di sopra della diagonale principale:

















0 . . .

. 3 0 . .

3 2 0 .

2 0 2 0

(4)

Infine si completa la matrice con gli elementi simmetrici rispetto alla diagonale, ottenendo la matrice di incidenza:

















0 3 3 2

. 3 0 2 0

3 2 0 2

2 0 2 0

Vogliamo ora illustrare un algoritmo per decidere, dati 2 vertici di un grafo non orientato, se esista o no un cammino fra di essi.

A questo scopo introduciamo un’operazione di prodotto fra matrici.

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 una 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). Per costruire il generico elemento c

ij

(in riga i e colonna j) della matrice prodotto MxN procediamo in questo modo: 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 ottenuto moltiplicando ordinatamente gli elementi della riga di M per quelli della colonna di N e sommando i risultati: tale numero (detto prodotto della riga i di M per la colonna j di N) 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 il “prodotto” della riga 1 di M per la colonna 2 di N, ottenuto dalla 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 MxN.

Potenza di una matrice quadrata

(5)

Se M è una matrice numerica quadrata nxn (quindi con eguale numero di righe e di colonne),

possiamo calcolare il prodotto righe per colonne MxM ottenendo ancora una matrice quadrata nxn,

indicata con M

²

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

prodotto righe per colonne M

²

xM ottenendo una matrice nxn, indicata con M

³