Archivio mensile:Agosto 2018

La catenaria: una curva ricca di proprietà e che piace alla natura

Catenaria? Che cos’è?! Un insetto? Beh, in realtà è una curva che conosci molto bene e di sicuro ti è capitato più di una volta di scambiare per una parabola. Quando prendi da due estremità una corda con peso uniformemente distribuito, generi proprio una catenaria. Oppure anche quando vedi le catene a penzoloni attaccate a dei paletti vedi delle catenarie, ma anche i ponticelli di legno si dispongono in quel modo. Questa curva geometrica è anche utilizzata in arte ed architettura perché gode di proprietà di stabilità molto interessanti, che  vedremo nei prossimi paragrafi. catenaria

Ti sembrerà strano ma nonostante la catenaria sia una curva poco nota ai più, essa è davvero ovunque e nelle prossime righe cercherò di illustrarti in breve la sua storia con alcune applicazioni e proprietà.

Studiare matematica a volte può risultare noioso. Uno stratagemma che secondo me funziona con chiunque per capire ed interessarsi a ciò che si studia è partire da degli esempi e da delle cose osservabili concretamente nel mondo in cui viviamo (ne ho parlato anche nell’articolo COME STUDIARE LA MATEMATICA). Studiare le proprietà e l’equazione della catenaria è quindi per me un ottimo modo per introdursi alla geometria differenziale delle curve e scoprire come la matematica sia sempre intorno a noi senza che ce ne rendiamo conto.

Un po’ di storia della catenaria

Lo studio della catenaria non è da farsi risalire a tempi molto antichi, almeno a quanto sappiamo. Il primo ad interessarsene fu Galileo Galilei nel 1638. Lui però la confuse con la parabola, infatti si convinse che la forma di una corda appesa per i suoi due estremi sotto la sola forza di gravità, fosse una parabola.

Ecco quello che Salviati afferma nella Seconda giornata del dialogo Discorsi e
dimostrazioni intorno a due nuove scienze (Ecco il link del libro di Galilei : LIBRO):

Salviati: …Ferminsi ad alto due chiodi in un parete, equidistanti all’orizonte e tra di loro lontani il doppio della larghezza del rettangolo su ‘l quale vogliamo notare la semiparabola, e da questi due chiodi penda una catenella sottile, e tanto lunga che la sua sacca si stenda quanta è la lunghezza del prisma: questa catenella si piega in figura parabolica, sì che andando punteggiando sopra ‘l muro la strada che vi fa essa catenella, aremo descritta un’intera parabola, la quale con un  perpendicolo, che penda dal mezo di quei due chiodi, si dividerà in parti eguali….

Il primo a dimostrare che tale curva non fosse una parabola è Joachim Jungius nel 1669. Tale risultato fu affermato e rafforzato dai fratelli Bernoulli, Huygens e Leibniz che nel 1691 dimostrarono anche che tale curva non fosse algebrica (in caso di dubbi si veda: “Curve algebriche: Nozioni di base“) e fu battezzata catenaria da Huygens.

Questa curva e talvolta chiamata funicolare velaria e fu studiata anche da Eulero che nel 1744 dimostrò che la sua rotazione attorno all’asse $x$ del piano cartesiano genera una superficie minima, chiamata catenoide.

Equazione della catenaria e alcuni risultati interessanti

Sulla storia di questa strana curva ci si potrebbe dilungare ancora molto, ma il mio interesse in questo articolo è quello di concentrarci sulle proprietà più caratteristiche e sugli esempi che possiamo trovare tranquillamente uscendo di casa.

La catenaria è una curva trascendente (si veda: Curve trascendenti ) che ammette la seguente equazione:

$y=a \cosh(\frac{x}{a}) = a\big (\frac{\mathrm{e}^{x/a}+\mathrm{e}^{-x/a}}{2}\big)$

dove $a$ è una costante che rappresenta la distanza del punto più basso con il “terreno”. Dall’equazione si nota che la curva non dipende dalla distanza dei punti a cui è appesa la fune. Inoltre la curva è simmetrica rispetto all´asse $y$.

Ruote quadrate

Un problema interessante che coinvolge la geometria e le equazioni differenziali è il problema della ruota quadrata. La domanda è: Quale dovrebbe essere la forma della strada per far si che una ruota quadrata rotoli/scorra regolarmente?

[divider style=”0″]

             

[divider style=”0″]

Si può dimostrare che nel caso di ruote poligonali, la strada deve essere composta da catenarie ribaltate collegate tra loro. Se vuoi vedere come mostrare tale risultato anche solo per il caso di ruote quadrate puoi guardare lo svolgimento dell’esame di maturità (seconda prova) del liceo scientifico un paio di anni fa : PROBLEMA RUOTA QUADRATA. Per un analisi più generale del problema si veda: Roads and Wheels.

Catenaria e trattrice

La curva trattrice, qui sopra raffigurata, gode di una proprietà essenziale: la lunghezza della tangente tra la stessa e l’asse x rimane costante per qualsiasi punto. Bene, una volta introdotta questa particolare curva, vediamo al volo il legame che c’è tra essa e la catenaria 😉

Nella geometria differenziale delle curve, si dice involuta ( o anche evolvente) una curva ottenuta da un’altra curva data seguendo questa procedura:

Si incolla una ipotetica striscia non allungabile ad un punto della curva data. Poi si tira il suo estremo libero e si fa aderire alla curva data la rimanente parte della striscia.

Nel caso della catenaria, l’estremo libero va ad individuare una metà della  curva trattrice se ne si disegna l’involuta 🙂 Legame strano ma interessante, no?!

Dove trovare la catenaria in natura?

Come già detto per i frattali in un precedente articolo (Frattali in natura), anche la catenaria è molto presente in natura, nell’arte, in architettura e molti altri ambiti, soprattutto grazie alle sue proprietà caratteristiche.

Lasciamo quindi ora le proprietà puramente geometriche viste nella precedente sezione per parlare della curva catenaria in natura e nei suoi molteplici utilizzi.

Catenoide e bolle di sapone

Come già citato prima, la rotazione della catenaria attorno all’asse delle ascisse, genera una superficie minima detta catenoide. Tale risultato, oltre che mediante il calcolo differenziale, è mostrabile come nella figura qui in alto mediante le bolle di sapone. Esse tendono ad occupare meno spazio possibile distribuendosi su superfici minime, soprattutto a causa della tensione superficiale. Su questo tema ci sarebbe davvero molto da dire, ma di sicuro dedicherò un apposito articolo all’argomento più avanti.

Per ora ti basti notare che immergendo due strutture a forma circolare (uguale) nell’acqua e sapone si genera proprio il catenoide, che è quindi superficie minima 😉

Archi e catenarie rovesciate

Numerose sono le applicazioni in vari ambiti dell’architettura. La catenaria ha la proprietà di avere in ogni suo punto una distribuzione uniforme del suo peso totale. Essa è stata quindi spesso utilizzata per realizzare manufatti e strutture architettoniche. Le strutture realizzate secondo tale curva subiscono soltanto sforzi a trazione, come le funi di sostegno nei ponti sospesi, oppure, in alternativa, a compressione, quando la struttura realizzata ha la forma di una catenaria rovesciata, come nelle strutture di cupole. (Fonte : https://goo.gl/VRNxBQ ) Ne sono un esempio la cupola della cattedrale di St. Paul a Londra e la Sagrada Familia a Barcellona.

                 

Anche molti ponti sono stati costruiti sulla base della struttura della catenaria, come il famoso ponte di Santa Trinità a Firenze . Infine citiamo il famoso Gateway Arch

dell’architetto finlandese Saarinen, posto nel parco del Jefferson National Expansion Memorial.

Gateway Arch – Catenaria

Ponte santa trinità – Catenaria

Catenaria e gravità

          

Il termine CATENARIA deriva del Latino catenaria ed è per definizione “la curva che descrive la forma di una catena flessibile appesa o di un cavo priva/o di pesi aggiuntivi o esterni”. Tutti i cavi appesi liberi da altri pesi o striscie di materiali vari assumono questa forma. Il requisito affichè essa si formi è che la massa del corpo deve essere distribuita uniformemente nella lunghezza del corpo, ovvero esso deve avere densità uniforme. Inoltre il corpo (cavo o catena che sia) deve essere soggetto alla sola forza di gravità.

Conclusione

La catenaria, come molte altre curve che vedremo magari in futuro, è un esempio lampante di come l’analisi matematica della realtà non sia una perdita di tempo ma piuttosto un mezzo in grado di concederci nuovi e più avanzati strumenti e conoscenze. Spero di averti quantomeno incuriosito e interessato, ho appositamente cercato di usare anche più immagini e contenuti visuali possibili 😉

Se vuoi proseguire nell’approfondimento, qui sotto trovi i contenuti che ho usato per comporre questo articolo e alcune risorse per studiare qualcosa in più, sono sicuro che ti divertirai!

Bibliografia e approfondimenti

Lectures on minimal surfaces in $\mathbb{R}^3$ : PDF

La catenaria – Progetto matematica : ARTICOLO

Mathematics and technology: LIBRO

The catenary – Mathematics all around us : VIDEO 

Una non parabola – La catenaria : PDF

Hyperbolic Functions: Catenary: Formula and Proof : VIDEO

The Catenary: Art, Architecture, History, and Mathematics : PDF

Catenary: Wikipedia

Catenary: Wolfram  MathWorld

Teoria del caos: Introduzione e primi esempi

La teoria del caos è la scienza delle sorprese, dei fenomeni non lineari e imprevedibili. Ci insegna ad aspettarci l’inaspettabile. Mentre la scienza tradizionale ha a che fare con fenomeni supposti prevedibili come la gravità, l’elettricità, o le reazioni chimiche, la teoria del caos tratta situazioni non lineari che sono effettivamente impossibili da prevedere o controllare, come la turbolenza, il tempo meteorologico, il mercato delle azioni e molto altro.

La parola caos deriva dal latino chaos, e indirettamente dal greco χάος (che contiene la stessa base χα- dei verbi χαίνωχάσκω «essere aperto, spalancato»). In matematica e in fisica, pur mantenendo un collegamento metaforico con il suo significato ordinario, il termine ha assunto un’importanza crescente, specialmente nello studio dei sistemi complessi: si dice che un sistema tende al caos quando le sue leggi di evoluzione comportano, dopo un certo caratteristico intervallo di tempo, comportamenti del tutto imprevedibili (senza sapere con esattezza le condizioni iniziali del sistema) e irregolari, mancando qualsiasi forma di correlazione tra stati successivi.

Caos non è Caso

La teoria del caos è un campo di studi relativamente recente e spesso frainteso nell’uso comune.Siamo abituati ad usare la parola caos abbastanza di frequente, chiaramente non con significato matematico. Tuttavia questa varietà di significati porta talvolta a fraintendere il termine nel campo matematico. Ti sarà capitato più volte di dire “La mia scrivania è un caos” volendo dire che “Nella mia scrivania ci sono tante cose messe a caso” o qualcosa di simile. In matematica però Caos e Caso sono due termini che si discostano, e di molto!

Le dinamiche caotiche non hanno necessariamente un carattere casuale/probabilistico nascosto. In questi sistemi se conosciamo l’ESATTA posizione attuale o iniziale, possiamo trarre tutte le informazioni che desideriamo sull’evoluzione futura della dinamica. Il problema non è quindi la casualità della dinamica o della posizione attuale, il problema è alla radice: conoscere la condizione esatta dalla quale il sistema inizia ad evolvere. Nel caso di dinamiche semplici (o meglio, non caotiche), anche conoscendo la condizione iniziale in maniera approssimativa, si possono comunque trarre delle rilevanti considerazioni sull’evoluzione della dinamica. Infatti in questi casi abbiamo una dipendenza continua della dinamica dai dati iniziali, ovvero almeno localmente se partiamo sufficientemente vicini alla condizione iniziale di riferimento, otterremo un comportamento dinamico simile. Nel caso di sistemi dinamici caotici, invece, nel tempo il comportamento relativo a condizioni iniziali approssimativamente simili a quella di nostro interesse sono COMPLETAMENTE IRRILEVANTI.

Come puoi vedere dai due esempi che ho fatto qui sopra, nel sistema caotico può essere che anche se ti avvicini arbitrariamente bene alla condizione iniziale con traiettoria rossa, ottieni sempre dinamiche completamente diverse oppure che variano completamente dopo un certo tempo, il quale non dipende però minimamente con la distanza tra le condizioni iniziali. Mentre nel caso della prima immagine, ovvero dinamica non caotica, hai sempre un certo tempo $T>0$ tale che per $0<t<T$ la distanza tra le due traiettorie è controllata dalla distanza dei punti iniziali. Inoltre la cosa importante è che in questo caso il tempo $T$ è strettamente legato alla distanza tra le due condizioni iniziali, più queste sono vicine, più le due traiettorie saranno simili a lungo, ovvero $T$ sarà grande.

Giusto per fare chiarezza, comunque nella seconda immagine le due traiettorie che ho disegnato non sono soggette al caso, sono loro certamente, sono traiettorie deterministiche 😉

Prima di proseguire ti consiglio un ottimo libro divulgativo se vuoi approfondire questi temi, è stato scritto da Ian Stewart e se intitola Dio gioca a dadi? La nuova matematica del caos, ti assicuro che vale la pena leggerlo 😉

Ecco perché spesso si coinvolge il termine caos deterministico. Partendo da un problema apparentemente semplice, il moto di tre corpi che interagiscono tra loro attraverso la forza di gravità (che tratteremo approfonditamente in un seguente articolo), Poincaré arrivò a descrivere in modo chiaro il fenomeno del caos deterministico, scrivendo nel 1903:

Una causa piccolissima che sfugga alla nostra attenzione determina un effetto considerevole che non possiamo mancare di vedere, e allora diciamo che l’effetto è dovuto al caso. Se conoscessimo esattamente le leggi della natura e la situazione dell’universo all’istante iniziale, potremmo prevedere esattamente la situazione dello stesso universo in un istante successivo. Ma se pure accadesse che le leggi naturali non avessero più alcun segreto per noi, anche in tal caso potremmo conoscere la situazione iniziale solo approssimativamente. Se questo ci permettesse di prevedere la situazione successiva con la stessa approssimazione, non ci occorrerebbe di più e dovremmo dire che il fenomeno è stato previsto. Ma non è sempre così; può accadere che piccole differenze nelle condizioni iniziali ne producano di grandissime nei fenomeni finali. Un piccolo errore nelle prime produce un errore enorme nei secondi. La previsione diviene impossibile

Poincaré

Ah dimenticavo, il primo contributo sostanziale alla teoria del caos fu fornito da Henri Poincaré, su cui ho di recente scritto un articolo biografico in cui analizzo anche i suoi principali riconoscimenti e contributi alla ricerca, lo puoi trovare qui: Henri Poincaré – L’ultimo universalista.

Immagine trovata su un video Youtube: https://www.youtube.com/watch?v=GDp8w19WGUo

Si parla quindi di determinismo nel senso che se sapessimo esattamente il nostro punto di partenza avremmo la certezza della dinamica evolutiva che lo caratterizza, mentre di caos per sottolineare la forte sensibilità ai dati iniziali e all’impossibilità di approssimarli per trarre informazioni rilevanti per la dinamica in analisi.

La teoria del caos ha come oggetto di interesse i sistemi dinamici, ma non tutti. La particolarità dei sistemi che seguono un comportamento caotico è la loro forte sensibilità ai dati iniziali. Ovvero sistemi in cui partendo da due situazioni iniziali di poco diverse, si verifica un’evoluzione nel tempo COMPLETAMENTE diversa.

Per non lasciare troppe idee astratte vagare nell’aria, iniziamo subito con un esempio chiaro da un punto di vista visivo, ma non per questo di semplice analisi matematica (la cui trattazione rimando a un articolo/video futuro), il PENDOLO DOPPIO.

Pendolo doppio – un classico esempio di teoria del caos

Il pendolo lo conosci giusto? Ci sono varie modalità per costruire un pendolo, tutte più o meno vicine alla situazione ideale che di solito si studia sui libri. In quest’ultima si suppone la totale assenza di attrito con l’aria solitamente. Si considera in particolare un punto materiale (massa supposta concentrato in un punto nello spazio) vincolato ad una corda/asta rigida e lasciato muoversi partendo da una condizione inziale, la cui altezza non verrà raggiunta periodicamente ma mai superata.

Se vuoi studiare qualcosina sul pendolo semplice ho scritto un articolo qui sul Blog a riguardo, potrai trovare un’analisi dell’equazione che ne regola la dinamica, il disegno del ritratto di fase e qualche considerazione finale a seguito di questo grafico, in pieno stile sistemi dinamici e analisi qualitativa 😉 , eccolo qui: Pendolo semplice.

Per complicare questo sistema dinamico ci si può muovere in varie direzioni, si può analizzare un pendolo 3-dimensionale in cui la particella non è vincolata a muoversi in sole due direzioni (si veda Pendolo di Foucault) o considerare un pendolo forzato da agenti esterni (si veda Oscillatore armonico forzato), oppure si possono analizzare situazioni a queste simili. Quella che però ci interessa per i nostri scopi è il pendolo doppio.

Questo oggetto si costruisce semplicemente vincolando un’altra asta rigida/corda al punto materiale del pendolo semplice. Ancorando all’estremità di questo nuovo “braccio” una nuova massa puntiforme. Avrai già intuito che in questo prolungamento si può giocare sulla lunghezza del braccio, sulla variazione della massa e così via per ottenere i comportamenti più strani. Però forse non immagini che in realtà non serve nemmeno giocare troppo per ottenere un comportamento strano, caotico in particolare.

Prima di analizzare un attimo l’evoluzione, ti consiglio di guardarti questo video per farti un’idea del fenomeno 😉

Già qui nel video è interessante vedere la particolare evoluzione della dinamica. Ma di per sé non è evidente alcun comportamento caotico in questo video, il caos lo si vede sensibilmente confrontando l’evoluzione di due dinamiche che partono da condizioni iniziali molto vicine. La dinamica in questi due casi (simili inizialmente) è completamente diversa all’avanzare del tempo. Guarda qua per fartene un’idea 😉

Non posso negarti di aver guardato il video 3-4 volte, è davvero spettacolare come fenomeno ma soprattutto contro intuitivo. Noi siamo abituati a pensare a dipendenze continue dai dati iniziali, siamo abituati a pensare che oggetti che seguono le stesse leggi e partono vicini, rimarranno vicini. Il che è esattamente il contrario rispetto al pendolo doppio!

Il fenomeno della caoticità è molto ampio e si può approfondirlo sotto vari aspetti ma per non mettere troppa carne al fuoco chiudiamo l’articolo con un esempietto semplce e numerico di dinamica caotica, per poi salutarci 🙂 .  Intanto spero che l’esempio appena fatto e il confronto tra caos e caso ti siano chiari. In caso di qualsiasi dubbio puoi contattarmi a list@mathone.it oppure lascia pure un commento qui sotto 😉

Un semplice esempio di teoria del caos con la calcolatrice

Prova a calcolare più volte consecutive, sulla tua calcolatrice $f(x) = 2x^2-1$ partendo da due $x$ iniziali molto simili, per esempio $x_1 = 0.54322$ e $x_2 = 0.54321$ e vedrai che dopo una cinquantina di iterazioni otterrai cose completamente diverse. Ecco un esempio molto semplice di caos in una mappa iterativa discreta. Perchè questa differenza? Prova un po’ a pensarci 😉

Ti ricordo che se ti piace guardare video, Mathone ha anche un canale Youtube, lo puoi trovare qui: CANALE

Fonti e approfondimenti

Dio gioca a dadi?  La nuova matematica del caos

La fisica del caos. Dall’effetto farfalla ai frattali

What is Chaos theory?

Sistemi dinamici e caos deterministico

Sistemi Dinamici Caotici – Liceo Locarno

Teoria del caos.pdf – Studio Legale Masciarelli

Teorema dei quattro colori: storia, colorazioni di grafi e applicazioni

Il Teorema dei quattro colori è indubbiamente uno dei più famosi ed affinascinati
teoremi della Teoria dei Grafi. In questo articolo vediamo come è nato questo problema
ed i vari risultati che hanno portato alla dimostrazione del teorema, senza
ovviamente tralasciare il legame con le colorazioni di grafi, molto importanti anche
in virtù delle loro applicazioni. Se invece di leggerti l’articolo preferissi scaricarti il PDF e guardarlo con calma, lo puoi scaricare qui: Teorema quattro colori PDF.

Questo articolo è stato gentilmente scritto da Anita Pasotti,  Prof. Associato presso l’Università degli Studi di Brescia (Dipartimento DICATAM – Sezione di Matematica). Per informazioni, questa è la sua pagina :

 

http://anita-pasotti.unibs.it/

Teorema dei quattro colori. Data una qualsiasi carta geografica politica è
possibile colorare stati adiacenti con colori distinti utilizzando al più quattro colori.

Ad esempio in Figura 1 la cartina degli Stati Uniti d’America è stata colorata
usando esattamente quattro colori. Bisogna precisare che ogni stato deve essere
connesso e che per stati adiacenti si intendono due stati con almeno un segmento
di confine in comune e non solo un punto.

FIGURA 1. Colorazione Stati Uniti d’America

L’origine del problema risale al 1852 quando Francis Guthrie, studente di De
Morgan, colorando la cartina della contee britanniche in modo che stati adiacenti
avessero colori distinti si accorse che erano sufficienti quattro colori. Non riuscendo
a trovare una carta che richiedesse più di quattro colori, Francis iniziò a chiedersi se
fosse vero che OGNI mappa potesse essere colorata utilizzando solo quattro colori.
De Morgan propose la congettura alla London Mathematical Society chiedendo se
qualcuno fosse in grado di risolverla. Moltissimi matematici dedicarono anni della
loro vita allo studio di questo problema. Nonostante per molti anni nessuno riuscì
a provare la congettura, i vari tentativi portarono non solo a molti risultati inerenti
alle colorazioni di grafi, ma contribuirono anche allo sviluppo di altre aree
della Teoria dei Grafi.

La prima pubblicazione inerente all’argomento è di Cayley che nell’articolo “On the colouring of maps” del 1879 spiegò le difficoltà incontrate nel cercare di risolvere tale congettura. Nello stesso anno Alfred Bray Kempe, un avvocato londinese che studiò matematica a Cambridge sotto la guida di Cayley, pubblicò una dimostrazione della congettura che venne riconosciuta valida per ben undici anni, fino a quando, nel 1890, Percy John Heawood, un docente universitario della Durham England, vi trovò un errore. Nel lavoro “Map colouring theorem”, Heawood non solo confutò la dimostrazione di Kempe, ma dimostrò il Teorema dei cinque colori che afferma che ogni mappa può essere colorata usando al più cinque colori. L’errata dimostrazione di Kempe ebbe comunque un importante valore poichè per ottenerla introdusse le cosiddette catene di Kempe che sono state poi utilizzate nella dimostrazione definitiva del teorema.

 

Negli anni a seguire sono stati ottenuti vari risultati parziali da molti matematici. Heesch, ad esempio, sviluppò i concetti di riducibilità e di scaricamento, che si rivelarono essere indispensabili per l’ultima dimostrazione. E’ doveroso osservare che mentre l’idea di riducibilità era già stata studiata da altri ricercatori, quella dello scaricamento è dovuta interamente a Heesch, il quale riteneva che un adeguato sviluppo di questo metodo avrebbe portato alla soluzione del problema.

Ciò fu confermato nel 1977 quando Kenneth Appel e Wolfgang Haken, due matematici dell’Università dell’Illinois, pubblicarono la loro dimostrazione del Teorema dei quattro colori [1], [2]. Questa dimostrazione si basa sulla riduzione del numero infinito di mappe possibili ad un numero finito di configurazioni (per l’esattezza 1476) per le quali la validità del teorema viene verificata caso per caso grazie ad un complesso algoritmo informatico che utilizza proprio le catene di Kempe.

Fondamentale fu l’aiuto di Koch, uno studente di informatica, che migliorò man mano il programma. Il programma definitivo aveva avuto ben 500 variazioni da quello originario e fu eseguito su due macchine diverse con algoritmi indipendenti al fine di ridurre al minimo la possibilità di errore. Per analizzare tutti i casi possibili i computer impiegarono circa 50 giorni e servirono più di 500 pagine per trascrivere a mano tutte le verifiche che costituivano la dimostrazione.

L’utilizzo di algoritmi informatici nella dimostrazione di Appel e Haken scatenò grandi polemiche nel mondo scientifico, tanto che alcuni matematici ne contestarono la validità non solo per l’impossibilità di verifica manuale, ma anche perchè la logica afferma che è impossibile dimostrare la correttezza dell’algoritmo.

Fino ad oggi nell’algoritmo non è stato trovato alcun errore, ad ogni modo anche se
ne viene accettata la validità, la dimostrazione non è di certo considerata elegante a
tal punto da essere stata paragonata ad un elenco telefonico. Nel 1997 N. Robertson,
D.P. Sanders, P.D. Seymour e R. Thomas [5] proposero una dimostrazione al
computer che consiste in una riduzione del numero di configurazioni da 1476 a 633,
ma anche la loro dimostrazione non è verificabile manualmente. Infine, nel 2000,
Ashay Dharwadker [6] propose una nuova dimostrazione del teorema che richiede
l’utilizzo della Teoria dei Gruppi.

 

Abbiamo quindi visto come un problema apparentemente così semplice sia stato
in realtà irrisolto per più di un secolo. Vediamo ora come esso possa essere formulato
in termini di colorazioni di grafi. Per fare ciò ci servono alcune nozioni
di base [3]. Un grafo $G$ è una coppia $(V, S)$ dove $V$ è un insieme di punti detti
vertici ed $S$ è un insieme di coppie non ordinate di punti detti spigoli. Sia
ad esempio $G$ il grafo rappresentato in Figura 2. Si ha $V (G) = \{0, 1, 2, 3, 4\}$ e
$S(G) = \{[0, 1], [0, 2], [0, 3], [1, 2], [2, 3], [3, 4]\}$. Due vertici si dicono adiacenti se c’è lo spigolo che li congiunge. Quindi, nel grafo in Figura 2 il vertice 0 è adiacente ai vertici 1, 2, 3, mentre il vertice 4 è adiacente solo al vertice 3.

 

FIGURA 2. Un esempio di grafo ed una sua 3-colorazione

 

Una colorazione di un grafo è una funzione che associa ad ogni vertice un colore in modo che vertici adiacenti abbiano colori distinti. Con c-colorazione si intende una colorazione che utilizza esattamente $c$ colori distinti. Si dice numero cromatico di un grafo $G$ il minimo $c$ per cui esiste una $c$-colorazione di $G$. Ad esempio il grafo in Figura 2 ha numero cromatico 3, a fianco abbiamo infatti una sua 3-colorazione ed è immediato osservare che una 2-colorazione non esiste.

Piccola parentesi esterna all’articolo originale. Se sei interessato/a ad approfondire la teoria introduttiva ai grafi, qui puoi trovare una bella playlist di video, sono davvero molto chiari 😉 , inoltre avevo scritto un articolo sul problema dei ponti di Konigsberg, lo puoi trovare qui: I 7 ponti di Konigsberg

Per enunciare il Teorema dei quattro colori in termini di colorazioni di grafi basta
osservare che ad ogni mappa geografica può essere associato un grafo nel seguente
modo. Rappresentiamo ogni stato della mappa con un punto in corrispondenza della
propria capitale e uniamo due punti se e solo se le capitali che essi rappresentano
corrispondono a stati adiacenti. In tal modo trasformiamo la carta in un grafo i cui
vertici sono le capitali mentre gli spigoli sono i segmenti congiungenti le capitali di
stati adiacenti. Si può dimostrare che il grafo che si ottiene in tal modo è sempre
planare, cioè si può disegnare in modo che i suoi spigoli si incontrino solo nei vertici.

Risulta quindi evidente che il Teorema dei quattro colori può essere enunciato
nel seguente modo: ogni grafo planare ammette una 4-colorazione.
Il filone delle colorazioni di grafi, che si è sviluppato ovviamente anche grazie
allo studio del problema dei quattro colori, ha svariate applicazioni concrete.

Ricordiamo, ad esempio, quella ai numerosi problemi di schedulazione [4]. In tutti
questi problemi si deve assegnare un dato insieme di compiti a degli spazi temporali,
ma alcune coppie di compiti sono in conflitto, cioè non possono essere assegnate
allo stesso spazio temporale. Per risolvere il problema si costruisce il grafo i cui
vertici rappresentano i compiti e due vertici sono adiacenti solo se rappresentano
una coppia di compiti in conflitto. Il numero cromatico del grafo è esattamente il
tempo ottimale per finire tutti i compiti senza conflitti. I dettagli del problema di
schedulazione definiscono la struttura del grafo, vediamo come tramite un esempio
concreto.

Consideriamo il problema di schedulazione del diario degli esami universitari:
Qual è il minimo numero di giorni necessario per far sostenere ad $n$ studenti
$m$ esami, in maniera tale che nessuno studente debba sostenere due esami lo stesso
giorno? Per rappresentare il problema consideriamo il grafo i cui vertici rappresentano
gli $m$ esami e due vertici sono adiacenti se c’è almeno uno studente che
deve sostenere entrambi gli esami rappresentati da quei due vertici. È immediato
vedere che il numero cromatico del grafo così ottenuto è proprio il minimo numero
di giorni necessari. Altri importanti problemi di schedulazione sono ad esempio
quello dell’assegnazione di aeromobili ai voli o quello dell’allocazione delle ampiezze
di banda alle stazioni radio.

Infine concludiamo osservando che anche molti problemi matematici ben noti,
sia ricreativi che non, possono essere formulati in termini di colorazioni di grafi.
Ad esempio il sudoku può essere visto come il completamento di una 9-colorazione
(ogni numero corrisponde ad un colore) di un assegnato grafo con 81 vertici (ogni
cella corrisponde ad un vertice).

Riferimenti bibliografici

[1] K. Appel e W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977), 429–490.
[2] K. Appel e W. Haken, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977), 491–567.
[3] F. Harary, Graph Theory, Addison-Wesley, Reading MA, 1969.
[4] D´aniel Marx, Graph colouring problems and their applications in scheduling, in Periodica Polytechnica, Electrical Engineering, 48 (2004), 11–16,
[5] N. Robertson, D. P. Sanders, P. D. Seymour e R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B. 70 (1997), 2–44.
[6] A. Dharwadker, A New Proof of the Four Colour Theorem,
http://www.geocities.com/dharwadker/, 2000.