Matematica Discreta Lezione del giorno 22 marzo 2011 Il paradosso del torneo sportivo.

(1)

Matematica Discreta

Lezione del giorno 22 marzo 2011 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….):

è 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

).

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:

(2)

A

B E

D

C

Costruiamo un cammino Hamiltoniano, seguendo il metodo iterativo indicato nella dimostrazione del teorema sui cammini Hamiltoniani.

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

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

(3)

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

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

(4)

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 positivi o nulli) 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) :

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 colonna i) della matrice di adiacenza

del grafo non orientato.

(5)

Un altro modo di rappresentare la struttura di un grafo non orientato è la cosiddetta matrice di incidenza.

Supponiamo che il grafo non orientato abbia k vertici ed r archi.

Ordiniamo in modo arbitrario i vertici:

x

1

, x

2

, x

3

,……., x

k

e gli archi:

a

1

, a

2

, a

3

,……., a

r

Costruiamo poi una matrice kxr (quindi con k righe, r colonne) in cui facciamo corrispondere ordinatamente le righe ai vertici del grafo (la prima riga al vertice x

1

, la seconda riga al vertice x

2

, e così via) e le colonne agli archi del grafo (la prima colonna all’arco a

1

, la seconda colonna all’arco a

2

, e così via).

In ogni casella della matrice, all’incrocio fra la riga i e la colonna j, poniamo il valore numerico 1 se il vertice x

i

(associato alla riga i) è uno degli estremi dell’arco a

j

(associato alla colonna j); in caso contrario poniamo nella casella il valore 0.

La matrice ottenuta (ad elementi numerici interi 0,1) è detta appunto matrice di incidenza del grafo non orientato.

Questo tipo di matrice (ad elementi numerici 0,1) è detta matrice booleana: dunque la matrice di incidenza di un grafo non orientato è una matrice booleana kxr dove k è il numero di vertici, r è il numero di archi del grafo. Ovviamente anche questa matrice dipende dalla scelta dell’ordinamento dei vertici e degli archi, ma fornisce pienamente la struttura del grafo.

Esempio.

Nel grafo dei ponti, rispetto all’ordinamento a,b,c,d dei 4 vertici è all’ordinamento 1,2,3,4,5,6,7 dei 7 archi, la matrice di incidenza è la seguente matrice booleana 4x7:



 









 







1 1 1 1 1 0 0

1 0 0 1 1 0 0

0 0 1 0 0 1 1

0 1 0 0 0 1 1

Nel secondo esempio di grafo non orientato visto prima (con 4 vertici ed 8 archi), la matrice di incidenza (rispetto all’ordinamento x

1

,x

2

,x

3

,x

4

dei vertici e 1,2,3,4,5,6,7,8 degli archi) è la seguente matrice booleana 4x8:



 









 







0 0 0 1 1 0 0 0

1 1 1 0 0 1 0 1

0 0 1 1 0 1 1 0

1 1 0 0 1 0 1 1

Si può notare che in ogni colonna della matrice di incidenza di un grafo non orientato vi saranno esattamente 2 valori uguali a 1 (e tutti gli altri valori uguali a 0): ciò corrisponde al fatto che l’arco corrispondente alla colonna ha esattamente 2 vertici come estremi (corrispondenti alle 2 righe delle caselle con valori 1).

Ovviamente anche in questo caso si può operare il processo inverso: data una matrice booleana kxr tale che in ogni colonna vi siano esattamente 2 valori uguali a 1 (e tutti gli altri uguali a 0) , si può costruire un grafo non orientato con k vertici ed r archi, di cui essa è la matrice di incidenza.

Anche la matrice di incidenza di un grafo non orientato fornisce informazioni sul grado dei vertici

del grafo: infatti per costruzione nella generica riga i della matrice i valori uguali a 1 corrispondono

agli archi che hanno come uno degli estremi il vertice x

i

(corrispondente alla riga i) quindi il grado

(6)

del generico vertice x

i

(corrispondente alla riga i) coincide con il numero dei valori uguali a 1 che si trovano nella riga i della matrice di incidenza del grafo non orientato.

Nell’ultimo esempio il vertice x

1

ha grado 5 (perché nella riga 1 vi sono 5 valori uguali a 1) e così via.

Per dimostrare il prossimo risultato, introduciamo il cosiddetto principio del contare per righe e per colonne, il quale afferma che, data una qualunque matrice booleana, la somma del numero dei valori uguali a 1 nelle colonne coincide con la somma dei valori uguali a 1 nelle righe (principio ovvio perché ambedue le somme non sono altro che il numero totale dei valori uguali a 1 nella matrice).

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

Dimostrazione: Costruiamo la matrice booleana di incidenza del grafo non orientato e contiamo il numero di 1 per righe e per colonne.

Contando per righe: in ogni riga il numero di 1 corrisponde al grado del vertice corrispondente alla riga, quindi, sommando i risultati, si ottiene come totale la somma dei gradi dei vertici.

Contando per colonne: in ogni colonna vi sono esattamente 2 valori =1, quindi sommando si ottiene come totale il doppio del numero delle colonne, cioè il doppio del numero dei vertici.