Matematica Discreta Lezione del giorno 13 dicembre 2011

(1)

Matematica Discreta

Lezione del giorno 13 dicembre 2011

Nella lezione precedente abbiamo dato le seguenti definizioni (valide sia per grafi orientati che per grafi non orientati):

- un cammino Hamiltoniano in un grafo è un cammino che tocca tutti i vertici del grafo, ognuno una sola volta

- un grafo è detto completo se, comunque dati 2 vertici distinti v, w, esiste sempre almeno un arco che ha v,w come estremi (dunque, nel caso orientato, se esiste almeno un arco dal vertice v al vertice w oppure un arco dal vertice w al vertice v).

Dimostriamo ora un Teorema il cui enunciato è stato anticipato nella lezione precedente:

Teorema. In un grafo completo esiste sempre almeno un cammino Hamiltoniano.

Dimostrazione:

Nel caso non orientato è banale: se v

1

, v

2

,…., v

n

sono i vertici distinti del grafo, per ipotesi esiste un arco a

1

che ha v

1

,v

2

come estremi, esiste un arco a

2

che ha v

2

,v

3

come estremi, etc.., esiste un arco a

n- 1

che ha v

n-1

,v

n

come estremi, egli archi a

1

, a

2

,…., a

n-1

formano un cammino Hamiltoniano.

Nel caso orientato: scegliamo a piacere due vertici distinti v

1

, v

2

: essendo il grafo completo, esiste almeno un arco da v

1

a v

2

o un arco da v

2

a v

1

. Supponiamo per esempio che esista un arco da v

1

a v

2

v

1

v

2

Se il numero totale dei vertici è 2, abbiamo già costruito un cammino Hamiltoniano, che passa per tutti i vertici, ognuno una sola volta.

Poniamoci quindi nel caso in cui il numero dei vertici sia >2.

Illustreremo un procedimento iterativo con cui, supponendo di avere già costruito un cammino che passi per k vertici distinti, riusciamo sempre, se esiste un ulteriore vertice nel grafo, ad inserirlo nel cammino, costruendone uno più lungo. Applicando tale procedimento più volte, potremo, da un cammino che passa per 2 vertici distinti, costruirne uno che passa per 3 vertici distinti; da questo potremo costruirne uno che passa per 4 vertici distinti, finché otterremo un cammino che passa per tutti i vertici del grafo, ognuno una sola volta, ossia un cammino Hamiltoniano.

Supponiamo quindi di avere già costruito un cammino che passi per k vertici distinti:

v

1

v

2

v

3

………….v

k-1

v

k

Sia dato un ulteriore vertice v

k+1

, distinto dai k vertici già toccati: vogliamo inserire tale vertice nel cammino.

Confrontiamo v

k+1

con v

1

: essendo il grafo completo, esisterà un arco da v

k+1

a v

1

o un arco da v

1

a v

k+1

.

Nel caso esista un arco da v

k+1

a v

1

, possiamo inserire il vertice v

k+1

nel cammino in prima posizione, sfruttando appunto tale arco:

v

k+1

v

1

v

2

………….v

k-1

v

k

Poniamo invece il caso che esista un arco da v

1

a v

k+1

:

v

k+1

v

1

v

2

v

3

………….v

k-1

v

k

(2)

In questo caso confrontiamo v

k+1

con v

2

: essendo il grafo completo, esisterà un arco da v

k+1

a v

2

o un arco da v

2

a v

k+1

.

Nel caso esista un arco da v

k+1

a v

2

, possiamo inserire il vertice v

k+1

nel cammino in seconda posizione, sfruttando appunto tale arco, e cancellando l’arco da v

1

a v

2

del cammino iniziale:

v

k+1

v

1

v

2

v

3

………….v

k-1

v

k

Poniamo invece il caso che esista un arco da v

2

a v

k+1

: v

k+1

v

1

v

2

v

3

………….v

k-1

v

k

In questo caso confrontiamo v

k+1

con v

3

etc. etc.

Il procedimento può continuare: se non riusciamo mai ad inserire il vertice v

k+1

nel cammino, alla fine avremo il caso di un arco da v

k

a v

k+1

, e in tale caso potremo inserire v

k+1

in ultima posizione, sfruttando appunto tale arco:

v

1

v

2

v

3

………….v

k-1

v

k

v

k+1

Il paradosso del torneo sportivo.

Supponiamo che si svolga un torneo sportivo (in uno sport dove non siano previsti pareggi, ma solo vittorie e sconfitte, per esempio la pallavolo) a cui partecipano n squadre, che si incontrano a coppie in varie partite .

Supponiamo anche che alla fine del torneo ogni squadra abbia incontrato ogni altra squadra almeno una volta.

Dimostriamo il seguente risultato (che sembra paradossale….):

qualunque sia il risultato delle partite è sempre possibile disporre le squadre del torneo in successione in un opportuno elenco ordinato:

A

1

, A

2

, …….., A

n

in modo che:

la prima squadra A

1

dell’elenco abbia sconfitto almeno una volta la seconda squadra A

2

; la seconda squadra A

2

abbia sconfitto almeno una volta la terza squadra A

3

;

etc…

cioè in modo che ogni squadra abbia sconfitto almeno una volta la squadra che la segue nella

successione (notare che non è detto che la classifica finale del torneo sia proprio la successione data

da A

1

, A

2

, …….., A

n

).

(3)

Per dimostrare tale affermazione possiamo rappresentare il torneo con un grafo orientato, in cui ogni vertice è una delle n squadre, e in cui ogni partita è rappresentata da un arco orientato che ha la coda sulla squadra vincente e la testa sulla perdente.

Poiché per ipotesi ogni squadra ha incontrato ogni altra squadra almeno una volta, il grafo è completo. Per un teorema precedente esiste nel grafo un cammino Hamiltoniano, che tocca tutte le n squadre (vertici) ognuna una sola volta.

Una rappresentazione lineare di tale cammino Hamiltoniano sia per esempio:

A

1

A

2

A

3

A

n-1

A

n

…………..

(dove A

1

,A

2

,….,A

n

sono tutte le squadre distinte del torneo, disposte in un certo ordine).

Si ottiene così la tesi, perché (per come è stato costruito il grafo) nell’elenco ordinato:

A

1

, A

2

, …….., A

n

la prima squadra A

1

dell’elenco ha sconfitto almeno una volta la seconda squadra A

2

; la seconda squadra A

2

ha sconfitto almeno una volta la terza squadra A

3

;

etc…

Esempio: ad un torneo di pallavolo partecipano le 5 squadre A,B,C,D,E. Si svolgono 10 partite con i seguenti risultati

A vince su B; B vince su D; C vince su D; B vince su C; C vince su A; D vince su A; A vince su E;

E vince su B; C vince su E; D vince su E.

Il grafo orientato completo che rappresenta il torneo è il seguente:

A

B E

D

C

Costruiamo un cammino Hamiltoniano, seguendo il metodo iterativo indicato nella dimostrazione del teorema sull’esistenza di cammini Hamiltoniani in grafi completi.

Partiamo da 2 vertici e da un arco che li ha come estremi, per esempio:

A B

Procediamo allungando il cammino con l’inserimento di un nuovo vertice, per esempio C:

confrontiamo C con A, e poiché esiste un arco da C verso A, inseriamo C al primo posto nel cammino:

C A B

(4)

Inseriamo ora per esempio il vertice D: confrontando D con C, si vede che non esiste un arco da D verso C ma un arco da C verso D, quindi confrontiamo D con A, e poiché esiste un arco da D verso A, inseriamo D nel cammino fra C ed A (elidendo l’arco da C verso A):

D

C A B

Inseriamo ora l’ultimo vertice E: confrontando E con C,D,A, si vede che non esistono archi da E verso C,D,A ma esiste un arco da A verso E, quindi confrontiamo E con B, e poiché esiste un arco da E verso B, inseriamo E nel cammino fra A ed B (elidendo l’arco da A verso B), ottenendo infine il cammino Hamiltoniano:

D E

C A B

L’elenco ordinato di squadre C,D,A,E,B è costruito in modo che ognuna abbia sconfitto quella che la segue nella successione (notare che B, ultima nella successione, non coincide con l’ultima nella classifica finale, che è E).

Matrice di adiacenza e matrice di incidenza.

Poniamoci il problema di rappresentare un grafo (orientato o non orientato) in forma “digitale” per inserire per esempio la sua struttura come input in un programma da fare svolgere ad un computer.

Consideriamo prima il caso di un grafo non orientato, per esempio il grafo dei “ponti di Konisberg”, una cui rappresentazione nel piano è la seguente:

a 6 1 2

b

5 d

3 4

c 7

In tale grafo vi sono 4 vertici, etichettati con le lettere a,b,c,d, e 7 archi, etichettati con i numeri 1,2,3,4,5,6,7. E’ evidente che la struttura del grafo è determinata non dai “nomi” dei vertici e degli archi ma dalla conoscenza della coppia di vertici estremi di ognuno degli archi.

In base a tale osservazione, introduciamo il concetto di matrice di adiacenza di un grafo (daremo

all’inizio tale nozione solo nel caso di un grafo non orientato).

(5)

Sia dato un grafo non orientato con k 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 numerico che indica il numero di archi che hanno come estremi il vertice x

i

(associato alla riga i) e il vertice x

j

(associato alla colonna j).

La matrice ottenuta (ad elementi numerici interi positivi o nulli) è detta appunto matrice di adiacenza del grafo non orientato.

Tale matrice naturalmente dipende dalla scelta dell’ordine in cui sono elencati i vertici, ma essa descrive pienamente la struttura del grafo e ovviamente si presta bene ad essere immessa come dato

“digitale” in un computer.

Esempio.

Nel grafo dei ponti, se consideriamo il seguente ordinamento dei 4 vertici: a,b,c,d, la matrice di adiacenza del grafo è la matrice 4x4:



 









 







0 1 1 1

1 0 2 0

1 2 0 2

1 0 2 0

Possiamo notare che tutti gli elementi della cosiddetta “diagonale principale” (\ da alto sinistra a basso destra) sono nulli: questo avverrà in tutte le matrici di adiacenza di un grafo non orientato, perché nella nostra definizione di grafo non orientato non sono consentiti i cappi, cioè archi in cui gli estremi coincidono.

Possiamo ancora notare che a coppie sono uguali gli elementi della forma a

ij

ed a

ji

(riga i colonna j e riga j colonna i) simmetrici rispetto alla diagonale principale (si dice anche che la matrice è una matrice simmetrica): questo avverrà in tutte le matrici di adiacenza di un grafo non orientato, perché l’elemento a

ij

indica il numero di archi che hanno come estremi il vertice x

i

(associato alla riga i) e il vertice x

j

(associato alla colonna j), mentre l’elemento a

ji

indica il numero di archi che hanno come estremi il vertice x

j

(associato alla riga j) e il vertice x

i

(associato alla colonna i), dunque questi numeri sono uguali.

Ovviamente si può operare il processo inverso: data una matrice quadrata kxk (ad elementi interi non negativi) simmetrica e con gli elementi nella diagonale principale tutti nulli, si può costruire un grafo non orientato con k vertici, di cui essa è la matrice di adiacenza.

Esempio.

Data la seguente matrice 4x4 (ad elementi interi positivi o nulli, simmetrica e con gli elementi nella diagonale principale tutti nulli) :



 









 







0 0 1 1

0 0 2 3

1 2 0 1

1 3 1 0

possiamo costruire un grafo non orientato con k vertici, di cui essa è la matrice di adiacenza: se

chiamiamo i 4 vertici del grafo con x

1

,x

2

,x

3

,x

4

(ordinatamente corrispondenti alle 4 righe e 4

colonne) una possibile rappresentazione nel piano del grafo è la seguente (in cui vi sono 8 archi

1,2,3,4,5,6,7,8) :

(6)

1 x

1

2 x

2

3 x

3

4 5

6 x

4

7 8

La matrice di adiacenza di un grafo non orientato fornisce anche informazioni sul grado dei vertici del grafo: infatti è ovvio che nella generica riga i (o colonna i, che è lo stesso) i valori numerici corrispondono al numero degli archi che hanno come estremi il vertice x

i

e uno fra i vertici x

1

,…, x

k

del grafo, quindi il grado del generico vertice x

i

(corrispondente alla riga i) coincide con la somma dei valori numerici che si trovano nella riga i (o egualmente nella colonna i) della matrice di adiacenza del grafo non orientato.