LA CARATTERISTICA DI EULERO
Triangolazioni
Definizione. Una triangolazione di una superficie compatta S è data da una famiglia
finita di suoi sottospazi chiusi {T1 , ..., Tn } che ricoprano S e da una famiglia (finita) di
0
0
omeomorfismi {φi }i=1, ..., n dove φi : Ti → Ti e Ti è un triangolo in R2 (ovvero l’inviluppo
convesso determinato da tre punti non allineati del piano). I Ti sono detti triangoli. Le
0
immagini tramite tali omeomorfismi di vertici e lati dei Ti si dicono vertici e lati della
triangolazione. Si richiede inoltre che, per i 6= j, sia verificata una e una soltanto delle
seguenti affermazioni:
(1) Ti e Tj sono disgiunti.
(2) Ti e Tj hanno in comune un solo vertice.
(3) Ti e Tj hanno in comune solo due vertici e il lato che li connette.
♦
Vale il seguente teorema, che ci limitiamo ad enunciare.
Teorema 1. Ogni superficie compatta ammette una triangolazione.
Poichè due triangoli distinti non possono avere gli stessi vertici una triangolazione è
completamente definita una volta assegnati i vertici dei triangoli e specificando quali terne
di vertici concorrono a formare un triangolo.
Osservazione. Segue anche dalla definizione che
• ogni lato è lato esattamente di due triangoli
• Sia v un vertice, i triangoli di vertice v possono essere riordinati in sequenza
T0 , ..., Tn − 1 , Tn = T0 in modo che triangoli consecutivi abbiano esattamente un
lato in comune e triangoli non consecutivi abbiano in comune soltanto il vertice v.
♦
Ecco alcuni esempi di superfici triangolate, rappresentate come poligoni topologici con
identificazione, i numeri si riferiscono ai vertici, le lettere ai lati identificati.
1
2
LA CARATTERISTICA DI EULERO
Figura 1. Toro. Questa triangolazione ha 16 vertici, 48 lati e 32 facce.
Figura 2. Sfera. La triangolazione ha 32 vertici, 66 lati e 32 facce.
Figura 3. Una triangolazione del piano proiettivo reale: 6 vertici, 15 lati
e 10 facce.
LA CARATTERISTICA DI EULERO
Figura 4. La superficie orientabile di genere due, ovvero la somma connessa di due tori (ottenuta come poligono topologico con identificazione da
un ottagono): la suddivisione ha 2 vertici, 12 lati e 8 facce. Per la triangolazione il calcolo è più faticoso (soprattutto contare i lati!)
Figura 5. (a sinistra) La somma connessa di due piani proiettivi ovvero
la bottiglia di Klein: 16 vertici, 48 lati e 32 facce.
Figura 6. (a destra) Il nasto di Möbius (superficie topologia compatta con
bordo): 19 vertici, 52 lati e 32 facce.
3
4
LA CARATTERISTICA DI EULERO
La caratteristica di Eulero
Definizione. Sia S una superficie compatta triangolata da T = {T1 , ..., Tn }. Definiamo
le seguenti quantià (numeri interi)
• v= numero di vertici
• e= numero di lati
• f = numeri di triangoli
La caratteristica di Eulero di S (a priori dipendente dalla triangolazione) è data da χ(S) =
v − e + f. ♦
Teorema 2. La caratteristica di Eulero cosı̀ definita non dipende dalla triangolazione.
Cenno di dimostrazione. Consideriamo suddivisioni di S in poligoni arbitrari, con n ≥ 1
lati e vertici, quindi non necessariamente triangoli. Inoltre ammettiamo che un lato possa
non suddividere una regione in due regioni distinte. Richiediamo che la parte interna di
ogni regione poligonale sia omeomorfa a un disco aperto del piano, che ogni lato privato
dei vertici sia omeomorfo a un intervallo aperto della retta euclidea e che la chiusura di
ogni tale lato sia omeomorfa a [0, 1] oppure S 1 . Infine si richiede che sia finito il numero di
vertici, lati e regioni poligonali. In particolare quindi le condizioni elencete sono soddisfatte
se si ha a che fare con una triangolazione. Definiamo come in precedenza la caratteristica
di Eulero come χ(S) = v − e + f . Osserviamo che le seguenti trasformazioni lasciano
invariata la caratteristica di Eulero
(1) Suddividere un lato aggiungendo un nuovo vertice in un punto interno: infatti
aumenta di uno il numero dei lati ma anche il numero dei vertici.
(2) Se due soli lati si incontrano in un dato vertice, eliminando tale vertice e ”fondendo”
i lati la caratteristica di Eulero non cambia.
(3) Suddividere un n-agono connettendo tra loro due vertici: infatti il numero delle
regioni aumenta di uno e cosı̀ anche il numero dei lati.
(4) Fondere tra loro due regioni aventi un lato in comune eliminando tale lato: sia il
numero di regioni che il numero di lati diminuiscono di uno.
LA CARATTERISTICA DI EULERO
5
(5) Introdurre all’interno di una regione un nuovo vertice e un nuovo lato, ma in modo
che la regione resti connessa, in questo caso aumentano di uno il numero di lati e
il numero di vertici.
(6) eliminare vertici e lati del tipo descritto appena sopra: il numero di vertici e il nu-
mero di lati decrescono di uno.
Se adesso proviamo che si può passare da una suddivisione di S a un’altra suddivisione in
un numero finito di operazioni tra quelle descritte ne seguirà l’invarianza della caratteristica
di Eulero.
0
Questo si prova facilmente nel caso in cui, date due triangolazioni T e T , i lati delle
due si intersechino in un numero finito di punti e in un numero finito di intervalli chiusi.
Supponiamo di sovrapporre infatti le due triangolazioni (per avere un’idea qualitativa del
procedimento si può osservare la figura 7).
Modifichiamo dapprima T aggiungendo nuovi vertici laddove i lati di T sono intersecati
0
dai lati di T e non vi sia già un vertice di T (sequenza finita di mosse di tipo (1)). Poi,
0
per ogni vertice di T che si trovi all’interno di una regione di T aggiungiamo (mossa di
0
tipo (5)) il vertice stesso e un lato (corrispondente a un lato o una porzione di lato di T ),
che lo connetta a un vertice preesistente. Infine, completiamo la sovrapposizione delle due
0
triangolazioni aggiungendo i lati mancanti (corrispondenti a lati o porzioni di lati di T ,
mosse di tipo (3)). Successivamente eliminiamo dalla suddivisione ottenuta per S vertici e
0
lati in modo da ottenere T .
0
Eliminiamo dapprima i lati che appartengono a T ma non a T e che suddividono in
due parti una regione (mossa di tipo (4)). Si eliminano poi quei lati e vertici che non
0
suddividono alcuna regione e che appartengono a T ma non a T (mossa di tipo (6)).
6
LA CARATTERISTICA DI EULERO
Figura 7
0
Restano allora da eliminare quei vertici in cui i lati di T intersecano quelli di T in punti
0
distinti dai vertici di T (mossa di tipo (2)).
0
Il caso in cui un lato di T e e uno di T si intersechino in un numero infinito di punti (si
pensi al caso dei due insiemi nel piano euclideo [−1, 1] × {0} e {(x, x sin( x1 )) | x ∈ [−1, 1] \
{0}}∪{(0, 0)}) è più complicato. Si può dimostrare che è sempre possibile ”deformare” una
LA CARATTERISTICA DI EULERO
7
delle due triangolazioni, ma facendo in modo che il numero di vertici, lati e facce rimanga
invariato, affinchè tale tipo di intersezione non avvenga.
Proposizione 3. Se S1 e S2 sono due superfici compatte e denotando con S1 ]S2 la loro
somma connessa, allora χ(S1 ]S2 ) = χ(S1 ) + χ(S2 ) − 2.
Dimostrazione. Supponiamo che S1 e S2 siano triangolate. Fare la somma connessa equivale a privare ciascuna superficie della parte interna di uno dei triangoli, prenderne l’unione
e identificare a due a due vertici e lati di tali triangoli. Perciò, se denotiamo rispettivamente con v1 , e1 , f1 e v2 , e2 , f2 vertici lati e triangoli della prima e seconda superficie, la
superficie ottenuta dalla somma connessa avrà v = v1 + v2 − 3 vertici, e = e1 + e2 − 3
lati e f = f1 + f2 − 2 triangoli. Da cui segue la formula.
Solidi platonici
Un poliedro che sia chiuso e convesso è detto essere un poliedro semplice. Ogni poliedro
semplice è omeomorfo a una sfera, pertanto la somma a segni alterni dei suoi vertici, lati
e facce è sempre uguale a 2. Quanto affermato segue dal fatto che l’immagine dei vertici,
spigoli e facce del poliedro tramite un omeomorfismo dota la sfera di una suddivisione del
tipo preso in considerazione nel teorema 2. Un poliedro è detto regolare se ogni sua faccia
è congruente allo stesso poligono regolare.
Vogliamo ora determinare condizioni per poter costruire poliedri regolari.
Denotiamo con E il numero di spigoli del poliedro, con F il numero delle sue facce e con
V il numero dei suoi vertici. Quindi V − E + F = 2. Supponiamo che un poliedro regolare
sia formato da n-agoni regolari e che in ogni vertice si incontrino f facce (n-agoni). Poichè
ogni spigolo appartiene a due facce e connette due vertici vale
2E = nF = f V
da cui segue
(1)
E(
2
2
− 1 + )=2⇔
f
n
1
1
1
1
+ = + .
E
2
f
n
Osserviamo poi che il minimo numero di facce che si incontrano in un dato vertice è tre, e
cosı̀ anche il minimo numero di spigoli di un poligono regolare, perciò f ≥ 3, n ≥ 3. Inoltre
se f e n fossero entrambi strettamente maggiori di 3 la (1) non potrebbe valere perchè si
otterrebbe E1 ≤ 0.
Esaminiamo quindi il caso f = 3. Deve essere n ≤ 5 per soddisfare (1) altrimenti
nuovamente si avrebbe E1 ≤ 0.
• Se n = 3 allora le facce del poliedro sono trinagoli equilateri e si ha che E = 6, F =
4, V = 4. Il solido cosı̀ ottenuto è il tetraedro.
• Se n = 4, le facce del poliedro sono dunque quadrati, E = 12, F = 6, V = 8 e si
ottiene il cubo (esaedro).
• Se infine n = 5 risulta E = 30, F = 12, V = 20. Il solido cosı̀ ottenuto è il
dodecaedro le cui facce sono pentagoni regolari.
8
LA CARATTERISTICA DI EULERO
Figura 8. Nell’ordine: tetraedro, ottaedro, icosaedro, cubo, dodecaedro.
Sia ora n = 3, 3 < f ≤ 5 (quest’ultima condizione segue da un’analisi analoga alla precedente), quindi cerchiamo ulteriori poliedri regolari le cui facce siano triangoli equilateri.
• Se f = 4 si ottiene E = 12, F = 8, V = 6. Il solido cosı̀ ottenuto è l’ottaedro.
• Se f = 5 allora E = 30, F = 20, V = 12 e si ottiene un icosaedro.
Non ci sono altre possibilità, per cui abbiamo determinato la totalità dei poliedri regolari.
Colorabilità
Definizione. Data una superficie S si definisce mappa sulla superficie il dato di un numero
finito di vertici e archi (lati) a due a due non intersecantesi che li connettano, disposti in
modo tale da suddividere la superficie in regioni semplicemente connesse. La mappa è
detta inoltre regolare se
(1) ogni vertice ha ordine (è il numero di lati che contengono tale vertice) non inferiore
a 3,
(2) ogni arco connette due vertici distinti,
(3) ogni arco separa due regioni distinte.
♦
Figura 9. mappa
Figura 10. mappa regolare
LA CARATTERISTICA DI EULERO
9
Quanti colori sono necessari per colorare una mappa regolare in una porzione limitata
del piano o su una sfera in modo tale che regioni adiacenti non abbiano mai lo stesso colore?
Si osserva facilmente che tre colori sono insufficienti (per esempio osservando la figura 12).
Si definisce numero cromatico (o costante cromatica) di una superficie S il minimo numero
di colori α tale che ogni mappa regolare su S possa essere colorata con al più α colori in
modo che regioni confinanti abbiano sempre colori diversi. In questa analisi, una porzione
limitata di piano è equivalente a una sfera, infatti si può passare da una rappresentazione
all’altra tramite la proiezione stereografica, considerando il complementare della porzione
limitata di piano come una calotta sferica contenente il polo di proiezione (come in figura
11).
Figura 11
Si può definire anche per una mappa su una superficie la caratteristica di Eulero come
somma a segni alterni di vertici, lati e regioni determinati dalla mappa. Ovviamente la
caratteristica di Eulero non dipende dalla particolare mappa ma è invariante e coincide
con la caratteristica di Eulero della superficie (nella dimostrazione dell’invarianza infatti
si utilizzano suddivisioni di una superficie più generali, tra le quali rientrano le mappe
regolari).
Consideriamo una superficie avente caratteristica di Eulero χ(S) > 0. Allora v − e + f >
0 (qui f denota il numero delle regioni). Dalle condizioni (1) e (2) della definizione segue
che 2e ≥ 3v per cui
6f − 2e > 0
Se denotiamo con fi il numero di regioni la cui frontiera è formata esattamente da i lati
con l’ovvia condizione che i ≥ 1 si può scrivere
X
X
6
fi −
ifi > 0
i
i
X
(6 − i)fi > 0.
ovvero
i
10
LA CARATTERISTICA DI EULERO
Figura 12
Deve pertanto esistere qualche regione la cui frontiera consista in i lati con i < 6. Possiamo
adesso dimostrare per induzione il seguente teorema
Teorema 4 (dei sei colori). Sia S una superficie con caratteristica di Eulero χ(S) > 0,
allora il numero cromatico di S è non maggiore di 6.
Dimostrazione. Procediamo per induzione sul numero di regioni f . Se f ≤ 6 la tesi è
ovvia. Sia ora f > 6 e supponiamo che il risultato sia vero per f − 1. Come osservato in
precedenza esiste una regione f ∗ la cui frontiera è formata da meno di sei lati. Contraendo
a un punto (un vertice) tale regione otteniamo una mappa regolare con f − 1 regioni,
che per ipotesi induttiva può essere colorata con al più sei differenti colori in modo tale
che regioni confinanti abbiano sempre colori diversi. Ripristinando la regione f ∗ , poichè
le regioni con essa confinanti sono al più cinque, è possibile assegnare a questa regione un
colore in modo che la tesi sia soddisfatta.
Di validità più generale è il seguente
Teorema 5. Ogni mappa regolare su una superficie S con caratteristica di Eulero χ(S) = χ
può essere colorata con al più γ colori, dove per γ vale
(2)
γf > 6(f − χ)
∀f > γ.
Dimostrazione. Procediamo per induzione sul numero di regioni f . Supponiamo quindi
0
0
che per γ soddisfacente la disuguaglianza dell’enunciato si abbia per qualche f , se f ≤ f ,
che ogni mappa regolare su S avente f regioni possa essere colorata con al più γ colori (in
modo che regioni contigue abbiano sempre colori differenti). In particolare questo è ovvio
per f ≤ γ. Poichè vale
χ = v − e + f, 2e ≥ 3v,
allora
6(f − χ) = 6(e − v) ≥ 2e,
LA CARATTERISTICA DI EULERO
11
e quindi da (2) anche γf > 2e. Quindi (ragionando in modo analogo a quanto fatto
per il teorema 4), almeno una regione deve avere frontiera costituita da meno di γ lati.
Contraendo a un punto tale regione χ rimane invariata e per l’ipotesi induttiva la mappa
cosı̀ ottenuta può essere colorata con al più γ colori. Ripristinando tale regione, poichè le
regioni ad essa contigue sono al più γ − 1, è sempre possibile assegnare ad essa un colore
in modo che la tesi risulti soddisfatta.
Vogliamo ora determinare per alcuni valori di χ il più piccolo intero γ̃ soddisfacente (2).
Si può riscrivere la dusuguaglianza come
χ
γ > 6(1 − )
f
Se χ = 2 o χ = 1, al crescere di f il secondo membro tende al valore 6. Quindi per
χ = 1, f > 6 si ha γ̃ = 6 e per χ = 2, f > 12, γ̃ = 6. È anche immediato vedere che γ̃ = 7
per χ = 0. Se χ < 0, ponendo f = γ + 1 e sostituendo nella disuguaglianza si ottiene
χ
γ > 6(1 −
).
γ +1
ovvero
5
49
γ 2 − 5γ > 6 − 6χ ⇔ (γ − )2 >
− 6χ.
2
4
quindi
√
5
49 − 24χ
γ> +
2
2
e γ̃ è la parte intera superiore √dell’espressione a secondo membro nel caso questa non sia
24χ
un intero, altrimenti γ̃ = 52 + 49 −
+ 1.
2
Figura 13. Nel caso del toro la costante cromatica è in effetti esattamente
uguale a 7 = γ̃, come si evince da questa mappa.
12
LA CARATTERISTICA DI EULERO
Si ottiene cosı̀ per esempio che per la bottiglia di Klein (somma connessa di un toro e
un piano proiettivo, quindi χ = −1) γ̃ = 7 e quindi la costante cromatica della bottiglia
di Klein è al più 7. Per la superficie orientabile di genere 2 (il 2-toro) χ = −2 la costante
cromatica è al più 8 mentre per il 3-toro è al più 9 cosı̀ come quella della superfici non
orientabili di genere 5 e 6 e cosı̀ via.
Vogliamo ora dimostrare che, nel caso di mappe regolari su una sfera o su una porzione
limitata di piano la costante cromatica è in realtà non maggiore di 5.
Teorema 6 (dei cinque colori). Ogni mappa regolare su una sfera o su una porzione
limitata di piano può essere colorata con cinque colori in modo che regioni confinanti
abbiano sempre colori distinti.
Dimostrazione. Procediamo per induzione sul numero di regioni come nel teorema dei sei
colori. Se la mappa ha cinque regioni o meno la tesi è evidente. Supponiamo di aver
dimostrato il teorema per mappe con f − 1 regioni. Abbiamo già provato che ogni mappa
regolare su una superficie con caratteristica di Eulero positiva deve possedere almeno una
regione f ∗ la cui frontiera sia formata al più da cinque archi. Nel caso la frontiera di
tale regione f ∗ sia formata da meno di cinque archi è evidente la possibilità di colorare
la mappa con al più cinque colori distinti. Contraendo infatti a un punto f ∗ si utilizza
l’ipotesi induttiva come fatto in precedenza per mostrare che la mappa cosı̀ ottenuta può
essere colorata con al più cinque colori. Si ripristina poi f ∗ e, avendo la sua frontiera
meno di cinque lati, è sempre possibile scegliere uno dei cinque colori in modo che la tesi
sia soddisfatta. Nel caso la frontiera di f ∗ consista esattamente di cinque archi, bisogna
osservare che (si confronti con la figura 14) necessariamente almeno una coppia di regioni
confinanti con f ∗ non hanno frontiera comune. Se per esempio A e C hanno frontiera
comune, allora B e D necessariamente sono disgiunte e anche B ed E, per cui le cinque
regioni confinanti con f ∗ possono essere colorate scegliendo tra soli quattro colori. Anche
contraendo f ∗ a un punto le considerazioni fatte continuano a valere. Procedendo quindi
come sopra, il teorema è dimostrato.
In effetti è stato dimostrato che la costante cromatica della sfera è 4, ma tale risultato
è decisamente più laborioso da ottenere.
LA CARATTERISTICA DI EULERO
Figura 14
13