Grafi e retiColorazione delle mappe

Abbiamo già usato la teoria dei grafi con alcune mappe. Rimpicciolendo una mappa, si nota che le singole strade e i ponti non sono più visibile, mentre vediamo il contorno di interi Paesi.

Quando si colora una mappa - o qualsiasi altro disegno costituito da regioni distinte - i Paesi adiacenti sono colorati con colori diversi. Potremmo anche voler usare il minor numero possibile di colori. Alcune semplici "mappe", come una scacchiera, richiedono solo due colori (bianco e nero), ma la maggior parte delle mappe complesse ha bisogno di più colori.

Quando si colora la mappa degli Stati Uniti, 50 colori sono ovviamente sufficienti, ma ne potresti usare molti di meno. Prova a colorare le mappe sottostanti con il minor numero di colori possibile:

Stati Uniti

America del Sud

Germania

Inghilterra

Well done!

Numero di colori: 0

Well done!

Numero di colori: 0

Well done!

Numero di colori: 0

Well done!

Numero di colori: 0

Tutte queste mappe possono essere colorate con solo quattro colori diversi, ma come puoi immaginare altre mappe molto complicate hanno bisogno di molti più colori. In effetti, alcune mappe richiedono almeno quattro colori, ogniqualvolta contengano quattro paesi tutti collegati tra loro.

Come in precedenza, possiamo convertire una mappa con Paesi e confini in un grafo planare: ogni Paese diventa ???

e i Paesi che ??? sono connessi da uno spigolo:

Ora vogliamo colorare i vertici di un grafico e fare in modo che due vertici collegati da uno spigolo siano di un colore diverso.

Nel 1852, lo studente di botanica Francis Guthrie

doveva colorare una mappa delle contee in Inghilterra. Osservò che quattro colori erano sufficienti per qualsiasi mappa, ma non era in grado di trovare una prova che funzionasse per tutte le mappe. Questo si è rivelato un problema estremamente difficile ed è diventato noto come il teorema dei quattro colori. Durante i successivi 100 anni, molti matematici hanno pubblicato "prove" sul teorema dei quattro colori, ma in seguito si scoprirono errate. Alcune di queste prove non valide erano così convincenti che ci sono voluti più di 10 anni per trovare gli errori. Per molto tempo, i matematici non sono stati in grado né di dimostrare che quattro colori sono sufficienti, né di trovare una mappa che richiedesse più di quattro colori.

Il problema dei quattro colori è stato risolto nel 1976 da Wolfgang Haken

e Kenneth Appel usando un computer. Ridussero l'infinito numero di possibili mappe in 1936 esempi speciali, che furono controllati da un computer per un totale di oltre 1000 ore.

Il teorema dei quattro colori è il primo teorema matematico ad essere stato dimostrato usando un computer. Ai giorni nostri, ciò è diventato molto più comune e meno controverso. Computer più veloci e un algoritmo più efficiente ci permettono di dimostrare il teorema dei quattro colori su un laptop odierno in poche ore.

Il teorema dei quattro colori funziona solo per le mappe su un piano piatto o una sfera e nel caso in cui tutti i Paesi sono costituiti da un'unica area.

Tuttavia i matematici hanno anche esaminato le mappe degli imperi in cui i Paesi possono essere composti da più componenti disconnesse, e le mappe su pianeti di forma diversa, come un toroide (forma di ciambella). In questi casi potresti aver bisogno di più di quattro colori e le prove diventano ancora più difficili.

Questa mappa su un toroide richiede sette colori.