Lezione del giorno 17 maggio 2011

Lezione del giorno 17 maggio 2011

Abbiamo parlato nella lezione precedente del problema del postino cinese, che, tradotto i termini di teoria dei grafi, richiede di costruire, in un grafo non orientato connesso, un cammino ciclico di lunghezza minima che percorra tutti gli archi del grafo (eventualmente percorrendo qualche arco più di una volta).

Un algoritmo per costruire questo cammino è stato elaborato da Kwan, nel modo che illustreremo.

Abbiamo già notato che, 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 (e si può costruire con l’algoritmo illustrato nella dimostrazione di Eulero).

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 soli 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 di lunghezza minima tra quelli che collegano i vertici u,v:

v

=u v

v

…... v

v

=v (*) a

a

a

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

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

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

L’algoritmo precedente per la costruzione (in un grafo connesso non orientato) di un cammino ciclico di lunghezza minima che percorra tutti gli archi del grafo, si può estendere facilmente al caso di un numero >2 di vertici di grado dispari (ricordiamo che tale numero in ogni caso è un numero pari).

I passi dell’algoritmo sono allora i seguenti:

- si costruiscono tutti le possibili partizioni dei vertici di grado dispari presi a 2 a 2

- fissata una di tali partizioni, si calcola, per ogni coppia di vertici nella partizione, si calcola il cammino di lunghezza minima che collega la coppia di vertici, e poi si sommano tutte le lunghezze ottenute al variare delle coppie nella partizione

- al variare delle partizioni, si sceglie una partizione in cui la somma precedente è minima

- nei cammini di lunghezza minima fra coppie di vertici coinvolti in tale partizione, si costruiscono archi “gemelli” di quelli originali e si procede come nel caso in cui vi sono solo 2 vertici di grado dispari

Anche in questo caso si può dimostrare che la lunghezza del cammino costruito con tale algoritmo è minima fra i cammini che percorrono tutti gli archi del grafo.

Esempio: consideriamo il caso del grafo dei ponti di Konisberg

a 6 1 2

b

7 d

3 4

c 5

In tale grafo vi sono 4 vertici, tutti di grado dispari.

Le possibili partizioni di tali vertici a 2 a 2 sono 3:

{a,b}, {c,d}

{a,c}, {b,d}

{a,d}, {b,c}

Nella prima partizione:

{a,b}, {c,d}

un cammino di lunghezza minima fra i vertici a,b è l’arco 1 mentre un cammino di lunghezza minima fra i vertici c,d è l’arco 5; quindi la somma delle lunghezze di tali cammini è 2.

Nella seconda partizione {a,c}, {b,d}

un cammino di lunghezza minima fra i vertici a,c è formato dagli archi 1,3 mentre un cammino di lunghezza minima fra i vertici b,d è l’arco 7; quindi la somma delle lunghezze di tali cammini è 3.

Nella terza partizione

{a,d}, {b,c}

un cammino di lunghezza minima fra i vertici a,d è l’arco 6 mentre un cammino di lunghezza minima fra i vertici b,c è l’arco 3; quindi la somma delle lunghezze di tali cammini è 2.

Una partizione con somma minima è per esempio la prima (o anche la terza, a scelta): gli archi coinvolti nei cammini di lunghezza minima trovati nella prima partizione sono gli archi 1,5 e dunque creiamo gli archi “gemelli” 1’, 5’.

a 6 1’ 1 2

b

7 d

3 4

c 5 5’

In tale nuovo grafo tutti i vertici hanno grado pari, dunque è possibile costruire un cammino ciclico Euleriano, per esempio quello che percorre di seguito i seguenti archi (con inizio e fine nel vertice a):

1, 3, 4, 1’, 2, 7, 5, 5’, 6

Sostituendo gli archi gemelli 1’, 5’ con gli originali 1,5 si ottiene nel grafo dei ponti il cammino ciclico:

1, 3, 4, 1, 2, 7, 5, 5, 6

che percorre tutti gli archi del grafo (passando 2 volte per gli archi 1,5), ed è di lunghezza minima.

Nei casi concreti il “problema del postino cinese” si applica per ottimizzare in un quartiere problemi di distribuzione della posta, di raccolta dei rifiuti etc., cercando di trovare il cammino ciclico più breve per effettuare la procedura. Ovviamente nella situazione teorica esaminata sopra ogni arco percorso ha “peso” 1 nel calcolare la lunghezza del cammino. Nella realtà le strade che collegano gli edifici avranno lunghezze differenti, quindi “pesi” differenti.

Si può però applicare l’algoritmo precedente anche ad un grafo non orientato “pesato”: è un grafo in cui ad ogni arco è assegnato un numero reale >0, detto appunto peso dell’arco. In tale tipo di grafo la lunghezza di un cammino è uguale non al numero degli archi percorsi nel cammino ma alla somma dei pesi degli archi percorsi nel cammino.

Come detto sopra, l’algoritmo precedente continua ad essere valido, anche per i grafi pesati.

Esempio: si consideri il seguente grafo connesso non orientato pesato con 9 vertici

{a,b,c,d,e,f,g,h,i} e 12 archi numerati da 1 a 12 (accanto all’etichetta di ogni arco è indicato fra

parentesi il peso dell’arco stesso):

a b c

1 (6) 2 (7)

3 (2) 4 (3) 5 (3) 6 (6) 7 (4)

d e f

8 (4) 9 (6) 10 (4)

g 11 (8) h 12 (7) i Tutti i vertici hanno grado pari, tranne i 4 vertici b,d,f,h.

Le possibili partizioni di tali vertici a 2 a 2 sono 3:

{b,d}, {f,h}

{b,f}, {d,h}

{b,h}, {d,f}

Nella prim partizione {b,d}, {f,h}

un cammino di lunghezza minima fra i vertici b,d (formato dagli archi 1,3) ha lunghezza 2+6=8 mentre un cammino di lunghezza minima fra i vertici f,h (formato dagli archi 7,9) ha lunghezza 4+6=10; quindi la somma delle lunghezze di tali cammini è 8+10=18.

Nella seconda partizione {b,f}, {d,h}

un cammino di lunghezza minima fra i vertici b,f (formato dagli archi 4,7) ha lunghezza 3+4=7 mentre un cammino di lunghezza minima fra i vertici d,h (formato dagli archi 6,9) ha lunghezza 6+6=12; quindi la somma delle lunghezze di tali cammini è 7+12=19.

Nella terza partizione {b,h}, {d,f}

un cammino di lunghezza minima fra i vertici b,h (formato dagli archi 4,9) ha lunghezza 3+6=9 mentre un cammino di lunghezza minima fra i vertici d,f (formato dagli archi 6,7) ha lunghezza 6+4=10; quindi la somma delle lunghezze di tali cammini è 9+10=19.

Una partizione con somma minima è la prima: gli archi dei cammini coinvolti in tale partizione

sono gli archi 1,3,7,9 e dunque creiamo gli archi “gemelli” 1’, 3’,7’,9’:

1’(6)

a b c 1 (6) 2 (7)

3’(2) 3 (2) 4 (3) 5 (3) 6 (6) 7 (4)

d e f 7’(4)

8 (4) 9 (6) 10 (4) 9’(6)

g 11 (8) h 12 (7) i

In tale nuovo grafo tutti i vertici hanno grado pari, dunque è possibile costruire un cammino ciclico Euleriano, per esempio quello che percorre di seguito i seguenti archi (con inizio e fine nel vertice a):

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

Sostituendo gli archi gemelli 1’,3’,7’,9’con gli originali 1,3,7,9 si ottiene nel grafo il cammino ciclico:

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

che percorre tutti gli archi del grafo (passando 2 volte per gli archi 1,3,7,9), ed è di lunghezza

minima: la lunghezza in particolare è 6+7+3+4+3+6+2+4+8+7+4+4+6+6+6+2=78.