Data una mappa divisa in regioni connesse, quanti colori si possono usare al minimo affinchè nessuna regione confini con altre due dello stesso colore?
4 Congetturò nel 1852 uno studente dell'University College London,
Francis Guthrie.
Inizialmente il problema resta in secondo piano, ma quando diversi matematici di grosso calibro vi si cimentano senza successo esso inizia ad assumere una certa fama all'interno degli ambienti universitari. Si sa che quanto più un problema risulta difficile e complicato da risolvere tanto più i matematici sono attratti da esso.
La dimostrazione (quì i matematici puri storceranno il naso) 'definitiva' arriva, dopo diversi tentativi, solo nel 1977 per opera di Kenneth Appel e Wolfgang Haken.
Un'infinità di casi possibili ridotti ad un numero finito, anche se particolarmente elevato (1936) , di casi particolari per poi provare la congettura su ogni singolo caso tramite un algoritmo informatico.
Una dimostrazione "brute-force", soluzione non elegante ma sicuramente funzionante!
Link su Wikipedia:
https://it.wikipedia.org/wiki/Teorema_dei_quattro_colori
- Approfondimento
Il teorema dei quattro colori fa parte della teoria dei Grafi, argomento relativamente recente della matematica che come avrete già intuito mi affascina non poco per via del suo stretto rapporto con l'informatica.
Esso riguarda il problema della colorazione dei grafi, ovvero dell'assegnare dei colori ai vertici di un grafo in modo tale che due vertici collegati non siano dello stesso colore.
Grafi, nodi, colori... Ma sti matematici di cosa si fanno?! Che applicazioni potrà mai avere sta roba?!
Immaginate di dover creare l'orario scolastico di un liceo.
Decine di professori per altrettante aule, ogni professore deve insegnare per un tot di ore settimanali, ogni aula deve avere un tot di ore di lezione settimanali per ogni materia, ogni giorno ogni aula deve avere al massimo 5/6 ore di lezione.... e qui mi fermo perchè solo per pensare tutte le condizioni da rispettare ci vuole almeno mezza giornata.
Tutto deve incastrarsi alla perfezione ( o quasi) , come faranno mai a realizzare quel orario scolastico?
Per fare ciò si usano dei software dedicati, che creano automaticamente delle configurazioni dell'orario.
Indovinate un pò su cosa sono basati quei software: Sulla teoria dei grafi!
Oppure il Sudoku, tutti conoscono questo 'giochino' che fino a qualche anno fa ( adesso ormai ci sono candy crush et similia.... ) impazzava durante il periodo estivo sotto gli ombrelloni.
Nonostante il sudoku esista fin dal 18° secolo alcune delle domande fondamentali su di esso hanno trovato risposta solo di recente (2007) grazie allo studio tramite la teoria dei grafi!
Adesso mi fermo, credo di aver scritto anche troppo, se continuo rischio di diventare pesante e palloso ahah
Vi lascio alcuni link per approfondire nel caso foste interessati!
-Teorema dei quattro colori - Colorabilità dei grafi - Applicazioni
www.science.unitn.it/probab/Mathmodels/article-quattro_colori.pdf
https://it.wikipedia.org/wiki/Colorazione_dei_grafi
https://it.wikipedia.org/wiki/Numero_cromatico_dei_vertici
-L'orario scolastico e la teoria dei grafi
http://www.diegm.uniud.it/satt/papers/DiSc04b.pdf
-Il Sudoku e la teoria dei grafi
http://www.matematicamente.it/.../il-teorema-del-sudoku/