English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGrafi 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
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
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
Il problema dei quattro colori è stato risolto nel 1976 da
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.
Timbro postale per il Dipartimento di Matematica presso l'Università dell'Illinois Urbana-Champaign, dove Haken e Appel hanno lavorato.
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.