Lezione del giorno 10 maggio 2011

Lezione del giorno 10 maggio 2011 Abbiamo dimostrato il seguente Teorema:

Teorema. Sia dato un grafo planare connesso e semplice. Siano poi v il numero di vertici, a il numero di archi. Allora, se v  3, si ha:

a  3v – 6

Come applicazione di tale Teorema si ha il seguente risultato:

il grafo completo semplice con 5 vertici K5 non è planare (ricordiamo che in tale grafo i vertici sono i 5 vertici di un pentagono e gli archi sono i 5 lati del pentagono e le sue 5 diagonali).

Infatti il grafo K5 è un grafo semplice e connesso, e se per assurdo fosse planare, per l’ultimo Teorema dimostrato si dovrebbe avere a  3v – 6 (dove a=numero degli archi=10, v=numero dei vertici=5), e ciò ovviamente non è vero.

D’altronde lo stesso Teorema non può aiutarci per dimostrare che il grafo dei servizi K3,3 non è planare (ricordiamo che in tale grafo vi sono 6 vertici dei quali 3 sono adiacenti agli altri 3): infatti il grafo K3,3 (connesso e semplice) soddisfa la diseguaglianza a  3v – 6, in quanto si ha a=9, v=6.

Dimostreremo quindi un altro Teorema sui grafi planari, la cui applicazione permetterà di dimostrare la non planarità del grafo K3,3 .

Teorema. Sia dato un grafo planare connesso e semplice e supponiamo che non esistano nel grafo cicli di lunghezza 3 . Siano poi v il numero di vertici, a il numero di archi e si supponga v 3. Allora si ha:

a  2v – 4

Dimostrazione. La dimostrazione ha la stessa struttura di quella del Teorema precedente.

Nel caso banale di una sola faccia infinita, si ottiene (ragionando come nella dimostrazione del Teorema precedente) che il grafo in questione è un albero, dunque v=a+1 ed essendo per ipotesi v3 si ha:

2v-4 = v + v – 4  v + 3 – 4 = v -1 = a e si ha la tesi.

Nel caso dell’esistenza anche di facce finite, si costruisce la matrice booleana come nella dimostrazione precedente (con righe corrispondenti alle f facce di una rappresentazione planare del grafo e colonne corrispondenti agli archi).

Tuttavia, quando si conta per “per righe” il numero di 1 nella matrice, si osserva che la frontiera di una faccia ha almeno 4 archi (una frontiera con 3 soli archi sarebbe un ciclo di lunghezza 3, contro l’ipotesi), quindi ogni riga ha almeno 4 valori uguali ad 1, e la somma di tali valori per tutte le righe è  4f. Contando “per colonne” si ottiene (come nella dimostrazione del Teorema precedente) che il numero di 1 nella matrice è =2a. Si ricava allora 2a 4f ossia f (1/2)a.

Applicando la formula di Eulero per i grafi planari connessi:

a = v + f – 2  v + (1/2)a – 2 ; 2a  2v + a – 4 ; a  2v – 4 cioè la tesi.

Come applicazione di tale Teorema si ha il seguente risultato:

il grafo dei servizi K3,3 non è un grafo planare (dunque il problema dei servizi ha risposta negativa). Infatti il grafo K3,3 è un grafo semplice e connesso ed inoltre non contiene cicli di lunghezza 3 (si può verificare notando che il suo numero cromatico è 2, dunque tutti i cammini ciclici hanno lunghezza pari, per un Teorema già dimostrato sulle colorazioni dei grafi): se per assurdo fosse planare, per l’ultimo Teorema dimostrato si dovrebbe avere a  2v – 4 (dove a=numero degli archi=9, v=numero dei vertici=6), e ciò ovviamente non è vero.

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 (omettiamo la dimostrazione).

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” (handshaking 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 handshaking problems) : ne esporremo uno come esempio.

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.

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’.

Prima di dimostrare vera tale affermazione, notiamo che se un grafo non orientato 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.

Dimostriamo ora vera l’affermazione precedente: 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.