Matematica Discreta Lezione del giorno 24 aprile 2012 Il

Matematica Discreta

Lezione del giorno 24 aprile 2012 Il problema del postino cinese.

Supponiamo che un quartiere di una città sia percorso da varie strade a doppio senso di percorrenza.

Un postino, partendo da uno degli incroci vuole distribuire la posta nel quartiere e (per essere certo di non “saltare” nessuno dei destinatari della posta) vuole percorrere tutte le strade del quartiere (notare che una strada può anche essere percorsa più di una volta) e tornare alla fine al punto di partenza, ma percorrendo il minimo numero di strade possibile: esiste un algoritmo che realizzi tale progetto ?

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.

In termini di teoria dei grafi, affinché il problema sopra esposto abbia soluzione, è necessario ovviamente che il grafo sia connesso (altrimenti vi sarebbero strade non raggiungibili dal postino):

si tratta quindi di implementare un algoritmo che, dato un grafo non orientato connesso, costruisca nel grafo 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).

La soluzione del problema è stata trovata dal cinese Kwan (1962): il problema è per questo 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).

Prima di esporre l’algoritmo di Kwan che risolve il problema, dimostriamo un interessante 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 connesso) 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 a 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 a da u verso v; si percorre un cammino A (formato da diversi archi) che parte da v ed arriva ad u; si percorre per la seconda volta l’arco a da u verso v; si percorre un altro cammino B che parte da v ed arriva ad u; si percorre per la terza volta l’arco a da u verso v; si percorre infine un altro cammino C che parte da v ed arriva ad u, chiudendo il cammino ciclico.

Gli archi dei 3 cammini “parziali” A,B,C, e l’arco di estremi u,v esauriscono per ipotesi tutti gli archi del grafo.

Ora costruiamo il seguente cammino ciclico:

si percorre l’arco a da u verso v; si percorre il cammino A che parte da v ed arriva ad u; si percorre il cammino B (ma in senso inverso rispetto al cammino precedente) che parte da u ed arriva a v; si percorre il cammino C 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 a di estremi u,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 a 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 cammini A,B,C e l’arco a 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.

Illustriamo ora l’algoritmo di Kwan che, dato un grafo non orientato connesso, costruisce un cammino ciclico di lunghezza minima fra quelli che percorrono tutti gli archi del grafo.

Esaminiamo un primo caso molto semplice: 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 (l’algoritmo per costruirlo è indicato nella dimostrazione del Teorema di Eulero).

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

Esaminiamo allora un secondo caso: quello nel quale siano solo 2 i vertici di grado dispari del grafo, e siano essi i vertici u,v .

In questo caso l’algoritmo per costruire il cammino richiesto è il seguente:

1) si trova un cammino A di lunghezza minima tra quelli che collegano i vertici u,v:

v

=u v

v

…... v

v

=v a

a

a

A

(per costruire A esistono degli opportuni algoritmi, come quello dovuto al matematico Dijkstra).

Osservazione: nel cammino (*) nessuno dei vertici intermedi v

, v

, ….., v

coincide con uno dei vertici estremi u, v, perché se per assurdo per esempio fosse v

=v si potrebbe elidere il settore del cammino compreso fra il vertice v

=v ed il vertice v

=v, ed ottenere un cammino che collega i vertici u,v di lunghezza minore di quella minima, contraddizione;

2) per ogni arco a

del cammino (*), si costruisce nel grafo un arco “gemello” a

’ (dunque si costruisce un nuovo grafo che ha più archi di quello iniziale)

Osservazione: il nuovo grafo è connesso come quello iniziale, perché i vertici sono rimasti gli stessi e sono stati aggiunti solo nuovi archi, quindi rimane valida l’esistenza, per ogni coppia di vertici, di un cammino che li collega;

3) tutti i vertici del nuovo grafo hanno grado pari: infatti (essendo diversi da u,v tutti i vertici

intermedi del cammino costruito nel passo 1)) i vertici u,v (gli unici di grado dispari) hanno

aumentato di 1 unità il loro grado, dunque il loro grado diventa pari, mentre i vertici intermedi di tale cammino hanno aumentato di un multiplo di 2 il loro grado (perché ogni volta che li incontriamo abbiamo aggiunto un nuovo arco di ingresso ed un nuovo arco di uscita), quindi il loro grado resta pari, come nel grafo iniziale;

4) 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; si costruisce tale cammino ciclico Euleriano nel nuovo grafo (con l’algoritmo illustrato nella dimostrazione di Eulero), e 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 (gli archi a

vengono percorsi 2 volte): è possibile dimostrare (ma ometteremo tale dimostrazione) che tale cammino è di lunghezza minima fra i cammini ciclici che percorrono tutti gli archi del grafo.

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 che hanno grado 3 (dispari).

Seguendo l’algoritmo illustrato sopra, 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’:

1’

1 2

a b c 3 4 5’ 5 6 7 8 9

d e f

10

11

Come previsto dalla teoria, otteniamo un nuovo grafo (con 2 archi in più) connesso e in cui tutti i vertici hanno grado pari, dunque esiste nel nuovo grafo un cammino ciclico Euleriano (che si può costruire utilizzando l’algoritmo contenuto nella dimostrazione del Teorema di Eulero): un esempio di cammino ciclico Euleriano è quello 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

Tale cammino (secondo quanto ha dimostrato Kwan) sarà un cammino di lunghezza minima fra quelli ciclici che percorrono tutti gli 11 archi del grafo.