Matematica Discreta Lezione del giorno 27 marzo 2012

(1)

Matematica Discreta

Lezione del giorno 27 marzo 2012

Sia dato un grafo planare, e una sua qualunque rappresentazione planare (ossia una rappresentazione nel piano 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 un 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, se f è il numero di facce in tale rappresentazione planare, 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 del grafo).

Dimostrazione.

Utilizzeremo 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 un risultato dimostrato sugli alberi nella lezione precedente si avrà v =a + 1, da cui a – v = -1 ossia:

f = 1 = a – v +2

e la formula di Eulero è è dunque 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 sia il numero di facce (in una sua rappresentazione planare): la tesi è che si ha f = k + 1 = a – v +2 (dove a, v indicano sempre il numero di archi e vertici del nostro 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 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.

(2)

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.

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. Premettiamo una osservazione.

Osservazione: in una rappresentazione planare di un grafo planare, un arco può essere parte della frontiera di 1 sola faccia o di 2 facce, come mostra il seguenti esempio.

a 1 2

e b c 6 3

5 d

4 In questa rappresentazione planare vi sono 2 facce (una infinita e l’altra finita): l’arco 3 è parte della frontiera di 1 sola faccia (quella finita) mentre tutti gli altri archi sono parte della frontiera di 2 facce (quella finita e quella infinita).

Si può notare anche che in una rappresentazione planare di un grafo planare, un arco non può essere parte della frontiera di 3 o più facce. Se infatti per assurdo l’arco di estremi a,b fosse parte della frontiera di 3 facce , ,  la situazione sarebbe la seguente (disegnando solo la parte “locale”

nelle vicinanze dell’arco):



a 

 b

e la rappresentazione non sarebbe più planare (l’arco di estremi a, b intersecherebbe un altro arco in

un punto del piano che non è un vertice).

(3)

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 a  3v – 6.

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.

Sia x la somma dei valori numerici della matrice, contati “per righe”, e sia y la somma dei valori numerici della matrice, contati “per colonne”: per il principio del contare per righe e per colonne si ha x=y. Contiamo “per righe” la somma dei valori numerici nella matrice: in ogni riga, per costruzione, vi è un numero di valori uguali ad 1 che coincide con il numero degli archi della frontiera della faccia corrispondente alla riga. L’ipotesi che il grafo sia semplice implica che la frontiera di una faccia ha almeno 3 archi (una frontiera con 2 soli archi implicherebbe 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: si ha perciò x 3f.

Contiamo poi “per colonne” la somma dei valori numerici nella matrice: in ogni colonna, per costruzione, il numero di valori uguali ad 1 coincide con il numero di facce che hanno nella loro frontiera l’arco corrispondente alla colonna. Ma (come visto nell’Osservazione precedente) un arco è parte della frontiera di 1 o 2 facce, quindi ogni colonna ha un numero ≤2 di valori uguali ad 1, e la somma di tali valori per tutte le colonne è dunque ≤2a: si ha dunque y≤2a.

Alla fine si ottiene 3f≤x=y≤2a ossia f(2/3)a.

Ricavando il numero di archi a dalla formula di Eulero (valida per i grafi planari connessi) 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 (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 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=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 K

3,3

non è planare (ricordiamo che in tale grafo vi sono 6 vertici dei quali 3 sono adiacenti agli altri 3): infatti il grafo K

3,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 K

3,3

.

(4)

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”, 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 è x  4f. Contando “per colonne” si ottiene (come nella dimostrazione del Teorema precedente) che la somma di tali valori per tutte le colonne è y≤2a. Alla fine si ottiene 4f≤x=y≤2a 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 K

3

,

3

non è un grafo planare (dunque il problema dei servizi ha risposta

negativa). Infatti il grafo K

3

,

3