Matematica Discreta Lezione del giorno 13 gennaio 2010

Matematica Discreta

Lezione del giorno 13 gennaio 2010 Abbiamo dimostrato il seguente teorema:

In un grafo completo (cioè un grafo in cui, comunque dati due vertici distinti v,w, esiste sempre almeno un arco di estremi v,w) esiste un cammino Hamiltoniano (cioè un cammino che tocca tutti i vertici del grafo, ognuno una sola volta).

Vediamo una interessante applicazione di tale teorema.

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.

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

A

A

A

A

…………..

(dove A

,A

,….,A

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

Da questo ragionamento si deduce che in pratica è sempre possibile disporre le squadre del torneo in successione in un opportuno ordine:

A

, A

, …….., A

in modo che:

la prima squadra A

abbia sconfitto almeno una volta la seconda squadra A

; la seconda squadra A

abbia sconfitto almeno una volta la terza squadra A

; 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

, A

, …….., A

).

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

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

La successione di squadre C,D,A,E,B è costruita in modo che ognuna abbia sconfitto quella che la

segue nella successione (notare che B, ultima nella successione) non è l’ultima nella classifica

finale (l’ultima in classifica è E).