Matematica Discreta
Lezione del giorno 23 marzo 2009
L’algoritmo di Kwan 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 di vertici di grado dispari >2 (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 un insieme di insiemi disgiunti ognuno contenente 2 vertici di grado dispari)
- 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
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.
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 intero 1) e voglia sottoporre tali varietà ad un test di qualità: vi saranno delle persone (testers) che effettueranno i test.
Una possibilità di effettuare il test è ovviamente quella in cui tutti i testers effettuano il test su tutte le varietà, 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 testi lo stesso numero k di varietà fra le v disponibili (con k dunque uguale per tutti i testers);
- ognuna delle v varietà sia testata dallo stesso numero r di testers (con r dunque uguale per tutte le varietà)
Esempio: sia v=6, k=3, r=2 (in totale 6 varietà, ogni tester ne testa 3 ed ogni varietà viene testata 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 ogni tester effettua il test su k=3 varietà ed ogni varietà è testata da 2 testers (per esempio la varietà a è testata dal primo e quarto tester, la varietà b è testata 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.
Ciò porterà, come vedremo, alla definizione del concetto formale di disegno.
