Matematica Discreta Lezione del giorno 13 marzo 2009

(1)

Matematica Discreta

Lezione del giorno 13 marzo 2009

Nella lezione precedente abbiamo dimostrato, che, in un qualunque grafo non orientato, la somma dei gradi dei vertici coincide con il doppio del numero degli archi.

Questo risultato implica una conseguenza:

Corollario. In un qualunque grafo non orientato, il numero di vertici di grado dispari é multiplo di 2 (quindi, se non é 0, é un numero naturale pari).

Dimostrazione: siano x

1

,x

2

,...,x

r

i vertici distinti del grafo, ordinati in modo che x

1

,x

2

,....,x

s

siano quelli di grado dispari, ed x

s+1

,...,x

r

siano quelli di grado pari. Per il Teorema precedente, se indichiamo con g

1

,g

2

,...,g

r

rispettivamente i gradi dei vertici x

1

,x

2

,...,x

r

, si ha (se t è il numero degli archi del grafo):

2t = g

1

+g

2

+...+g

r

(*)

Poiché per costruzione i gradi g

1

,g

2

,...,g

s

sono dispari, mentre i gradi g

s+1

,g

s+2

,...,g

r

sono pari, si ha:

g

1

=2h

1

+1, ..., g

s

=2h

s

+1, g

s+1

=2h

s+1

, ..., g

r

=2h

r

dove h

1

,...,h

s

,h

s+1

,....,h

r

sono opportuni numeri interi.

Dall’eguaglianza (*) si ottiene allora:

2t = 2(h

1

+....+h

s

+h

s+1

+...+h

r

)+s s = 2(t-h

1

-....-h

s

-h

s+1

+...-h

r

)

dunque s (il numero dei vertici di grado dispari) é multiplo di 2, come si voleva dimostrare.

Grafi planari

Consideriamo il grafo non orientato definito formalmente dall’insieme di vertici V={a,b,c,d}, dall’insieme di archi A={1,2,3,4,5,6} e dalla funzione di adiacenza f: A  V

2

(dove V

2

é l’insieme dei sottoinsiemi di cardinalità 2 di V) definita da f(1)={a,b}, f(2)={b,c}, f(3)={b,d}, f(4)={a,d}, f(5)={d,c}, f(6)={a,c}.

Una possibile rappresentazione nel piano di tale grafo é la seguente:

1 a b 4

6 3 2

c d 5

Come si vede, in tale rappresentazione vi sono archi (l’arco 4 e l’arco 2) che nel piano si intersecano in un punto (al centro del disegno) che non é un vertice del grafo.

Si può però scegliere una diversa rappresentazione del grafo in cui ciò non succede, cioé in cui gli

archi si intersecano solo in punti del piano che sono vertici del grafo, per esempio la seguente:

(2)

1 a b 4

6 3

2 c d 5

Una rappresentazione nel piano con la proprietà suddetta (ossia in cui gli archi si intersecano solo in punti del piano che sono vertici del grafo) é detta rappresentazione planare del grafo: dunque il grafo dell’esempio precedente ha una rappresentazione planare (vedremo che non per tutti i grafi ne esiste una).

Un grafo planare é un grafo non orientato che ha almeno una rappresentazione planare.

Il grafo dell’esempio precedente é un grafo planare.

Esempio: il grafo dei ponti di Konisberg é un grafo planare, avendo la seguente rappresentazione planare:

a 6 1 2

b

5 d

3 4

c 7

Anche il grafo semplice non orientato associato ad una qualunque mappa geografica (in cui i vertici sono le regioni e i vertici corrispondenti a due regioni confinanti sono collegati da un arco) è un grafo planare, come si può dimostrare formalmente (intuitivamente basta “rimpicciolire” ogni regione fino a ridurla ad un punto, tenendola collegata con un arco con ognuna delle regioni confinanti).

Lo studio dei grafi planari si applica a diverse situazioni: per esempio al progetto di un circuito elettronico, in cui si cerca di fare in modo che le “piste elettriche” (archi) che collegano fra loro

“componenti” del circuito (vertici) non si intersechino fra loro, tranne che nei componenti che essi collegano.

Vedremo poi esempi di grafi non orientati che non sono planari: il grafo K

3

,

3

dei 3 servizi e il

grafo semplice completo K

5

con 5 vertici.

(3)

Il grafo K

3

,

3

dei servizi.

Problema dei 3 servizi: Siano A, B, C tre abitazioni ed a, b, c tre centrali che forniscono servizi (luce, acqua, gas) e si colleghi 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 il problema in teoria dei grafi: costruiamo un grafo non orientato semplice 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 grafo è spesso indicato con il simbolo K

3

,

3

)

Una possibile rappresentazione nel piano del grafo K

3

,

3

è la seguente:

A B C

K

3

,

3

a b c

Il problema dei 3 servizi è equivalente al seguente: il grafo suddetto é un grafo planare, cioè esiste una sua rappresentazione planare ?

Dimostreremo che il grafo K

3,3

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

Il grafo completo K

5

.

Ricordiamo che un grafo è completo se, comunque presi 2 vertici distinti, esiste almeno un arco che li unisce. Consideriamo il grafo (non orientato) completo semplice con 5 vertici (detto anche grafo K

5

). I 5 vertici sono a 2 a 2 reciprocamente collegati da un arco, per un totale di 10 archi.

Una possibile rappresentazione nel piano del grafo K

5

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.

Problema: il grafo K

5

è planare ? Dimostreremo che la risposta è negativa.

La formula di Eulero per i 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 punti degli archi) in sottoinsiemi del piano detti facce (due punti del piano appartengono alla stessa faccia se è possibile tracciare una linea continua che li unisce senza attraversare gli archi).

Notiamo anche che una delle facce è di area infinita.

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

(4)

 



 

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

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

Esempio: nella rappresentazione planare del grafo dei ponti di Konisberg vista sopra, il contorno della faccia  è formato dagli archi 6,2,5 (per la numerazione degli archi si faccia riferimento all’esempio ancora precedente); il contorno della faccia (infinita)  è invece 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.

Teorema (formula di Eulero per i grafi planari). 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.

Dimostrazione. Dimostreremo la formula per induzione su f (che assume valori nei numeri naturali).

Nel caso f=1, la rappresentazione planare avrà solo la faccia infinita; la non esistenza di facce finite implica che tutti gli archi del grafo formino “catene” del tipo:

……….

Ma l’ipotesi che il grafo sia connesso implica che di tali catene ve ne sia una sola. Dunque i vertici e gli archi del grafo sono tutti presenti nell’unica catena, e perciò il numero di vertici v supera di 1 unità il numero a di archi; da v=a+1 segue allora f = 1 = a – v +2, ossia la formula vale per f=1.

Supponiamo vera la formula per un valore fissato di f e dimostriamola vera per il valore successivo f+1.

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

Ma se f+1 è il numero di facce nella rappresentazione planare del grafo, possiamo “cancellare” dal grafo un arco che sia comune al contorno di 2 facce (una delle 2 facce può essere anche quella infinita): otteniamo in tal modo un nuovo grafo non orientato planare che ha v vertici (come il grafo originale) ma a-1 archi ed f facce (le 2 facce dal cui contorno abbiamo cancellato l’arco formano ora una sola faccia). Poiché la formula è per ipotesi vera per f, possiamo affermare che:

f = (a-1) – v +2

(5)

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

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

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: