Matematica Discreta Lezione del 22 marzo 2010
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).
Ma come costruire questo cammino di lunghezza minima ?
Illustreremo l’algoritmo, 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).
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 è il seguente:
1) si trova un cammino di lunghezza minima che collega i vertici u,v: notiamo che tutti i vertici incontrati in tale cammino (inclusi u,v) sono distinti, perché se per assurdo per esempio un vertice fosse presente nel cammino almeno 2 volte, si potrebbe elidere il settore del cammino compreso fra 2 ripetizioni di tale vertice ed ottenere un cammino che collega i vertici u,v di lunghezza minore di quella minima, contraddizione;
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): si nota che il nuovo grafo è connesso come quello iniziale, perché i vertici sono rimasti gli stessi e sono stati aggiunti nuovi archi, quindi rimane valida l’esistenza, per ogni coppia di vertici, di un cammino che li collega;
3) si nota che nel nuovo grafo tutti i vertici hanno grado pari: infatti (essendo distinti tutti i vertici 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 2 unità il loro grado, 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, 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 (alcuni 2 volte): è possibile dimostrare (ma ometteremo tale dimostrazione) 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 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 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 i possibili “accoppiamenti” dei vertici di grado dispari presi a 2 a 2 (ognuno di tali accoppiamenti è in pratica una partizione dell’insieme dei vertici di grado dispari in sottoinsiemi ognuno contenente 2 vertici)
- fissato uno di tali accoppiamenti, si calcola, per ogni coppia di vertici nell’accoppiamento, la lunghezza del cammino di lunghezza minima che li collega, e poi si sommano tali lunghezze al variare di tutte le coppie nell’accoppiamento
- al variare degli accoppiamenti, se ne sceglie uno in cui la somma precedente è minima
- nei cammini di lunghezza minima fra coppie di vertici coinvolti in tale accoppiamento, 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.
I possibili accoppiamenti di tali vertici a 2 a 2 sono 3:
{a,b}, {c,d}
{a,c}, {b,d}
{a,d}, {b,c}
Nel primo accoppiamento:
{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.
Nel secondo accoppiamento{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.
Nel primo accoppiamento{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.
Un accoppiamento con somma minima è per esempio il primo: i cammini coinvolti in tale accoppiamento 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.
I possibili accoppiamenti di tali vertici a 2 a 2 sono 3:
{b,d}, {f,h}
{b,f}, {d,h}
{b,h}, {d,f}
Nel primo accoppiamento:{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.
Nel secondo accoppiamento: {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.
Nel terzo accoppiamento:{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.
Un accoppiamento con somma minima è per esempio il primo: gli archi dei cammini coinvolti in tale accoppiamento 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.
Teoria dei disegni.
E’ un teoria che ha origine storicamente dai test industriali di qualità.
Supponiamo che un industria produca un numero v di differenti varietà di uno stesso prodotto (v è un numero naturale) e voglia sottoporre tali varietà ad un test di qualità: vi saranno dei soggetti (detti testers) che effettueranno il test.
Una possibilità di effettuare il test è ovviamente quella in cui tutti i testers effettuano il test su tutte le varietà del prodotto, ma spesso per motivi organizzativi ciò non è possibile.
Dunque in generale ogni tester effettuerà il test solo su alcune delle varietà del prodotto.
In questo caso, però, affinché il test sia equilibrato e omogeneo nei risultati, è ovviamente opportuno richiedere che:
- ogni tester effettua il test sullo stesso numero k di varietà del prodotto fra le v disponibili (con k numero naturale uguale per tutti i testers);
- ognuna delle v varietà del prodotto sia sottoposta al test dallo stesso numero r di testers (con r numero naturale uguale per tutte le varietà)
Esempio: sia v=6, k=3, r=2 (in totale 6 varietà del prodotto, ogni tester sottopone 3 varietà al test ed ogni varietà viene sottoposta al test da 2 testers). È possibile, con questi dati, effettuare il test? E con quanti testers? Con i dati precedenti la risposta è positiva; infatti, se l’insieme delle 6 varietà è A=a,b,c,d,e,f si possono impiegare 4 testers per esempio secondo lo schema seguente:
1° tester: {a,b,c}, 2° tester: {b,c,d}, 3° tester: {d,e,f}, 4° tester: {e,f,a}
Possiamo notare che in effetti con questo schema ogni tester effettua il test su k=3 varietà ed ogni varietà è sottoposta al test da r=2 testers (per esempio la varietà a è sottoposta al test dal primo e quarto tester, la varietà b dal primo e secondo tester, etc….).
Se vogliamo formalizzare l’esempio precedente nel linguaggio della teoria degli insiemi, possiamo dire che si è partiti da un insieme con v=6 elementi (nel nostro caso A=a,b,c,d,e,f) e si sono costruiti dei sottoinsiemi di A (nel nostro caso{a,b,c},{b,c,d},{d,e,f}, {e,f,a}) ognuno dei quali ha la stessa cardinalità k=3, e tali che ogni elemento dell’insieme di partenza è contenuto esattamente in r=2 di tali sottoinsiemi.
Da ciò nasce in modo naturale la definizione del concetto formale di disegno.
Fissati i numeri naturali v,k,r (detti parametri) si chiama disegno di parametri (v,k,r) una struttura formata da:
- un insieme A di cardinalità v;
- alcuni sottoinsiemi non vuoti di A (detti blocchi del disegno), tutti della stessa cardinalità k e tali che ogni elemento di A appartenga esattamente ad r blocchi
Esempio: L’esempio precedente, dove A=a,b,c,d,e,f) e dove i sottoinsiemi di A sono {a,b,c}, {b,c,d},{d,e,f}, {e,f,a}, è un esempio di disegno di parametri (v=6,k=3,r=2).
