Matematica Discreta Lezione del giorno 18 marzo 2009

(1)

Matematica Discreta

Lezione del giorno 18 marzo 2009

Dalla formula di Eulero valida per i grafi planari, si possono dedurre alcune conseguenze, che possono essere utili per costruire esempi di grafi non planari.

Ricordiamo che un grafo non orientato è detto semplice se, comunque dati 2 vertici distinti, esiste al più un arco che li collega.

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

a  3v – 6

Dimostrazione. Sia f il numero di facce di una rappresentazione planare del grafo e siano x

1

,x

2

,

…..,x

f

le facce del grafo. Siano poi y

1

,y

2

,…..,y

a

gli archi del grafo.

Consideriamo dapprima un caso banale, quello in cui vi è una sola faccia (quella infinita): in tale caso, come visto in una dimostrazione precedente, essendo il grafo connesso i suoi archi formano una singola “catena” tale che v=a+1 (il numero di vertici supera di 1 il numero di archi):

……….

In tale caso, essendo per ipotesi v3 si ha:

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

Supponiamo ora che oltre alla faccia infinita vi siano altre facce finite.

Costruiamo una matrice booleana con f righe e con a colonne in cui facciamo corrispondere ordinatamente le righe alle facce x

1

,x

2

,…..,x

f

, e le colonne agli archi y

1

,y

2

,…..,y

a

: in ogni casella della matrice, all’incrocio fra la riga i e la colonna j, poniamo il valore 1 se la faccia x

i

(corrispondente alla riga i) ha nel suo contorno l’arco y

j

(corrispondente alla colonna j) mentre poniamo il valore 0 in caso contrario.

Contiamo “per righe” il numero di 1 nella matrice: in ogni riga, per costruzione, vi è un numero di valori uguali ad 1 che coincide con il numero degli archi del contorno della faccia corrispondente alla riga. L’ipotesi che il grafo sia semplice implica che il contorno di una faccia ha almeno 3 archi (un contorno con 2 soli archi implica che i 2 archi uniscono la stessa coppia di vertici, contro l’ipotesi che il grafo è semplice), quindi ogni riga ha almeno 3 valori uguali ad 1, e la somma di tali valori per tutte le righe è 3f.

Contiamo poi “per colonne” il numero di 1 nella matrice: in ogni colonna, per costruzione, il numero di valori uguali ad 1 coincide con il numero di facce che hanno nel loro contorno l’arco corrispondente alla colonna. Ma un arco può essere contorno di non più di 2 facce, quindi ogni colonna ha non più di 2 valori uguali ad 1, e la somma di tali valori per tutte le colonne è 2a.

Eguagliando il numero di valori uguali ad 1 contati per righe e per colonne si ottiene dunque 2a3f ossia f(2/3)a. Ricavando a dalla formula di Eulero e sostituendo, si ottiene:

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

Come applicazione di tale Teorema si ha il seguente risultato:

il grafo completo semplice con 5 vertici K

5

non è planare.

Infatti il grafo K

5

è 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, v=numero dei

vertici), e ciò non è vero perché a=10, v=5.

(2)

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 cammini ciclici di lunghezza 3 . Siano poi v il numero di vertici, a il numero di archi. Allora, se il numero di vertici v è 4, 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, essendo per ipotesi v4 si ha:

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

Nel caso dell’esistenza anche di facce infinite,si costruisce la matrice booleana come nella dimostrazione precedente.

Tuttavia, quando si conta per “per righe” il numero di 1 nella matrice, si osserva che il contorno di una faccia ha almeno 4 archi (un contorno con 3 soli archi sarebbe un cammino ciclico 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. Si ricava in questo caso 2a4f ossia f(1/2)a.

Ragionando allora come sopra:

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 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 cammini ciclici di lunghezza 3 (si può vedere esaminando direttamente il grafo, oppure notando che il suo numero cromatico è 2, dunque tutti i cammini ciclici hanno lunghezza pari).

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.

Dati 2 grafi (non orientati) G

1

e G

2

, diremo che il grafo G

1

è contraibile per archi al grafo G

2

, se G

2

si ottiene da G

1

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 e poi si elimina l’arco a, e si fondono i vertici v,w in un unico vertice (si dice che l’arco a é stato contratto).

Esempio: il seguente grafo G

1

v z G w y

è contraibile per archi al grafo dei servizi G

2

=K

3

,

3

: basta “fondere” per esempio i vertici v,w (eliminando l’arco che li unisce), e poi analogamente “fondere” i vertici z,y (eliminando l’arco che li unisce) per ottenere il grafo K

3

,

3

.

Il prossimo Teorema (di cui omettiamo la dimostrazione) dimostra che i grafi K

3

,

3

e K

5

sono in

qualche modo i grafi non planari “essenziali” per stabilire la non planarità di un grafo.

(3)

Definiamo prima di tutto il concetto di sottografo di un grafo fissato G

1

: un sottografo di G

1

é un grafo G

2

tale che tutti i vertici ed archi di G

2

siano anche vertici ed archi di G

1

.

Teorema di Kuratowski. Un grafo (non orientato) è non planare se e solo se contiene un sottografo contraibile per archi al grafo K

3

,

3

o al grafo K

5