Matematica Discreta Lezione del giorno 20 marzo 2009 Alcuni problemi risolubili con la teoria dei grafi. 1) Problemi delle “strette di mano” (handshaking problems).

Matematica Discreta

Lezione del giorno 20 marzo 2009

Alcuni problemi risolubili con la teoria dei grafi.

1) Problemi delle “strette di mano” (handshaking problems).

Consideriamo una riunione di n persone, alcune delle quali si stringono la mano fa loro.

Possiamo rappresentare la situazione in termini di teoria dei grafi, costruendo un grafo semplice non orientato G in cui i vertici sono le n persone, e in cui 2 vertici distinti x,y sono adiacenti (quindi collegati da un arco) se x,y si sono stretti la mano.

Con questa situazione iniziale, vi sono nella letteratura diversi problemi: ne esporremo uno come esempio.

Problema: se il numero n di persone è 6, dimostrare che è verificata sempre almeno una delle seguenti condizioni

- esistono 3 persone che si sono strette reciprocamente la mano

- esistono 3 persone tali che nessuna delle 3 ha stretto la mano alle altre 2

Cerchiamo prima di tradurre il problema in un problema relativo al grafo G associato alla riunione delle n persone, ricorrendo al concetto di grafo duale.

Dato un qualunque grafo semplice non orientato G, si chiama grafo duale di G il grafo semplice non orientato G’ che ha gli stessi vertici di G, ma nel quale due vertici distinti x,y sono adiacenti (cioè collegati da un arco) se e solo se x,y non sono adiacenti nel grafo G.

Esempio: dato il seguente grafo semplice non orientato G a b

c d il suo grafo duale G’ è il seguente

a b

c d

Nel grafo duale del grafo associato alla riunione di n persone, due vertici distinti x,y saranno adiacenti se x,y non si sono stretti la mano.

Dunque il problema precedente, in termini di teoria dei grafi, diventa:

dato un qualunque grafo semplice orientato G con n vertici, in cui n6, dimostrare che è verificata sempre almeno una delle seguenti condizioni

- esistono 3 vertici reciprocamente adiacenti nel grafo G - esistono 3 vertici reciprocamente adiacenti nel grafo G’

Poiché 3 vertici reciprocamente adiacenti in un grafo formano un cammino ciclico di lunghezza 3, detto anche triangolo, il problema diventa:

dato un qualunque grafo semplice orientato G con n vertici, in cui n6, dimostrare che esiste almeno un triangolo in G o nel grafo duale G’.

Notiamo che se il numero n di vertici n è <6, l’affermazione precedente può non essere vera.

Per esempio nel seguente grafo G con 5 vertici:

a b

e c d

non esiste un triangolo, e lo stesso avviene nel grafo duale G’:

a b

e c d

Dimostriamo allora la proprietà enunciata sopra: in un qualunque grafo semplice orientato G con n vertici, in cui n6, esiste sempre almeno un triangolo in G o nel grafo duale G’.

Dimostrazione:

Fissiamo a piacere un vertice v in G. Distinguiamo 2 casi:

- vi sono almeno 3 vertici v

,v

,v

adiacenti a v nel grafo G v v

v

v

In questo caso, se almeno due dei tre vertici v

,v

,v

sono adiacenti fra loro, in G esiste un triangolo (con terzo vertice v) e si ha la tesi; se invece nessuno dei tre vertici v

,v

,v

è adiacente ad uno degli altri, allora v

,v

,v

formano un triangolo nel grafo duale G’, e di nuovo si ha la tesi;

- non vi sono 3 vertici v

,v

,v

adiacenti a v nel grafo G; in questo caso al più due vertici sono adiacenti a v nel grafo G e dunque (essendo il numero n di vertici 6) vi sono certamente almeno altri 3 vertici v

,v

,v

non adiacenti a v nel grafo G, quindi v

,v

,v

sono adiacenti a v nel grafo duale G’; allora si può ragionare come nel primo caso (scambiando nel ragionamento i ruoli del grafo G e del grafo G’) per concludere che esiste un triangolo nel grafo G’ oppure nel grafo G, ed ottenere di nuovo la tesi.

2) Il problema del postino cinese (studiato dal matematico cinese Kwan nel 1962). Sia dato un quartiere con strade che si intersecano in alcuni incroci. La situazione può essere rappresentata da un grafo non orientato in cui gli incroci sono i vertici, e le strade che le collegano sono gli archi.

Supponiamo anche che, comunque scelti 2 incroci, esista sempre almeno un cammino che le collega: il grafo è dunque connesso.

Un postino, partendo da incrocio, vuole distribuire la posta a tutte le abitazioni del quartiere, e, per essere certo di ciò, vuole percorrere tutte le strade del quartiere (una strada può anche essere percorsa più di una volta) e tornare alla fine all’incrocio di partenza, ma percorrendo il minimo numero di strade possibile.

In termini di teoria dei grafi, si vuole trovare (in un grafo non orientato) un cammino ciclico di lunghezza minima che percorra tutti gli archi del grafo (eventualmente percorrendo qualche arco più di una volta): notare che non si pretende che il cammino sia Euleriano, ossia che percorra tutti gli archi del grafo ognuno una sola volta.

Prima di esporre l’algoritmo di Kwan che risolve il problema, dimostriamo un risultato formale, dal

quale segue che in un cammino come quello richiesto non è necessario ripercorrere le stesse strade

un numero “eccessivo” di volte.

Infatti Kwan dimostrò che in un cammino ciclico di lunghezza minima (fra quelli che percorrono tutti gli archi di un grafo non orientato) nessun arco viene percorso più di 2 volte.

Dimostriamo tale affermazione.

Per assurdo sia dato un cammino ciclico di lunghezza minima (fra quelli che percorrono tutti gli archi del grafo) e che percorra l’arco di estremi u,v almeno 3 volte.

Supponiamo per esempio che l’arco di estremi u,v sia percorso durante il cammino 3 volte tutte nella stessa direzione da u verso v.

Dunque, schematizzando tale cammino ciclico, si ha:

si percorre l’arco da u verso v; si percorre un settore A del cammino che parte da v ed arriva ad u; si percorre per la seconda volta l’arco da u verso v; si percorre un altro settore B del cammino che parte da v ed arriva ad u; si percorre per la terza volta l’arco da u verso v; si percorre infine un altro settore C del cammino che parte da v ed arriva ad u, chiudendo il cammino ciclico.

Ora costruiamo il seguente cammino:

si percorre l’arco da u verso v; si percorre il settore A (del cammino precedente) che parte da v ed arriva ad u; si percorre il settore B (del cammino precedente, ma in senso inverso) che parte da u ed arriva a v; si percorre il settore C (del cammino precedente) che parte da v ed arriva ad u, chiudendo il ciclo.

Il cammino così costruito contiene esattamente gli stessi archi del precedente, ma con la doppia cancellazione dell’arco da u verso v: dunque (come il precedente) è certamente un cammino ciclico che percorre tutti gli archi del grafo, ma ha lunghezza inferiore di 2 unità, e ciò è una contraddizione, perché avevamo supposto che il cammino originario ciclico fosse di lunghezza minima (fra quelli che percorrono tutti gli archi del grafo).

Per completare la dimostrazione si dovrebbero esaminare gli altri casi: quello per esempio in cui l’arco di estremi u,v sia percorso durante il cammino 2 volte nella stessa direzione da u verso v ed 1 volta nella direzione contraria da v verso u (etc……). Ma in ognuno di tali casi si ragiona in modo simile, “incollando” opportunamente i 3 settori A,B,C del cammino per ottenere un cammino di lunghezza minore di quella minima (contraddizione).

Dunque abbiamo dimostrato che, se riusciamo a costruire un cammino ciclico di lunghezza minima (fra quelli che percorrono tutti gli archi del grafo non orientato) nessun arco viene percorso più di 2 volte, ossia se il postino riesce a trovare la strada più breve, è certo di non passare più di 2 volte per ognuna delle strade del quartiere.

Ma come costruire questo cammino di lunghezza minima ?

Illustreremo l’algoritmo trovato da Kwan, anche se ometteremo 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.

Supponiamo invece che esistano vertici di grado dispari: per un Teorema precedente, il numero di tali vertici di grado dispari è pari (2,4,6,8…..).

Esaminiamo prima il caso più semplice: siano 2 i vertici di grado dispari del grafo.

In questo caso, se u,v sono tali 2 vertici di grado dispari, l’algoritmo di Kwan è il seguente:

1) si trova un cammino di lunghezza minima che collega i vertici u,v

2) per ogni arco a di tale cammino, si costruisce un arco “gemello” a’ (dunque si costruisce un nuovo grafo che ha più archi di quello iniziale)

3) si nota che nel nuovo grafo tutti i vertici hanno grado pari: infatti i vertici u,v hanno aumentato di

1 unità il loro grado, dunque il loro grado diventa pari, mentre i vertici intermedi del cammino di

lunghezza minima che collega u,v hanno aumentato di 2 unità il loro grado, quindi il loro grado

resta pari. Per il Teorema di Eulero esiste nel nuovo grafo un cammino ciclico Euleriano che

percorre tutti gli archi (del nuovo grafo) ognuno 1 sola volta

4) si costruisce tale cammino ciclico Euleriano nel nuovo grafo, e poi in tale cammino si sostituisce ogni arco “gemello” a’ con l’arco originale a, ottenendo alla fine un cammino ciclico (nel grafo iniziale) che percorre tutti gli archi del grafo (alcuni più volte): Kwan dimostrò che tale cammino è di lunghezza minima.

Esempio: si consideri il seguente grafo (connesso) non orientato con 6 vertici (a,b,c,d,e,f) e 11 archi (numerati da 1 a 11):

1 2

a b c 3 4 5 6 7 8 9

d e f

10

11

Tutti i vertici hanno grado pari, tranne i 2 vertici c,d.

Seguendo l’algoritmo di Kwan, individuiamo un cammino di lunghezza minima che unisce tali 2 vertici di grado dispari, per esempio il cammino formato dagli archi 1 e 5. Creiamo per ognuno di tali archi un arco gemello 1’, 5’. Otteniamo un nuovo grafo (con 2 archi in più) in cui tutti i vertici hanno grado pari, dunque esiste nel nuovo grafo un cammino ciclico Euleriano, per esempio quello (che ha inizio e fine nel vertice a) formato in successione dai seguenti archi:

1,4,2,3,6,8,5,1’,7,10,9,11,5’

Sostituendo in tale cammino l’arco 1’ con 1 e l’arco 5’ con 5 si ottiene nel grafo iniziale un cammino ciclico di lunghezza 13 che percorre tutti gli 11 archi (ripetendo 2 volte gli archi 1 e 5):

1,4,2,3,6,8,5,1,7,10,9,11,5

e tale cammino (secondo quanto dimostrato da Kwan) é di lunghezza minima fra quelli ciclici che percorrono tutti gli 11 archi del grafo.