Matematica Discreta
Lezione del giorno 2 aprile 2012
Il teorema di Kuratowski sui grafi planari.
Vedremo che i grafi non planari K3,3 e K5 sono in qualche modo “essenziali” per verificare la non planarità di un grafo, come dimostrato dal matematico Kuratowski.
Introduciamo prima una definizione.
Dati i grafi non orientati G1 e G2, diremo che il grafo G1 è una espansione del grafo G2, se G1 si ottiene da G2 ripetendo un numero finito di volte la seguente operazione: si fissa in G1 un arco a che ha come estremi i vertici v,w, si inserisce un nuovo vertice z all’interno dell’arco a, sostituendo quindi l’arco a con 2 nuovi archi a1 (di estremi v,z) ed a2 (di estremi z,w):
v a w v a1 z a2 w (prima dell’operazione) (dopo l’operazione)
In pratica in una espansione vengono aggiunti nuovi vertici tutti di grado 2, ognuno all’interno di un arco del grafo originario.
Esempio: il seguente grafo G1
A B C G1 z y a b c è una espansione del grafo dei servizi G2=K3,3:
A B C
G2 = K3,3
a b c
(sono stati inseriti 2 nuovi vertici z,y all’interno di 2 archi di K3,3).
Siamo ora in grado di enunciare il risultato seguente (di cui omettiamo la dimostrazione):
Teorema di Kuratowski. Un grafo non orientato è non planare se e solo se contiene una espansione del grafo K3,3 o del grafo K5 .
Esempio: il seguente grafo
1
2
è non planare: infatti (eliminando gli archi 1,2) si nota che esso contiene una espansione del grafo dei servizi K3,3 (si tratta dell’espansione di K3,3 considerata nell’esempio precedente).
Da tale Teorema di Kuratowski segue un algoritmo per verificare se un dato grafo non orientato è o non è planare:
- si eliminano tutti i vertici di grado 2, fondendo in un solo arco le coppie di archi che li hanno come estremi (eliminiamo quindi i vertici che potrebbero essere stati inseriti per ottenere espansioni) - all’interno del nuovo grafo così ottenuto si cerca l’esistenza del grafo K5 (cioè 5 vertici tutti adiacenti reciprocamente fra loro) o del grafo K3,3 (cioè 6 vertici dei quali 3 sono adiacenti agli altri 3)
- se tale ricerca ha successo, il grafo è non planare; in caso contrario è planare.
Problemi delle “strette di mano” (handshake problems).
Sono problemi risolubili con la teoria dei grafi.
In tutti questi problemi la situazione iniziale è la seguente: consideriamo una riunione di n persone, alcune delle quali si stringono la mano fa loro.
Possiamo rappresentare tale situazione in termini di teoria dei grafi, costruendo un grafo semplice non orientato G in cui i vertici sono le n persone, e in cui 2 vertici distinti x,y sono adiacenti (quindi collegati da un arco) se x,y si sono stretti la mano.
Con questa situazione iniziale, vi sono nella letteratura diversi problemi (detti appunto handshake problems).
Un esempio di handshake problem molto semplice è il seguente: se nel gruppo di n persone ognuno stringe la mano a tutti gli altri, quante strette di mano in totale vengono effettuate ?
Soluzione: costruendo come detto sopra un grafo semplice non orientato che rappresenti la situazione, ogni stretta di mano corrisponde ad un arco, dunque il problema chiede di contare il numero x di archi. Per un risultato sui grafi già dimostrato, la somma dei gradi dei vertici è uguale al doppio del numero degli archi, ma ogni vertice ha grado (n-1) (perché ogni persona stringe la mano a tutti gli altri) dunque la somma dei gradi dei vertici è (n-1)+(n-1)+….(n-1) (con n addendi) ossia è n(n-1) e da n(n-1)=2x segue la risposta: il numero x di strette di mano è x=n(n-1)/2.
Vi sono esempi di handshake problem più complessi, come quello che ora illustreremo.
Problema: se il numero n di persone è 6, dimostrare che è verificata sempre almeno una delle seguenti condizioni
- esistono 3 persone che si sono strette reciprocamente la mano
- esistono 3 persone tali che nessuna delle 3 ha stretto la mano alle altre 2
Cerchiamo prima di tradurre il problema in un problema relativo al grafo G associato alla riunione delle n persone, ricorrendo al concetto di “grafo duale”.
Dato un qualunque grafo semplice non orientato G, si chiama grafo duale di G il grafo semplice non orientato G’ che ha gli stessi vertici di G, ma nel quale due vertici distinti x,y sono adiacenti (cioè collegati da un arco) se e solo se x,y non sono adiacenti nel grafo G.
Esempio: dato il seguente grafo semplice non orientato G a b
c d il suo grafo duale G’ è il seguente
a b
c d
Nel grafo duale del grafo associato alla riunione di n persone, due vertici distinti x,y saranno adiacenti se e solo se x,y non si sono stretti la mano.
Notiamo che se un grafo non orientato semplice G ha n vertici, e se un vertice v in G ha grado k allora lo stesso vertice v nel grafo duale G’ ha grado n-1-k: infatti se v è adiacente ad un numero k di vertici nel grafo G (questi k vertici sono scelti fra gli (n-1) vertici diversi da v), allora v nel grafo duale G’ è adiacente ai restanti vertici diversi da v, che sono appunto in numero di n-1-k.
Dunque il problema precedente, in termini di teoria dei grafi, diventa:
dato un qualunque grafo semplice orientato G con n vertici, in cui n 6, dimostrare che è verificata sempre almeno una delle seguenti condizioni
- esistono 3 vertici reciprocamente adiacenti nel grafo G - esistono 3 vertici reciprocamente adiacenti nel grafo G’
Poiché 3 vertici reciprocamente adiacenti in un grafo formano un ciclo di lunghezza 3, il problema diventa:
dato un qualunque grafo semplice orientato G con n vertici, in cui n 6, dimostrare che esiste almeno un ciclo di lunghezza 3 in G o nel grafo duale G’.
Dimostrazione:
Fissiamo a piacere un vertice v in G. Distinguiamo 2 casi (e in ambedue i casi dimostriamo la tesi):
I° caso: il grado k di v è 3; in questo caso vi sono almeno 3 vertici v1,v2,v3 adiacenti al vertice v nel grafo G
v v1
v2 (grafo G) v3
In questo caso, se almeno due dei tre vertici v1,v2,v3 sono adiacenti fra loro, in G esiste un ciclo di lunghezza 3 (con terzo vertice v) e si ha la tesi; se invece nessuno dei tre vertici v1,v2,v3 è adiacente ad uno degli altri, allora v1,v2,v3 sono tutti adiacenti fra loro nel grafo duale G’ quindi essi formano un ciclo di lunghezza 3 in G’, e di nuovo si ha la tesi;
II° caso: il grado k di v è <3 ; in questo caso il grado di v nel grafo duale G’, come osservato sopra, è n-1-k e poiché n 6 tale grado è 6-1-k=5-k 3 , dunque v nel grafo duale G’ ha grado 3; in questo caso vi sono almeno 3 vertici v1,v2,v3 adiacenti al vertice v nel grafo duale G’
v v1
v2 (grafo G’) v3
e si può allora effettuare lo stesso ragionamento fatto primo caso (sostituendo nel ragionamento il grafo G con il grafo G’) per concludere che esiste un ciclo di lunghezza 3 nel grafo G’ oppure nel grafo duale di G’ (che è G), ed ottenere di nuovo la tesi.
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….).
Nella prossima lezione vedremo come formalizzare questi problemi nella teoria degli insiemi.
