Lezione del giorno 3 maggio 2011 La formula di Eulero per i grafi planari.

(1)

Lezione del giorno 3 maggio 2011

La formula di Eulero per i grafi planari.

Abbiamo definito nella lezione precedente il concetto di grafo planare e di facce determinate da una sua rappresentazione nel piano in cui gli archi sono disegnati in modo che si intersechino solo nei vertici.

Dimostreremo inseguito un’interessante formula (dovuta ad Eulero) che coinvolge il numero delle facce, dei vertici e degli archi di un grafo planare connesso.

Prima di dimostrarla dobbiamo premettere alcune nozioni relative a particolari grafi non orientati, detti alberi.

Dato un grafo non orientato, chiameremo ciclo un qualunque cammino ciclico nel grafo, nel quale tutti gli archi percorsi sono distinti.

Esempio: Nel grafo dei ponti di Konisberg:

a 6 1 2

b

5 d

3 4

c 7

il seguente cammino ciclico è un ciclo:

a 1 b 3 c 4 b 2 a

mentre il seguente cammino ciclico non è un ciclo (perché l’arco 1 è percorso più di una volta):

a 1 b 3 c 4 b 1 a

Osservazione: Con tale terminologia un cammino ciclico Euleriano (di cui abbiamo parlato nel Teorema di Eulero) non è altro che un ciclo che percorre tutti gli archi del grafo.

Un albero è un grafo non orientato connesso e in cui non esistono cicli.

Esempio: Il grafo dei ponti non è un albero, mentre il seguente grafo non orientato è un albero:

(2)

a 1 2 b c 3 d

4 5

e f

In un albero ogni vertice di grado 1 è detto foglia.

Nell’esempio precedente le foglie sono 3: i vertici b,e,f . Teorema. In ogni albero esiste almeno una foglia.

Dimostrazione.

Supponiamo per assurdo che tutti i vertici dell’albero abbiano grado ≠1, quindi >1 (nessun vertice è di grado 0 poiché in un grafo connesso non esistono vertici isolati).

Sia v

1

un qualunque vertice e sia a

1

un qualunque arco che abbia v

1

come uno degli estremi; sia poi v

2

l’altro estremo di a

1

: si ha v

2

≠v

1

perché non vi sono cappi. Poiché v

2

ha grado >1, esiste un arco a

2

≠a

1

che abbia v

2

come uno degli estremi; sia poi v

3

l’altro estremo di a

2

: si ha v

3

≠v

1

(se fosse v

3

=v

1

esisterebbe un ciclo, contro l’ipotesi che il grafo è un albero) e v

3

≠v

2

perché non vi sono cappi.

Dunque abbiamo creato 3 vertici distinti v

1

,v

2

,v

3

. Di nuovo, poiché v

3

ha grado >1, esiste un arco a

3

≠a

2

che abbia v

3

come uno degli estremi; sia poi v

4

l’altro estremo di a

3

: si ha v

4

≠v

1

, v

4

≠v

2

(se fosse v

4

=v

1

oppure v

4

=v

2

esisterebbe un ciclo, contro l’ipotesi che il grafo è un albero) e v

4

≠v

3

perché non vi sono cappi. Abbiamo così creato 4 vertici distinti v

1

,v

2

,v

3

,v

4

.

E’chiaro che tale procedimento può continuare in definitivamente, e ciò è una contraddizione perché il grafo (come tutti quelli che consideriamo nella Teoria dei Grafi) ha un numero finito di vertici.

Osservazione. Come si vede dalla precedente dimostrazione, è essenziale la convenzione (valida in tutto il nostro corso di Teoria dei Grafi), che ogni grafo abbia un numero finito di archi e vertici.

Non è difficile capire che in un albero con infiniti vertici potrebbero non esistere vertici di grado 1 (si potrebbe “prolungare” l’albero senza fine e non esisterebbero foglie).

Dal Teorema precedente segue una conseguenza importante che lega il numero dei vertici e degli archi in un grafo:

Teorema. Per ogni numero naturale a è vera la seguente affermazione:

in ogni albero in cui a è il numero degli archi, v è il numero dei vertici si ha:

v = a+1 Dimostrazione.

Dimostriamolo utilizzando il principio di induzione.

Per a=1 si ha un solo arco, e poiché nessun vertice nell’albero è isolato (perché è un grafo connesso) vi sono solo 2 vertici (estremi dell’unico arco): dunque a=1, v=2 e il Teorema è vero.

Supponiamolo vero per a=k, e dimostriamolo vero per a=k+1.

Sia dunque dato un albero con a=k+1 vertici, e dimostriamo che in tale albero, se v è il numero dei

vertici, si ha v=a+1=k+2.

(3)

Per il Teorema precedente esiste nell’albero almeno una foglia, ossia un vertice w di grado 1, da cui esce un solo arco. Consideriamo un nuovo grafo ottenuto dall’albero elidendo il vertice w e l’unico arco che lo ha come estremo.

Tale nuovo grafo non contiene cicli (perché esso è una parte dell’albero originario che non contiene cicli). Inoltre è ovvio che tale nuovo grafo è ancora connesso come l’albero originario (elidere l’unico arco che ha w come estremo porta ad abolire solo i cammini che uniscono w ed un altro vertice, ma poiché w non appartiene al nuovo grafo, è ancora vero che fra 2 vertici distinti del nuovo grafo esiste sempre un cammino). In totale il nuovo grafo è anch’esso un albero, come il grafo originario.

Il numero di archi di tale nuovo albero è a-1=k, mentre il numero di vertici è v-1. Poiché per k il teorema è vero per ipotesi, vale la relazione fra il numero dei vertici e quello degli archi:

v-1=(a-1)+1=a

ossia v-1=a=k+1 da cui v=k+2, come si voleva dimostrare.

Torniamo alla teoria dei grafi planari.

Sia dato un grafo planare, e una sua qualunque rappresentazione planare in cui gli archi si intersecano solo nei vertici del grafo.

Abbiamo già definito nella lezione precedente il concetto di faccia e di frontiera di una faccia, relativamente alla rappresentazione planare scelta per il grafo.

Dimostriamo l’importante risultato dovuto ad Eulero:

Teorema (formula di Eulero per i grafi planari connessi).

Per ogni numero naturale f è vera la seguente affermazione:

dato un grafo planare connesso e data una sua qualunque rappresentazione planare in cui gli archi si intersecano solo nei vertici del grafo, se f è il numero di facce in tale rappresentazione, si ha:

f = a – v +2 dove v é il numero di vertici, a é il numero di archi.

(una conseguenza di tale risultato è che il numero delle facce non cambia se cambiamo la rappresentazione planare in cui gli archi si intersecano solo nei vertici del grafo).

Dimostrazione.

Utilizzeremo nuovamente il principio di induzione.

Nel caso f=1, la rappresentazione planare avrà solo una faccia, dunque solo la faccia infinita (che è sempre presente). In tale caso il grafo planare, oltre ad essere connesso, non avrà cicli (se per assurdo esistesse un ciclo, esso sarebbe la frontiera di una faccia finita, contraddizione); dunque il grafo planare sarà un albero, e per l’ultimo risultato dimostrato sugli alberi si avrà v=a+1, da cui:

f = 1 = (-1)+2 =a – v +2 e la formula è vera per f=1.

Supponiamo vera la formula per un valore f=k e dimostriamola vera per il valore f=k+1.

Sia dunque dato un grafo planare connesso tale che f=k+1 è il numero di facce (di una sua rappresentazione planare): la tesi è che si ha k+1 = a – v +2 (dove a, v indicano sempre il numero di archi e vertici del grafo planare connesso con f=k+1 facce).

Poiché f=k+1>1, il grafo ha almeno 2 facce: consideriamo quindi due delle facce che nella loro frontiera abbia almeno un arco t in comune (una delle due facce potrebbe anche essere quella infinita), e costruiamo un nuovo grafo ottenuto cancellando dal grafo iniziale tale arco t: otteniamo in tal modo un nuovo grafo non orientato planare che ha sempre v vertici (come il grafo originale) ma a-1 archi ed una faccia in meno rispetto al grafo originale (le 2 facce dalla cui frontiera abbiamo cancellato l’arco t formano ora una sola faccia); quindi il nuovo grafo planare ha un numero di facce = (k+1)-1=k. E’ facile verificare che tale grafo è ancora connesso come quello originale:

infatti abbiamo abolito solo un arco della frontiera di una faccia, quindi qualunque cammino fra 2

vertici che coinvolga tale arco può essere modificato sostituendo tale arco con il cammino formato

dai rimanenti archi della frontiera della faccia; questo porta a concludere che anche nel nuovo grafo

(4)

comunque dati 2 vertici esiste almeno un cammino che li unisce. Poiché la formula di Eulero è per ipotesi vera per un grafo planare connesso con k facce, possiamo affermare che in tale nuovo grafo si ha (tenendo conto che (a-1) è il numero degli archi, e che v è il numero dei vertici del nuovo grafo planare):

k = (a-1) – v +2

da cui, sommando 1 ad ambo i membri, si ottiene:

k+1 = a – v +2 e la formula è vera anche per f=k+1.

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

1 a b 2

3 c d

4 il numero di facce è f=3 (sono 2 facce finite ed 1 infinita), dunque non è più vero che 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.

(5)

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 è contorno di 2 facce, quindi ogni colonna ha 2 valori uguali ad 1, e la somma di tali valori per tutte le colonne è dunque =2a.