Lezione del giorno 16 maggio 2011 Teoria dei 2-disegni.

(1)

Lezione del giorno 16 maggio 2011 Teoria dei 2-disegni.

Supponiamo che, date v squadre sportive diverse, si debbano organizzare dei tornei a ognuno dei quali partecipano solo alcune di tali squadre. Per uno svolgimento equilibrato dei tornei (in vista per esempio di una classifica finale) è ovviamente opportuno richiedere che:

- ad ogni torneo partecipi lo stesso numero k di squadre, con k uguale per tutti i tornei;

- ogni coppia di squadre si incontri in uno stesso numero r

1

di tornei, con r

1

uguale per tutte le coppie

Esempio: sia v=8, k=4, r

1

=3 (in totale 8 squadre: si pretende che ad ogni torneo partecipino 4 squadre, ed ogni coppia di squadre si incontri esattamente in 3 tornei). È possibile, con questi dati, organizzare i tornei? E quanti tornei?

Con i dati precedenti la risposta è positiva; infatti, se l’insieme delle 8 squadre è A=1,2,3,4,5,6,7,8 si possono organizzare 14 tornei per esempio secondo lo schema seguente:

{1,2,5,6} {3,4,7,8} {1,3,5,7} {2,4,6,8} {1,4,5,8} {2,3,6,7} {1,2,3,4} {5,6,7,8}{1,2,7,8} {3,4,5,6}

{1,3,6,8} {2,4,5,7} {1,4,6,7} {2,3,5,8}

Notiamo che ogni coppia di squadre si incontra effettivamente in 3 tornei: per esempio la coppia (1,2) nel 1°, 7° e 9° torneo, la coppia (1,3) nel 3°,7° e 11° torneo etc.. (si può effettuare la verifica per tutte le altre possibili coppie di squadre).

Anche in questo caso, come nella Teoria dei Disegni si può formalizzare il problema pervenendo alla seguente definizione.

Dati i numeri naturali v,k,r

1

si chiama 2-disegno di parametri (v,k,r

1

) una struttura formata da:

- un insieme A di cardinalità v;

- alcuni sottoinsiemi di A (detti blocchi del disegno), tutti della stessa cardinalità k e tali che ogni coppia di elementi di A appartenga esattamente ad r

1

blocchi

L’esempio precedente è un esempio di 2-disegno di parametri (8,4,3).

Esaminando i blocchi in questo esempio, notiamo che ogni elemento di A appartiene esattamente a 7 blocchi (per esempio l’elemento 1 al 1°,3°,5°,7°,9°,11°,13° blocco, l’elemento 2 al 1°,4°,6°,7°,9°,12°,14° blocco etc…), quindi il 2-disegno di parametri (8,4,3) è nello stesso tempo un disegno di parametri (8,4,7). Ciò non è casuale:

Teorema. Un 2-disegno di parametri (v,k,r

1

) è sempre anche un disegno di parametri (v,k,r) dove il parametro r ha il valore r=r

1

(v-1)/(k-1).

Dimostrazione: Supponiamo dato un 2-disegno di parametri (v,k,r

1

): la tesi è che esso è anche un disegno di parametri (v,k,r=r

1

(v-1)/(k-1)), quindi per dimostrare la tesi dobbiamo verificare che ogni elemento appare in un numero costante r di blocchi, dove r=r

1

(v-1)/(k-1) (questo valore deve essere uguale per tutti gli elementi).

Sia A= {a

1

, a

2

, …., a

v

} l’insieme di cardinalità v sul quale è costruito il 2-disegno, e fissiamo per esempio l’elemento a

1

(per gli altri elementi si ragiona in modo analogo).

Sia r il numero dei blocchi del 2-disegno che contengono a

1

come elemento: la tesi, come detto, è che r=r

1

(v-1)/(k-1).

Siano B

1

, B

2

, ……, B

r

i blocchi del 2-disegno che contengono l’elemento a

1

.

Costruiamo una matrice booleana con r colonne e con (v-1) righe, in cui alle righe si fanno

corrispondere ordinatamente gli elementi a

2

,…..a

v

di A (quindi gli elementi di A diversi da a

1

), e

alle colonne si fanno corrispondere ordinatamente i blocchi B

1

,B

2

,…B

r

(quindi i blocchi che

contengono a

1

), mentre in ogni casella all’incrocio fra riga i e colonna j si pone il valore 1 se

l’elemento a

i

appartiene al blocco B

j

, e il valore 0 in caso contrario.

(2)

Il fatto che ogni blocco B

j

abbia cardinalità k dice che ogni colonna della matrice contiene esattamente (k-1) valori =1 (tenendo conto che già l’elemento a

1

appartiene al blocco); dunque, contando per colonne, il numero di valori =1 è (k-1)+….+(k-1)=(k-1)r.

Se a

i

è un generico elemento di A distinto da a

1

, la riga corrispondente ad a

i

contiene esattamente r

1

valori =1 (ognuno di tali valori =1 corrisponde ad un blocco che contiene la coppia a

1

, a

i

, ed il numero di tali blocchi è appunto r

1

, per definizione di 2-disegno); dunque, contando per righe, il numero di valori =1 è r

1

+…..+r

1

=r

1

(v-1).

Per il principio del contare per righe e per colonne si ha l’eguaglianza:

r

1

(v-1) = r(k-1)

da cui r = r

1

(v-1)/(k-1) (cioè la tesi).

Dal Teorema precedente segue che se esiste un 2-disegno di parametri (v,k,r

1

), dovendo essere il numero r = r

1

(v-1)/(k-1) intero, è verificata certamente la condizione:

**(*) (k-1) è divisore di r**

1

(v-1)

Ricordando poi le condizioni per l’esistenza di un disegno di parametri (v,k,r) si ottiene (sempre dal Teorema precedente) che, se esiste un 2-disegno di parametri (v,k,r

1

), sono verificate le 2 condizioni:

() k è divisore del prodotto r**

1

v(v-1)/(k-1) (perché k è divisore del prodotto vr) (*) x = r**

1

v(v-1)/k(k-1)  _



 



 k

v (perché x=vr/k  _



 



 k v )

ed inoltre x = r

1

v(v-1)/k(k-1) rappresenta il numero dei blocchi del 2-disegno.

Nell’esempio precedente di un 2-disegno di parametri (8,4,3), si può notare che il numero x di blocchi (cioè dei tornei) è 14 proprio perché in questo caso 14 = r

1

v(v-1)/k(k-1) come si calcola facilmente.

Dunque se fissiamo 3 numeri naturali (v,k,r

1

) e almeno una delle condizioni (), (), () non è verificata, non è possibile costruire il un 2-disegno di parametri (v,k,r

1

).

**Purtroppo (al contrario di quanto avviene per i disegni) le condizioni (), (), () non sono necessarie e sufficienti per l’esistenza di un 2-disegno di parametri (v,k,r**

1

) : esistono esempi di terne di numeri naturali (v,k,r

1

) che soddisfano le 3 condizioni, ma tali che non esiste un 2-disegno di parametri (v,k,r

1

).

Allo stato attuale delle ricerche non sono state ancora trovate condizioni necessarie e sufficienti per l’esistenza dei 2-disegni.

Il problema del postino cinese.

Sia data una città (o un quartiere di una città) con varie strade lungo le quali sorgono alcuni edifici.

La situazione può essere rappresentata da un grafo non orientato in cui le strade sono gli archi e i vertici sono gli incroci delle strade stesse.

Un postino, partendo dall’ufficio postale (che è uno degli edifici), vuole distribuire la posta a tutti gli edifici, e, per essere certo di ciò, vuole percorrere tutte le strade della città (una strada può anche essere percorsa più di una volta) e tornare alla fine all’edificio di partenza, ma percorrendo il minimo numero di strade possibile: esiste un algoritmo che realizzi tale progetto ?

In termini di teoria dei grafi è necessario ovviamente che il grafo sia connesso (altrimenti il progetto non sarebbe realizzabile, perché vi sarebbero strade non raggiungibili): quindi il problema è di implementare un algoritmo che, dato un grafo non orientato connesso, costruisca un cammino ciclico di lunghezza minima fra i cammini che percorrono tutti gli archi del grafo.

Notiamo che nel problema non si pretende che il cammino sia anche Euleriano, ossia che percorra

tutti gli archi del grafo ognuno una sola volta (sappiamo, per il teorema di Eulero, che un tale

cammino non sempre esiste).

(3)

La soluzione del problema è stata trovata dal cinese Kwan (1962): il problema è quindi noto come il

“problema del postino cinese”.

Illustreremo i vari passi dell’algoritmo di Kwan,, anche se ometteremo, per semplicità, la dimostrazione che tale algoritmo in effetti produce un cammino ciclico di lunghezza minima (fra quelli che percorrono tutti gli archi del grafo).

Se tutti i vertici del grafo hanno grado pari, per il Teorema di Eulero (essendo il grafo connesso) esiste nel grafo un cammino ciclico Euleriano, che percorre tutti gli archi del grafo ognuno 1 sola volta, ed ovviamente questo è il cammino di lunghezza minima cercato.