Usuari:Habicht/proves/Teorema dels quatre colors
From Wikipedia, the free encyclopedia
A partir de en:Four color theorem
Aquesta és una pàgina de proves de Habicht. Es troba en subpàgines de la mateixa pàgina d'usuari. Serveix per a fer proves o desar provisionalment pàgines que estan sent desenvolupades per l'usuari. No és un article enciclopèdic. També podeu crear la vostra pàgina de proves.
Vegeu Viquipèdia:Sobre les proves per a més informació, i altres subpàgines d'aquest usuari |
En matemàtiques, el teorema dels quatre colors estableix que, en qualsevol separació d'un pla en regions contigües, que produeix una figura anomenada mapa, no es necessiten més de quatre colors per a acolorir les regions del mapa de manera que no hi hagi dues regions adjacents del mateix color. Dues regions s'anomenen adjacents si comparteixen una frontera comuna que no sigui una cantonada, on les cantonades són els punts compartits per tres o més regions.[1] Per exemple, al mapa dels Estats Units d'Amèrica, Utah i Arizona són adjacents, però Utah i Nou Mèxic, que només comparteixen un punt que també pertany a Arizona i Colorado, no ho són.
Tot i la motivació d'acolorir els mapes polítics dels països, la cartografia no està particularment interessada en el teorema. Segons un article de l'historiador de matemàtiques Kenneth May, "són rars els mapes que utilitzen només quatre colors, i dels que ho fan en general només en necessiten tres. Els llibres de cartografia i història de la cartografia no esmenten la propietat dels quatre colors".[2]
En els mapes més simples tres colors són suficients, però en alguns casos es necessita un quart color addicional per a alguns mapes, com ara aquells en els quals una regió està envoltada per un nombre senar d'altres regions que es toquen en un cicle. El teorema dels cinc colors, que té una curta demostració elemental, estableix que cinc colors són suficients per acolorir un mapa i es va demostrar el segle XIX;[3] en canvi, demostrar que quatre colors són suficients va resultar ser significativament més difícil. Hi ha hagut una sèrie de demostracions i contraexemples falses des del primer enunciat del teorema dels quatre colors el 1852.
El teorema dels quatre colors va ser demostrat el 1976 per Kenneth Appel i Wolfgang Haken. Va ser el primer teorema important en ser demostrat mitjançant un ordinador. L'enfocament d'Appel i Haken va començar mostrant que hi ha un conjunt particular de 1.936 mapes, cadascun dels quals no pot formar part d'un contraexemple de mida més petita pel teorema dels quatre colors. Appel i Haken van utilitzar un programa informàtic especialment dissenyat per confirmar que cadascun d'aquests mapes tenien la propietat de poder ser acolorits amb quatre colors. A més, qualsevol mapa (independentment de si es tracta d'un contraexemple o no) ha de tenir una porció que s'assembla a un d'aquests 1.936 mapes. Demostrar això va requerir centenars de pàgines d'anàlisi a mà. Appel i Haken van arribar a la conclusió que no existien contraexemples més petits, ja que qualsevol hauria de contenir, però en canvi no conté, un d'aquests 1.936 mapes. Aquesta contradicció significa que no hi ha en realitat cap contraexemple i que, per tant, el teorema és cert. Inicialment, la seva demostració no va ser acceptada per tots els matemàtics, perquè la demostració assistida per ordinador era impossible de comprovar a mà per un humà.[4] Des de llavors, la prova ha guanyat més acceptació, encara que persisteixen alguns dubtes.[5]
Per dissipar els dubtes restants sobre la demostració d'Appel-Haken, el 1997 Robertson, Sanders, Seymour i Thomas van publicar una demostració més senzilla que utilitzava les mateixes idees i que seguia basant-se en els ordinadors. A més, el 2005 Georges Gonthier va demostrar el teorema utilitzant programari de demostració de teoremes de propòsit general.