Matematica Discreta Lezione del 10 marzo 2010 Teorema.

(1)

Matematica Discreta Lezione del 10 marzo 2010

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 circuito, 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 circuito, 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) 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 “allungare” 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. In ogni albero, se a è il numero degli archi e se v è il numero dei vertici, si ha:

v = a+1 Dimostrazione.

Dimostriamolo per induzione sulla variabile a (numero degli archi).

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, 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 circuiti (perché è sottografo dell’albero iniziale che non contiene circuiti). Inoltre è ovvio che tale nuovo grafo è ancora connesso come l’albero iniziale (elidere l’unico arco che ha w come estremo porta ad abolire solo i cammini fra 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.

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. Dal punto di vista

geometrico ciò determina una partizione dell’insieme dei punti del piano diversi dai vertici e dai

(2)

punti appartenenti agli archi 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 



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 sono “adiacenti” (in senso geometric) a 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.

Nel caso di un grafo planare che sia anche connesso dimostreremo un’interessante relazione fra il numero delle facce, dei vertici e degli archi, scoperta da Eulero.

Teorema (formula di Eulero per i grafi planari connessi). Sia dato un grafo planare connesso.

In qualunque rappresentazione planare del grafo il numero f di facce è dato dalla seguente formula:

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 planare).

Dimostrazione.

Dimostreremo la formula per induzione sulla variabile f (numero delle facce).

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

(3)

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 costruito ha un numero di facce uguale (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 il grafo planare connesso ora costruito 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):