Matematica Discreta Lezione del giorno 15 maggio 2012

Matematica Discreta

Lezione del giorno 15 maggio 2012

Nella lezione precedente abbiamo illustrato un algoritmo per la costruzione (in un grafo connesso non orientato) di un cammino ciclico di lunghezza minima che percorra tutti gli archi del grafo, almeno nel caso in cui siano solo 2 i vertici di grado dispari.

Tale algoritmo si può estendere facilmente al caso più generale in cui il numero dei vertici di grado dispari sia >2 (ricordiamo che, per un risultato precedente, tale numero in ogni caso è un multiplo di 2).

I passi dell’algoritmo sono allora i seguenti:

- se V

è l’insieme dei vertici di grado dispari, si costruiscono tutti le possibili partizioni di V

in sottoinsiemi di cardinalità 2 (ciò è possibile perché appunto la cardinalità di V

è multipla di 2) - fissata una di tali partizioni, si calcola, per ogni coppia di vertici in un sottoinsieme della partizione, il cammino di lunghezza minima che collega la coppia di vertici, e poi si sommano tutte le lunghezze ottenute al variare delle coppie

- al variare delle partizioni, si sceglie una partizione in cui la somma calcolata nel passo 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 visto nella lezione precedente 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 in sottoinsiemi di cardinalità 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.

Grafi pesati

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 che percorra tutte le strade del quartiere. Ovviamente nella situazione teorica esaminata sopra ogni arco percorso ha “peso” 1 nel calcolare la lunghezza del cammino: nella realtà le strade del quartiere 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 si definisce lunghezza di un cammino non il numero degli archi percorsi nel cammino ma la 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 in sottoinsiemi di cardinalità sono 3:

{b,d}, {f,h}

{b,f}, {d,h}

{b,h}, {d,f}

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

un cammino di lunghezza minima fra i vertici b,d è formato dagli archi 1,3 ed ha lunghezza 2+6=8 mentre un cammino di lunghezza minima fra i vertici f,h è formato dagli archi 7,9 ed 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 ed ha lunghezza 3+4=7 mentre un cammino di lunghezza minima fra i vertici d,h è formato dagli archi 6,9 ed 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 ed 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 di lunghezza minima 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.