Matematica Discreta Lezione del giorno 11 marzo 2010

(1)

Matematica Discreta

Lezione del giorno 11 marzo 2010

Abbiamo dimostrato la seguente formula di Eulero:

f = a – v +2

valida per qualunque grafo planare connesso (dove f=numero delle facce di una qualunque rappresentazione planare del grafo, a=numero degli archi del grafo, v=numero dei vertici del grafo).

Osservazione: Notiamo che la formula di Eulero può non essere più valida se il grafo planare non è connesso. Per esempio nella seguente rappresentazione planare di un grafo (non connesso) con v=4 vertici, a=4 archi:

1 a b 2

3 c d

4 il numero di facce è f=3, dunque non è valida la relazione f = a – v +2.

Esiste in effetti un Teorema più generale (di cui ometteremo la dimostrazione) che riguarda un qualunque grafo planare (connesso o non connesso):

in ogni grafo planare con v vertici, a archi, f facce si ha f = a – v + c + 1

dove c è il numero delle componenti connesse del grafo.

Si noti che nel caso di un grafo planare connesso si ha c=1, e si ritrova la formula di Eulero.

Nell’ultimo esempio (grafo non connesso) si ha c=2, a=4, v=4, f=3 e dunque f = a – v + c + 1, come previsto.

Dalla formula di Eulero valida per i grafi planari connessi, 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 all’inizio della dimostrazione del Teorema sulla formula di Eulero, il grafo è un albero, si ha v=a+1 e quindi:

3v-6 = v + 2v – 6  v + 6 – 6 = v = a+1 > a

e si ha la tesi.

(2)

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 nella sua frontiera 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 è dunque 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 è dunque

2a.

Eguagliando il numero di valori uguali ad 1 contati per righe e per colonne si ottiene 2a3f ossia f(2/3)a.

Ricavando il numero di archi 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.

D’altronde lo stesso Teorema non può aiutarci per dimostrare che il grafo dei servizi K

3,3

non è planare: infatti il grafo K

3,3

(connesso e semplice) soddisfa la diseguaglianza a  3v – 6, in quanto si ha a=9, v=6.

Nella prossima lezione dimostreremo un altro Teorema sui grafi planari, la cui applicazione

permetterà di dimostrare la non planarità del grafo K

3,3