Arrivo con un giorno di ritardo, ma ieri è stato l'Ada Lovelace Day, giornata dedicata alla celebrazione dei successi delle donne nei campi della scienza, della tecnologia, dell'ingegneria e della matematica.
Ricordiamo Ada, la prima programmatrice di computer, con un semplice saluto — ovviamente scritto in Ada.
giovedì 16 ottobre 2014
giovedì 9 ottobre 2014
Il teorema dei quattro cinque colori — la dimostrazione
Dimostriamo il teorema dei cinque colori per induzione. Ovvero: supponiamo che sia possibile colorare come si deve un grafo avente un certo numero di vertici, e facciamo vedere che è possibile colorare anche un grafo avente un vertice in più. Da qui, come in una catena di domino in cui ogni tessera che cade mette in moto una nuova tessera, si deduce che il teorema è vero per ogni grafo.
Quindi: sappiamo che in un qualunque grafo ci deve essere un vertice avente al massimo cinque spigoli che escono da esso. Troviamolo.
Ok, concentriamoci sul vertice blu, immaginiamo che il grafo possa proseguire a partire dai vertici rossi come vuole. Anche se i vertici rossi in questo disegno sono tutti connessi con meno di cinque spigoli, in realtà potrebbero averne molti di più.
Il vertice blu è collegato a meno di cinque vertici, in questo caso quattro.
Bene, se noi rimuoviamo dal grafo il vertice blu, otteniamo un grafo che ha un vertice in meno e, quindi, per ipotesi induttiva, è colorabile con cinque colori. Se aggiungiamo il vertice blu, non ci sono problemi a colorare il tutto: dato che è connesso con solo quattro altri vertici, non sono certamente stati usati tutti i cinque colori. Quindi prendiamo un colore che non abbiamo usato e siamo a posto.
Passiamo al caso difficile: il vertice sul quale abbiamo posto l'attenzione è effettivamente collegato con cinque altri vertici, e abbiamo già usato tutti i cinque colori disponibili.
Scegliamo due colori, per esempio il giallo e il viola, e consideriamo solo i nodi colorati con quei colori, e solo gli spigoli che connettono quei nodi. Può succedere, come in questa figura, che il sottografo contenente solo i due colori sia formato da due o più componenti connesse, separate tra di loro. Ecco qua:
Se le cose stanno così, è facile colorare il grafo con cinque colori: basta invertire i colori di una delle due componenti connesse, e si riesce a liberare un colore da assegnare al vertice nero. Per esempio, se invertiamo i colori della componente in alto, otteniamo questa figura:
Abbiamo liberato il colore viola, che possiamo assegnare al vertice nero, ed ecco fatto.
E se il sottografo che contiene i due colori che abbiamo scelto fosse composto da un'unica componente connessa? Come potremmo fare in questo caso? Vediamo un disegnino:
Se le cose fossero così, dovremmo scegliere altri due colori e ripetere il ragionamento fatto sopra. Domanda: siamo sicuri di trovare una coppia di colori che forma almeno due sottografi sconnessi, come prima? Potrebbe verificarsi il caso in cui ogni coppia di colori che noi scegliamo genera un sottografo avente un'unica componente connessa?
La risposta è no, ma se cercate su internet trovate delle spiegazioni poco convincenti e troppo sbrigative. Dice per esempio wikipedia che se scegliamo altri due colori, per esempio il verde e il blu, allora il sottografo formato solo dai nodi avente quei colori e dagli spigoli che li collegano non può essere composto da un'unica componente connessa, perché si intreccerebbe con il sottografo giallo-viola. Ma non è mica vero, non è difficile immaginare un percorso verde-blu non intrecciato col giallo-viola.
Il fatto è che non è possibile che, comunque noi scegliamo due colori, il sottografo che li contiene sia composto da un'unica componente connessa.
Per dire, se aggiungo un po' di collegamenti posso arrivare a una figura del genere, dove ancora le componenti bicolorate sono tutte connesse:
Posso andare avanti ancora? Posso immaginare che blu e rosso siano collegati tra loro da un'unico cammino bicolorato? Sì, è possibile, ma questo cammino dovrà contenere il nodo verde, oppure tutti gli altri. Se contiene il verde, per esempio, può succedere una cosa del genere:
A questo punto un cammino verde-giallo non potrebbe più essere connesso, perché il verde è all'interno del circuito rosso-blu, mentre il giallo è all'esterno (e questo, attenzione, è il risultato di uno di quei teoremi aventi il rapporto chiarezza enunciato/facilità di dimostrazione elevatissimo: si tratta del teorema della curva di Jordan, che dice che ogni curva chiusa del piano non intrecciata divide il piano stesso in due regioni, una interna e una esterna. Sembra una scemata, ma non è banale per niente).
Quindi, anche in questo caso si riesce a colorare il vertice nero con uno dei cinque colori.
Conclusione: l'induzione funziona, le carte geografiche si possono colorare tutte utilizzando cinque colori al massimo.
Per dimostrare che di colori ne servono quattro servono un computer, tanto tempo a disposizione, e una predisposizione filosofica a fidarsi dell'operato di un programma.
Quindi: sappiamo che in un qualunque grafo ci deve essere un vertice avente al massimo cinque spigoli che escono da esso. Troviamolo.
Ok, concentriamoci sul vertice blu, immaginiamo che il grafo possa proseguire a partire dai vertici rossi come vuole. Anche se i vertici rossi in questo disegno sono tutti connessi con meno di cinque spigoli, in realtà potrebbero averne molti di più.
Il vertice blu è collegato a meno di cinque vertici, in questo caso quattro.
Bene, se noi rimuoviamo dal grafo il vertice blu, otteniamo un grafo che ha un vertice in meno e, quindi, per ipotesi induttiva, è colorabile con cinque colori. Se aggiungiamo il vertice blu, non ci sono problemi a colorare il tutto: dato che è connesso con solo quattro altri vertici, non sono certamente stati usati tutti i cinque colori. Quindi prendiamo un colore che non abbiamo usato e siamo a posto.
Passiamo al caso difficile: il vertice sul quale abbiamo posto l'attenzione è effettivamente collegato con cinque altri vertici, e abbiamo già usato tutti i cinque colori disponibili.
Scegliamo due colori, per esempio il giallo e il viola, e consideriamo solo i nodi colorati con quei colori, e solo gli spigoli che connettono quei nodi. Può succedere, come in questa figura, che il sottografo contenente solo i due colori sia formato da due o più componenti connesse, separate tra di loro. Ecco qua:
Se le cose stanno così, è facile colorare il grafo con cinque colori: basta invertire i colori di una delle due componenti connesse, e si riesce a liberare un colore da assegnare al vertice nero. Per esempio, se invertiamo i colori della componente in alto, otteniamo questa figura:
Abbiamo liberato il colore viola, che possiamo assegnare al vertice nero, ed ecco fatto.
E se il sottografo che contiene i due colori che abbiamo scelto fosse composto da un'unica componente connessa? Come potremmo fare in questo caso? Vediamo un disegnino:
Se le cose fossero così, dovremmo scegliere altri due colori e ripetere il ragionamento fatto sopra. Domanda: siamo sicuri di trovare una coppia di colori che forma almeno due sottografi sconnessi, come prima? Potrebbe verificarsi il caso in cui ogni coppia di colori che noi scegliamo genera un sottografo avente un'unica componente connessa?
La risposta è no, ma se cercate su internet trovate delle spiegazioni poco convincenti e troppo sbrigative. Dice per esempio wikipedia che se scegliamo altri due colori, per esempio il verde e il blu, allora il sottografo formato solo dai nodi avente quei colori e dagli spigoli che li collegano non può essere composto da un'unica componente connessa, perché si intreccerebbe con il sottografo giallo-viola. Ma non è mica vero, non è difficile immaginare un percorso verde-blu non intrecciato col giallo-viola.
Il fatto è che non è possibile che, comunque noi scegliamo due colori, il sottografo che li contiene sia composto da un'unica componente connessa.
Per dire, se aggiungo un po' di collegamenti posso arrivare a una figura del genere, dove ancora le componenti bicolorate sono tutte connesse:
A questo punto un cammino verde-giallo non potrebbe più essere connesso, perché il verde è all'interno del circuito rosso-blu, mentre il giallo è all'esterno (e questo, attenzione, è il risultato di uno di quei teoremi aventi il rapporto chiarezza enunciato/facilità di dimostrazione elevatissimo: si tratta del teorema della curva di Jordan, che dice che ogni curva chiusa del piano non intrecciata divide il piano stesso in due regioni, una interna e una esterna. Sembra una scemata, ma non è banale per niente).
Quindi, anche in questo caso si riesce a colorare il vertice nero con uno dei cinque colori.
Conclusione: l'induzione funziona, le carte geografiche si possono colorare tutte utilizzando cinque colori al massimo.
Per dimostrare che di colori ne servono quattro servono un computer, tanto tempo a disposizione, e una predisposizione filosofica a fidarsi dell'operato di un programma.
mercoledì 8 ottobre 2014
Il teorema dei quattro cinque colori — un errorino nella dimostrazione
Dicevamo che la seconda più bella formula della matematica afferma che Facce più Vertici uguale a Spigoli più 2. Usando le formule: F + V = S + 2.
Ogni faccia di un grafo planare come quelli di cui ci stiamo occupando (cioè quelli che modellizzano una carta geografica, in cui ogni vertice è collegato al più a uno spigolo) è circondata da almeno 3 spigoli. Insomma, non ci occupiamo di grafi di questo tipo:
Siccome le facce sono almeno triangolari, cioè circondate da almeno tre spigoli, allora 3F sarà minore o uguale al numero totale di spigoli presenti nel grafo, moltiplicato per 2 (questo perché ogni spigolo confina con due facce, quindi viene contato due volte). In formule: 3F ≤ 2S.
Facciamo un po' di passaggi banali, come dicono i Veri Matematici.
F + V = S + 2 (formula di Eulero)
3F + 3V = 3S + 6 (moltiplico tutto per 3)
3S = 3F + 3V − 6 (ricavo 3S)
3S ≤ 2S + 3V − 6 (per quanto detto sopra, 3F ≤ 2S)
S ≤ 3V − 6 (sottraggo 2S a destra e a sinistra)
2S ≤ 6V − 12 (moltiplico tutto per 2).
Risultato: il doppio del numero di spigoli nel grafo è minore o uguale di 6V − 12.
Domanda: è possibile che ogni vertice sia connesso a almeno altri sei vertici? Se così fosse, il totale degli spigoli moltiplicati per 2 dovrebbe essere uguale a almeno 6V. Dato che 6V − 12 non può essere uguale a 6V, la risposta alla domanda è no.
Quindi esiste almeno un vertice connesso con altri cinque vertici al massimo.
Nel 1879 il matematico Alfred Kempe annunciò di aver dimostrato il teorema dei quattro colori. Solo undici anni dopo, nel 1890, Percy Heawood si accorse di un errore nella dimostrazione di Kempe. Nel farlo, notò il particolare di cui abbiamo discusso ora (e cioè che deve esistere almeno un vertice dal quale escono al più cinque spigoli) che aprì le porte alla dimostrazione del teorema dei cinque colori. Ovvero: cinque colori sono sufficienti per colorare una carta geografica.
Per dimostrarlo non servono né computer né pagine e pagine di dimostrazioni.
Ogni faccia di un grafo planare come quelli di cui ci stiamo occupando (cioè quelli che modellizzano una carta geografica, in cui ogni vertice è collegato al più a uno spigolo) è circondata da almeno 3 spigoli. Insomma, non ci occupiamo di grafi di questo tipo:
Siccome le facce sono almeno triangolari, cioè circondate da almeno tre spigoli, allora 3F sarà minore o uguale al numero totale di spigoli presenti nel grafo, moltiplicato per 2 (questo perché ogni spigolo confina con due facce, quindi viene contato due volte). In formule: 3F ≤ 2S.
Facciamo un po' di passaggi banali, come dicono i Veri Matematici.
F + V = S + 2 (formula di Eulero)
3F + 3V = 3S + 6 (moltiplico tutto per 3)
3S = 3F + 3V − 6 (ricavo 3S)
3S ≤ 2S + 3V − 6 (per quanto detto sopra, 3F ≤ 2S)
S ≤ 3V − 6 (sottraggo 2S a destra e a sinistra)
2S ≤ 6V − 12 (moltiplico tutto per 2).
Risultato: il doppio del numero di spigoli nel grafo è minore o uguale di 6V − 12.
Domanda: è possibile che ogni vertice sia connesso a almeno altri sei vertici? Se così fosse, il totale degli spigoli moltiplicati per 2 dovrebbe essere uguale a almeno 6V. Dato che 6V − 12 non può essere uguale a 6V, la risposta alla domanda è no.
Quindi esiste almeno un vertice connesso con altri cinque vertici al massimo.
Nel 1879 il matematico Alfred Kempe annunciò di aver dimostrato il teorema dei quattro colori. Solo undici anni dopo, nel 1890, Percy Heawood si accorse di un errore nella dimostrazione di Kempe. Nel farlo, notò il particolare di cui abbiamo discusso ora (e cioè che deve esistere almeno un vertice dal quale escono al più cinque spigoli) che aprì le porte alla dimostrazione del teorema dei cinque colori. Ovvero: cinque colori sono sufficienti per colorare una carta geografica.
Per dimostrarlo non servono né computer né pagine e pagine di dimostrazioni.
martedì 7 ottobre 2014
Il teorema dei quattro cinque colori — grafi planari
Il teorema dei quattro colori è famoso, facile da enunciare, difficilissimo da dimostrare (tant'è che qualcuno ancora discute sulla validità della sua dimostrazione). Dice che sono sufficienti quattro colori per colorare una qualsiasi carta geografica in modo tale che due territori confinanti non siano colorati con lo stesso colore.
Naturalmente i Veri Matematici non dicono così: non parlano di carte geografiche (per le quali sicuramente si riuscirebbe a trovare qualche strana configurazione che nemmeno i cartografi più assatanati avrebbero mai immaginato di vedere), ma parlano di grafi planari.
I grafi planari sono molto semplici da descrivere: sono costituiti da un po' di oggetti (vertici) collegati da un po' di segmenti, anche curvilinei (detti spigoli, o archi). Cose così, insomma:
Alcuni grafi possono essere rappresentati senza intersezioni tra gli spigoli, altri no. Per esempio il grafo completo (cioè con tutti i possibili collegamenti) con 4 elementi è fatto così:
e basta poco per capire che si può evitare l'intersezione tra i due spigoli interni riarrangiando un pochino il disegno:
(si può fare anche lasciando la configurazione dei vertici un pochino più simmetrica, ma il programma che sto usando non lo fa in automatico e non so come fare per fargli fare quello che voglio io, quindi pazienza)
Esistono grafi non planari, cioè che non possono in nessun modo essere rappresentati sul piano senza intersezioni tra gli spigoli. Un teorema importante di teoria dei grafi (teorema di Kuratowski) afferma che se un grafo contiene almeno un sottografo omeomorfo (cioè avente la stessa forma) a uno dei due disegnati qua sotto, allora non è planare.
Questo qui sopra è il grafo completo con 5 vertici (per gli amici, K5).
E quest'altro è il famoso grafo relativo al giochino delle tre case che devono essere raggiunte dai tre fornitori di servizi (acqua, luce e gas, per esempio). Sono entrambi non planari, naturalmente.
Quindi, riassumendo, le carte geografiche di cui si occupa il teorema dei quattro colori sono grafi
E per questo tipo di grafi è valida la seconda più bella formula della matematica, ovvero Facce più Vertici = Spigoli più 2. Dove con facce intendiamo le regioni delimitate dai bordi, compresa quella esterna che ha estensione infinita.
Dopo tutte queste belle definizioni, e grazie anche a Eulero, dimostrare il teorema dei quattro colori dovrebbe essere molto facile.
Naturalmente i Veri Matematici non dicono così: non parlano di carte geografiche (per le quali sicuramente si riuscirebbe a trovare qualche strana configurazione che nemmeno i cartografi più assatanati avrebbero mai immaginato di vedere), ma parlano di grafi planari.
I grafi planari sono molto semplici da descrivere: sono costituiti da un po' di oggetti (vertici) collegati da un po' di segmenti, anche curvilinei (detti spigoli, o archi). Cose così, insomma:
Alcuni grafi possono essere rappresentati senza intersezioni tra gli spigoli, altri no. Per esempio il grafo completo (cioè con tutti i possibili collegamenti) con 4 elementi è fatto così:
e basta poco per capire che si può evitare l'intersezione tra i due spigoli interni riarrangiando un pochino il disegno:
(si può fare anche lasciando la configurazione dei vertici un pochino più simmetrica, ma il programma che sto usando non lo fa in automatico e non so come fare per fargli fare quello che voglio io, quindi pazienza)
Esistono grafi non planari, cioè che non possono in nessun modo essere rappresentati sul piano senza intersezioni tra gli spigoli. Un teorema importante di teoria dei grafi (teorema di Kuratowski) afferma che se un grafo contiene almeno un sottografo omeomorfo (cioè avente la stessa forma) a uno dei due disegnati qua sotto, allora non è planare.
Questo qui sopra è il grafo completo con 5 vertici (per gli amici, K5).
E quest'altro è il famoso grafo relativo al giochino delle tre case che devono essere raggiunte dai tre fornitori di servizi (acqua, luce e gas, per esempio). Sono entrambi non planari, naturalmente.
Quindi, riassumendo, le carte geografiche di cui si occupa il teorema dei quattro colori sono grafi
- planari,
- connessi (una carta geografica potrebbe avere due continenti disconnessi, separati da un oceano, ma questo non ci dà fastidio: il nostro problema è colorare un continente alla volta),
- semplici, cioè tali che due vertici sono connessi da al massimo un solo spigolo (non ha senso dire che i due stati A e B confinano due o più volte, insomma).
E per questo tipo di grafi è valida la seconda più bella formula della matematica, ovvero Facce più Vertici = Spigoli più 2. Dove con facce intendiamo le regioni delimitate dai bordi, compresa quella esterna che ha estensione infinita.
Dopo tutte queste belle definizioni, e grazie anche a Eulero, dimostrare il teorema dei quattro colori dovrebbe essere molto facile.
Iscriviti a:
Post (Atom)