b'\n_START_ARTICLE_\nTeorema dei quattro colori\n_START_PARAGRAPH_\nIl teorema dei quattro colori \xc3\xa8 un teorema di matematica che afferma che data una superficie piana divisa in regioni connesse, come ad esempio una carta geografica politica, sono sufficienti quattro colori per colorare ogni regione facendo in modo che regioni adiacenti non abbiano lo stesso colore. Due regioni sono dette adiacenti se hanno almeno una linea di confine in comune. Ciascuna regione deve inoltre occupare un territorio connesso, cio\xc3\xa8 non deve essere formata da due o pi\xc3\xb9 parti sconnesse, ovvero con la presenza di exclavi._NEWLINE_\xc3\x88 immediato trovare mappe per le quali tre soli colori non sono sufficienti. Non \xc3\xa8 eccessivamente difficile dimostrare che ne bastano al pi\xc3\xb9 cinque._NEWLINE_Tuttavia dimostrare che ne siano sufficienti quattro \xc3\xa8 particolarmente complesso, tanto che la dimostrazione di questo teorema ha richiesto, tra l\'altro, un estensivo ricorso al computer, per una delle prime volte nella storia della matematica.\n_START_SECTION_\nStoria\n_START_PARAGRAPH_\nLa congettura venne presentata per la prima volta nel 1852, quando Francis Guthrie, uno studente di Augustus De Morgan, si accorse che per colorare una mappa delle contee britanniche erano sufficienti quattro colori. La prima pubblicazione relativa all\'argomento si deve ad Arthur Cayley._NEWLINE_Negli anni successivi molti matematici tentarono invano di dimostrare il teorema. La prima, acclamata "dimostrazione", a lungo riconosciuta come definitiva, fu formulata nel 1879 da Alfred Kempe; nel 1880 Peter Tait annunci\xc3\xb2 di avere trovato un\'ulteriore dimostrazione del teorema. Nel 1890 Percy Heawood scopr\xc3\xac l\'errore che minava la dimostrazione di Kempe, ben undici anni dopo la sua formulazione; l\'anno successivo, ad opera di Julius Petersen, anche la dimostrazione di Tait fu riconosciuta errata. Confutando la dimostrazione di Kempe, Heawood dimostr\xc3\xb2 tuttavia che cinque colori erano sufficienti per qualsiasi mappa._NEWLINE_La definitiva dimostrazione del teorema per quattro soli colori \xc3\xa8 stata fornita nel 1977 da parte di Kenneth Appel e Wolfgang Haken, due matematici dell\'Universit\xc3\xa0 dell\'Illinois, grazie a un complesso algoritmo informatico._NEWLINE_La dimostrazione si basa sulla riduzione del numero infinito di mappe possibili a 1936 configurazioni (poi ulteriormente ridotte a 1476), per le quali la validit\xc3\xa0 del teorema viene verificata caso per caso dal computer. Qualsiasi mappa pu\xc3\xb2 infatti essere ricondotta a un numero finito, sebbene assai elevato, di topologie "notevoli" tramite operazioni che modificano le relative posizioni delle regioni che la costituiscono, ma non le propriet\xc3\xa0 topologiche della mappa stessa._NEWLINE_Per ridurre al minimo la possibilit\xc3\xa0 di errore, il programma fu eseguito su due diverse macchine con due algoritmi indipendenti; per completare l\'analisi di tutti i casi possibili fu necessario far lavorare i computer per migliaia di ore. Alla fine, servirono pi\xc3\xb9 di 500 pagine per trascrivere a mano tutte le verifiche che costituivano la dimostrazione._NEWLINE_Il rivoluzionario utilizzo di algoritmi informatici per verificare l\'esattezza della congettura scaten\xc3\xb2 grandi polemiche sull\'affidabilit\xc3\xa0 di questi metodi. Il fatto che la dimostrazione fosse basata sull\'analisi di una moltitudine di casi discreti port\xc3\xb2 alcuni matematici a contestarne l\'effettiva validit\xc3\xa0: sia per l\'impraticabilit\xc3\xa0 di una verifica manuale di tutti i casi possibili, sia per la difficolt\xc3\xa0 di avere la certezza che l\'algoritmo fosse implementato correttamente. Ad ogni modo, nonostante le accuse di scarsa "eleganza", nell\'algoritmo non \xc3\xa8 mai stato trovato alcun errore.\n_START_SECTION_\nFormulazione in teoria dei grafi\n_START_PARAGRAPH_\nIl teorema pu\xc3\xb2 essere espresso in forma pi\xc3\xb9 comprensibile sfruttando la teoria dei grafi. In questa formulazione i vertici di ciascun grafo planare possono essere colorati utilizzando al massimo quattro colori, in modo tale che due vertici adiacenti non ricevano mai lo stesso colore. In breve, si pu\xc3\xb2 affermare che "ogni grafo planare \xc3\xa8 4-colorabile". Questa rappresentazione associa ogni regione della mappa a un vertice del grafo; due vertici sono connessi da uno spigolo se e solo se le due regioni corrispondenti hanno un segmento di bordo in comune.\n_START_SECTION_\nGeneralizzazione\n_START_PARAGRAPH_\n\xc3\x88 inoltre possibile considerare il problema della colorazione su una superficie piuttosto che su un piano. Il problema applicato alla sfera \xc3\xa8 equivalente a quello sul piano. Per le superfici chiuse (orientate come il toro o non orientate come il nastro di M\xc3\xb6bius) di genere positivo, il massimo numero di colori necessari dipende dalla caratteristica di Eulero  della superficie, in accordo con la formula:_NEWLINE_dove le parentesi pi\xc3\xb9 esterne stanno a indicare la funzione parte intera. Per esempio, il toro ha caratteristica di Eulero  = 0 e p = 7: saranno pertanto necessari al massimo sette colori per colorare qualsiasi mappa su una superficie toroidale._NEWLINE_La sola eccezione alla formula \xc3\xa8 la Bottiglia di Klein, la quale ha caratteristica di Eulero uguale a 0 e richiede sei colori.'