Matematica Discreta Lezione del 15 marzo 2010

(1)

Matematica Discreta Lezione del 15 marzo 2010

Se nell’ultimo Teorema dimostrato aggiungiamo un’ulteriore ipotesi, si ottiene un diverso risultato:

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

Di nuovo osserviamo che il Teorema precedente non vale per v=2: in tale caso vi è un solo arco che unisce i 2 vertici del grafo, quindi a=1 e non è vero che a  2v – 4 .

Come applicazione di tale Teorema si ha il seguente risultato:

il grafo dei servizi K

3

,

3

non è un grafo planare (dunque il problema dei servizi ha risposta negativa). Infatti il grafo K

3

,

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

Per l’ultimo Teorema dimostrato, se il grafo K

3,3

fosse planare, si dovrebbe avere a  2v – 4 (dove a=numero degli archi, v=numero dei vertici), e ciò non è vero perché a=9, v=6.

Il teorema di Kuratowski sui grafi planari.

Vedremo che i 2 grafi non planari K

3,3

e K

5

sono in qualche modo “essenziali” per verificare la non planarità di un grafo, come dimostrato dal matematico Kuratowski.

Introduciamo prima alcune definizioni.

Dati 2 grafi non orientati G

1

e G

2

, diremo che il grafo G

1

è una espansione del grafo G

2

, se G

1

si ottiene da G

2

ripetendo un numero finito di volte la seguente operazione: si fissa in G

1

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 a

1

(di estremi v,z) ed a

2

(di estremi z,w):

v a w v a

1

z a

2

w

(prima dell’operazione) (dopo l’operazione)

(2)

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 G

1

A B C G

1

z y a b c è una espansione del grafo dei servizi G

2

=K

3

,

3

:

A B C

G

2

= K

3

,

3

a b c

(sono stati inseriti 2 nuovi vertici z,y all’interno di 2 archi di K

3,3

).

E’ facile osservare che se un grafo G

1

è una espansione del grafo G

2

allora G

1

è planare se e solo se G

2

è planare. Infatti se si considera una rappresentazione planare di G

1

(in cui gli archi non si intersecano in punti che non sono vertici), basta “cancellare” i vertici di G

1

che sono stati inseriti nella sua costruzione a partire da G

2

e si ottiene una rappresentazione planare anche per G

2

.

Con il procedimento inverso, data una rappresentazione planare di G

2

, si può ottenere una rappresentazione planare di G

1

(inserendo vertici all’interno di archi).

Esempio: una possibile espansione del seguente grafo G

2

1 a b 4

6 3 G

2

2 c d 5

é il seguente grafo G

1

1 a b 4 10 7 f

e 3 G

1

8 9

c d

(3)

5 (è stato inserito un nuovo vertice e all’interno dell’arco 6 di estremi a,c, sostituendo tale arco 6 con due nuovi archi 7,8 ed è stato inserito un nuovo vertice f all’interno dell’arco 2 di estremi c,b, sostituendo tale arco 2 con due nuovi archi 9,10). Il grafo G

2

è planare, avendo per esempio la seguente rappresentazione planare: 1

a b 4

6 3

2 c d 5

e da essa si può facilmente costruire una rappresentazione planare per G

1

, inserendo i nuovi vertici e,f all’interno rispettivamente degli archi 6,2 1

a b 4

7 e 3

10

8 c d 5

9 Da quanto osservato segue anche che se un grafo G

1

è una espansione del grafo G

2

allora G

1

è non planare se e solo se G

2

è non planare.

In un esempio considerato sopra, abbiamo visto un grafo G

1

espansione del grafo dei servizi G

2

=K

3,3

: poiché sappiamo che K

3,3

non è planare, ne deduciamo che anche G

1

non è planare.

Un’altra osservazione utile è la seguente. Se un grafo G

1

è contenuto come sottografo di un grafo G

2

(nel senso che tutti i vertici ed archi di G

1

siano anche vertici ed archi di G

2

) allora se G

2

è planare anche il sottografo G

1

è planare (basta considerare una rappresentazione planare di G

2

e

“cancellare” archi e vertici che non fanno parte di G

1

per ottenere una rappresentazione planare di

G

1

).

(4)

Esempio: un possibile sottografo del seguente grafo G

2

1 a b 4

6 3 G

2

2 c d 5

é il seguente grafo G

1

1 a b 4

G

1

2 c d 5

Il grafo G

2

è planare, e da una sua rappresentazione planare:

1 a b 4

6 3

2 c d 5

si può ricavare una rappresentazione planare per G

1

cancellando gli archi 3,6 che non fanno parte di G

1

1 a b 4

6 3

2 c d

5

(5)

Mettendo insieme tutte le osservazioni precedenti si deduce che: se un grafo G

1

contiene un sottografo G

2

che sia una espansione di K

5

o di K

3,3

allora G

1

non è planare.

Infatti se per assurdo G

1

fosse planare, anche il sottografo G

2

sarebbe planare, e dunque K

5

o K

3,3

sarebbero planari (essendo G

2

espansione di uno dei due) e si otterrebbe una contraddizione.

Il matematico Kuratowski dimostrò che è anche vero il viceversa, ottenendo il seguente Teorema (di cui omettiamo la dimostrazione) che fornisce una condizione necessaria e sufficiente per la non planarità di un grafo:

Teorema di Kuratowski. Un grafo non orientato è non planare se e solo se contiene come sottografo una espansione del grafo K

3

,

3

o del grafo K

5

.

Esempio: il seguente grafo 1

2 è non planare: infatti (eliminando gli archi 1,2) si nota che esso contiene un sottografo espansione del grafo dei servizi K

3

,

3

(si tratta del grafo considerato in un 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) - nel nuovo grafo così ottenuto si cerca un sottografo K

5

(cioè 5 vertici tutti adiacenti reciprocamente fra loro) o un sottografo K

3,3

(cioè 6 vertici dei quali 3 sono adiacenti agli altri 3) - se tale ricerca ha successo, il grafo è non planare; in caso contrario è palnare.

Alcuni problemi risolubili con la teoria dei grafi.

1) Problemi delle “strette di mano” (handshaking problems).

Consideriamo una riunione di n persone, alcune delle quali si stringono la mano fa loro.

Possiamo rappresentare la 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.

(6)

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