Matematica Discreta Lezione del giorno 20 marzo 2012

Matematica Discreta

Lezione del giorno 20 marzo 2012

Riprendiamo la trattazione della teoria dei grafi planari.

Abbiamo dato già la seguente definizione: un grafo non orientato è detto grafo planare se fra le sue diverse rappresentazioni nel piano ne esiste almeno una che è una rappresentazione planare, cioè in cui gli archi si incontrano solo in punti del piano che sono vertici.

Esempio: il grafo dei ponti di Konisberg é un grafo planare, avendo, come visto più volte, la seguente rappresentazione planare:

a 6 1 2

b

5 d

3 4

c 7

Se un grafo non orientato è planare può avere più di una rappresentazione planare; per esempio il seguente grafo (già esaminato in una lezione precedente):

1

a b 4

6 3 2

c 5 d

è un grafo planare perché per esempio (come già visto) ha la seguente rappresentazione planare:

1

a b 4

6 3

2

c 5 d

:

Ma lo stesso grafo ha anche la seguente rappresentazione planare:

a

6 1 4 b

2 3

c 5 d

Esamineremo ora esempi di grafi non orientati che non sono grafi planari: i più importanti sono il grafo K

,

dei 3 servizi e il grafo semplice completo K

con 5 vertici.

Il grafo K

,

dei servizi.

Problema dei 3 servizi: Siano A, B, C tre abitazioni ed a, b, c tre centrali che forniscono servizi (luce, acqua, gas); si vorrebbe collegare ognuna delle centrali con ognuna delle abitazioni mediante una linea: è possibile fare in modo che le 9 linee da costruire non si intersechino, se non nelle abitazioni stesse e nelle centrali ?

Tale problema fu posto per la prima volta negli Stati Uniti nel 1913 come gioco enigmistico dal titolo “Water, Gas and Electricity”.

Si può tradurre anche questo problema (come quello dei circuiti elettronici) in teoria dei grafi:

costruiamo un grafo non orientato in cui A,B,C,a,b,c, sono 6 vertici, e in cui ognuno dei 3 vertici A,B,C è collegato ad ognuno dei vertici a,b,c da un arco (tale tipo di grafo è spesso indicato con il simbolo K

,

e detto appunto “grafo dei servizi”).

Il progetto precedente (collegare ognuna delle centrali con ognuna delle abitazioni mediante una linea in modo che le 9 linee da costruire non si intersechino, se non nelle abitazioni stesse e nelle centrali) sarà realizzabile solo se il grafo K

è un grafo planare.

Una possibile rappresentazione piana del grafo K

,

è la seguente:

A B C

K

,

a b c

Questa rappresentazione piana non è però una rappresentazione planare: gli archi si intersecano anche in punti del piano che non sono vertici del grafo. Esiste una rappresentazione planare di tale grafo ?

Si può provare a disegnare in modo diverso gli archi, in modo da evitare che si intersechino in punti

del piano che non sono vertici. Nella seguente rappresentazione piana la situazione è migliorata, ma

essa non è ancora una rappresentazione planare, perché c’è ancora un punto di intersezione fra archi

che non è un vertice:

A B C K

,

a b c

Dimostreremo in seguito che in effetti i tentativi per trovare una rappresentazione planare di tale grafo sono inutili, perché il grafo K

non è planare, ed il problema dei 3 servizi non ha dunque soluzione.

Il grafo K

.

Ricordiamo che un grafo è completo se, comunque presi 2 vertici distinti, esiste almeno un arco che li ha come estremi, mentre un grafo è semplice se, comunque presi 2 vertici distinti, esiste non più di un arco che li ha come estremi. Consideriamo il grafo non orientato completo semplice con 5 vertici (detto anche grafo K

): dunque in tale grafo i 5 vertici sono a 2 a 2 reciprocamente collegati da un solo arco, per un totale di 10 archi.

Una possibile rappresentazione piana del grafo K

si ottiene disegnando un pentagono e tutte le sue possibili diagonali: i vertici sono i 5 vertici del pentagono, e gli archi sono i 5 lati del pentagono e le 5 diagonali:

Tale rappresentazione piana ovviamente non è una rappresentazione planare perché non è vero che gli archi si intersecano solo in punti del piano che sono vertici del grafo.

Problema: il grafo K

è planare ? Dimostreremo che anche in questo caso la risposta è negativa.

Per decidere se alcuni degli esempi illustrati sopra sono grafi non planari, procederemo nel modo

seguente: dimostreremo alcune proprietà che sono soddisfatte dai grafi planari; se un grafo non

soddisferà tutte le proprietà che troveremo, potremo concludere che non è un grafo planare.

Sia dato un grafo planare, e una sua qualunque rappresentazione planare (dunque una rappresentazione piana in cui gli archi si intersecano solo in punti del piano che sono vertici del grafo).

Sia A l’insieme dei punti del piano non appartenenti a nessuno degli archi. Dal punto di vista geometrico la rappresentazione planare determina una partizione dell’insieme A in sottoinsiemi del piano detti facce (due punti del piano appartengono alla stessa faccia se è possibile tracciare una linea continua, anche non rettilinea, che li unisce senza attraversare gli archi).

Notiamo anche che una delle facce è di area infinita (ed è detta appunto faccia infinita), mentre le altre sono di area finita (e sono dette appunto facce finite).

Esempio: nella solita rappresentazione planare del grafo dei ponti di Konisberg:

6 1  2 

5 

3  4  7

si distinguono 5 facce (le facce “finite” ,,, e la faccia “infinita” ).

La frontiera (o contorno) di una faccia è l’insieme degli archi i cui punti “toccano” (in senso geometrico) alcuni punti della faccia (si possono dare definizioni geometriche formalmente più precise, che ometteremo per semplicità).

Esempio: nella rappresentazione planare del grafo dei ponti di Konisberg vista sopra, il contorno della faccia  è per esempio formato dagli archi 6,2,5; invece il contorno della faccia (infinita)  è formato dagli archi 6,1,3,7.

Dimostreremo in seguito un’interessante formula (dovuta ad Eulero) che coinvolge il numero delle facce, dei vertici e degli archi di un grafo planare connesso. Più precisamente dimostreremo che, data una qualunque rappresentazione planare di un grafo planare, se f è il numero di facce in tale rappresentazione si ha sempre:

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

Prima di dimostrare tale formula 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 diversi fra loro.

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: Usando tale terminologia un cammino ciclico Euleriano (argomento che abbiamo studiato nelle lezioni precedenti) non è altro che un ciclo che percorre tutti gli archi del grafo.

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

Esempio: Il grafo dei ponti non è un albero (perché come visto poco sopra esso contiene cicli), mentre il seguente grafo non orientato è un albero:

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 in particolare tutti i vertici dell’albero abbiano grado >1 (nessun vertice è di grado 0 poiché in un grafo connesso non esistono vertici isolati).

Sia v

un qualunque vertice e sia a

un qualunque arco che abbia v

come uno degli estremi; sia poi

v

l’altro estremo di a

: si ha v

≠v

perché non vi sono cappi. Poiché v

ha grado >1, esiste un arco

a

≠a

che abbia v

come uno degli estremi; sia poi v

l’altro estremo di a

: si ha v

≠v

(se fosse v

=v

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

≠v

perché non vi sono cappi.

Dunque abbiamo creato 3 vertici distinti v

,v

,v

. Di nuovo, poiché v

ha grado >1, esiste un arco a

≠a

che abbia v

come uno degli estremi; sia poi v

l’altro estremo di a

: si ha v

≠v

, v

≠v

(se fosse v

=v

oppure v

=v

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

≠v

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

,v

,v

,v

.

E’chiaro che tale procedimento può continuare indefinitivamente, e ciò è una contraddizione perché il grafo (come tutti quelli che consideriamo nella nostra 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 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 è vero il seguente predicato:

in ogni albero in cui a è il numero degli archi si ha:

v = a+1 dove v è il numero dei vertici dell’albero.

Dimostrazione.

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

Per il Teorema precedente esiste nell’albero almeno una foglia, ossia un vertice w di grado 1, che è estremo di un unico 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 è k, mentre il numero di vertici è v-1. Poiché per a=k il teorema è vero per ipotesi, vale la relazione fra il numero dei vertici e quello degli archi:

v-1=k+1

ossia v=k+2, come si voleva dimostrare.