Teorema dels quatre colors
En teoria de grafos, la teorema dels quatre colors (o teorema de la minimalidad cromàtica) és un teorema sobre la coloració de grafos que establix lo següent:
Assumint que les regions adjacents compartixen no solament un punt, sino tot un segment de vora (frontera) en comuna.
Tres colors són suficients per a mapes simples, pero en alguns casos és necessari un quart color adicional, açò és, quan una regió a colorear queda tancada per un número impar de regions que es toquen formant un cicle. El teorema dels cinc colors, la demostració dels quals és curta i elemental, establix que cinc colors són suficients per a colorear un mapa i va ser provat en el XIX per Heawood.[1] Una série de proves falses i falsos contraeixemples han aparegut des del primer enunciat de la teorema dels quatre colors en 1852.
El problema del mapa de quatre colors va ser plantejat, per primera volta, per l'estudiant Francis Guthrie en 1852, lo que va ser comunicat a Augustus de Morgan.[2] La conjectura es va fer famosa en la declaració d'Arthur Cayley, en 1878, en el sentit de que l'havia abordat. Va ser resolt, a mitan de 1970, per Kenneth Appel i Wolfgang Haken.[3]
La demostració de Appel-Haken consistix en analisar un gran número de configuracions reducibles. Açò va ser millorat en 1997 per Robertson, Sanders, Seymour i Thomas, que varen conseguir reduir el número de tals configuracions a 633, lo que seguix sent un cas d'anàlisis extremadament llarc. En 2005, Georges Gonthier va verificar la teorema utilisant un programa informàtic de demostració de teoremes d'us general.
Formulació precisa de la teorema
En primer lloc, tots els cantons i punts en comú que pertanyen a tres o més països deuen ser ignorades. Sense esta restricció, els mapes estranys (utilisant les regions de l'àrea finita pero perímetro infinit) poden requerir més de quatre colors.
En segon lloc, per al propòsit de la teorema cada "país" té que ser una regió simplement conexa o contínua. En el món real, açò no és cert (per eixemple, Alaska com a part dels Estats Units, Nakhchivan com a part d'Azerbaiyan, Kaliningrado com a part de Rússia o Llivia com a part d'Espanya no són regions contínues). Degut a que el territori d'un país en particular deu ser del mateix color, si es permeteren "països" no continus, quatre colors podrien no ser suficients. Per eixemple, considere's un mapa simplificat:
En este mapa, les dos regions A pertanyen a un mateix país, i per lo tant, deuen ser del mateix color. En conseqüència, este mapa requerix cinc colors, ya que les dos regions A sò contigües en les atres quatre regions, i cada una d'estes regions són contigües entre sí. Si hi ha tres regions A, llavors es necessiten sis o més colors; es poden construir mapes que requerixen un número arbitrariamente elevat de colors. Un escenari similar també es pot donar si el color blau es reserva per a l'aigua.
Una versió més simple de la teorema utilisa la teoria de grafos. El conjunt de les regions d'un mapa es pot representar de manera més abstracta com un grafo simple no dirigit associant un vèrtiç per a cada regió i una aresta per a cada parell de regions que compartixen un segment de vora. Esta representació del mapa en vèrtiços i arestes és un grafo dual i el problema de colorear països es canvia per la coloració del grafo. Este grafo és pla, o siga, que es pot dibuixar en el pla sense creuament d'arestes per mig de la colocació de cada vèrtiç en un lloc elegit arbitrariamente dins de la regió a la que correspon. En la terminologia de la teoria de grafos, la teorema de quatre colors establix que:
És dir, els vèrtiços de cada grafo pla poden ser coloreats en un màxim de quatre colors de modo que no existixquen dos vèrtiços adjacents en el mateix color. χ(G) correspon al número cromàtic.
Història
La teorema dels quatre colors va sorgir com a conjectura. En 1852, Francis Guthrie era un estudiant de Augustus De Morgan i va formular eixa conjectura, que no va poder ser provada per Guthrie, ni pel seu germà Frederick, que havia segut també estudiant de De Morgan, ni per sir William Rowan Hamilton, a qui De Morgan li va escriure formulant la conjectura.
En 1879 Alfred Bray Kempe va anunciar en la revista Nature que tenia una demostració per a la conjectura. En 1890, Percy John Heawood va trobar un error en la demostració de Kempe. Heawood no va poder demostrar que la conjectura no era vàlida, pero va seguir treballant en el coloreo de mapes, podent provar que en cinc colors es podia colorear qualsevol mapa.[4]
En 1976 la conjectura va tindre demostració, gràcies a Kenneth Appel i Wolfgang Haken, que varen utilisar un ordenador per a la demostració, lo que va generar múltiples controvèrsia en l'ambient matemàtic.
La polèmica demostració
El teorema de quatre colors va ser demostrat en l'ajuda d'un ordenador. No obstant, la demostració no és acceptada per tots els matemàtics ya que seria impracticable per la seua gran cantitat de detalls, de manera que una persona es voria impossibilitada per a verificar-ho manualment. Solament queda acceptar l'exactitut del programa, del compilador i del computador en el qual es va eixecutar la prova.
Un atre aspecte de la demostració, que pot ser considerat negatiu, és la seua falta d'elegància. Una crítica que parla sobre l'elegància de la mateixa, comentada en l'época de la seua publicació, diu:
Simplificació i verificació
Des de que es va demostrar la teorema, un nou enfocament ha dut a una demostració més curta i a un algoritme més eficient per als mapes de 4 colors. En 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour i Robin Thomas varen crear un algoritme de temps quadràtic (que requerix només de temps, a on n és el número de vèrtiços), millorant un algoritme de temps cuártico basat en la prova de Appel i Haken[6] La nova prova, basada en les mateixes idees, és similar a la de Appel i Haken pero més eficient perque reduïx la complexitat del problema i requerix comprovar només 633 configuracions reducibles. Tant la part d'inevitabilitat com la de reducibilidad d'esta nova prova deuen ser eixecutades per un ordenador i no és pràctic comprovar-les a mà.[7] En 2001, els mateixos autors varen anunciar una prova alternativa, demostrant la conjectura de la teoria de grafos snark.[8] No obstant, esta prova seguix sense publicar-se.
En 2005, Benjamin Werner i Georges Gonthier varen formalisar una prova de la teorema dins de l'assistent de proves Coq. Açò va eliminar la necessitat de confiar en els diversos programes informàtics utilisats per a verificar casos particulars; només és necessari confiar en el núcleu de Coq.[9]
Resum de les idees de la demostració
El següent resum està basat en el llibre Every Planar Map is Four Colorable de Appel i Haken publicat en 1989. Encara que la prova de la teorema dels quatre colors donada per Kempe contenia un fallo, va proporcionar algunes de les ferramentes bàsiques utilisades posteriorment per a demostrar-ho. L'explicació que es dona ací s'ha reformulat utilisant térmens moderns de la teoria de grafos.
L'argument de Kempe és el següent. En primer lloc, si el grafo té regions o cares planes no triangulars, és dir, no tenen tres arestes com a fronteres, es poden agregar arestes al grafo (sense introduir nous vèrtiços) de manera que cada regió del grafo siga triangular, inclosa la regió exterior. Si este grafo triangular obtingut de l'original admet una coloració en quatre colors o menys, llavors el grafo inicial també admet la mateixa coloració (o una coloració en menys colors), ya que la coloració seguix sent vàlida si s'eliminen les arestes introduïdes. Aixina que basta demostrar la teorema dels quatre colors per al cas particular dels grafos triangulars per a provar-ho a tots els grafos plans, i sense pèrdua de generalitat, suponem que el grafo és triangular.
Supongam que v, a, i c és el número de vèrtiços, arestes i regions. Ya que cada regió és triangular i cada aresta és compartida per dos regions, tenim que 2a = 3c. Açò, junt en la fòrmula del teorema de Euler per a poliedres (v - a + c = 2) es pot utilisar per a demostrar que 6v - 2a = 12. Ara be, el grau d'un vèrtiç és el número de les arestes incidents. Si vn és el número de vèrtiços de grau n, i D és el grau màxim d'un vèrtiç, es té:
Pero 12 > 0, és un número positiu i "6 - i ≤ 0" per a tot "i ≥ 6", açò demostra que existix a lo manco un vèrtiç de grau 5 o menys.
Si existix un grafo que requerix 5 colors, llavors existix un grafo minimal, a on l'eliminació de qualsevol vèrtiç ho fa quatre colorable. Cridem a este grafo G. El grafo G no pot tindre un vèrtiç de grau 3 o menys, perque si g(v) ≤ 3, podem eliminar v de G, i colorear en quatre colors el grafo modificat més menut, i a continuació, afegir de nou el vèrtiç v i colorearlo en un color diferent al dels seus veïns.
Kempe també va demostrar que G no pot tindre cap vèrtiç de grau 4. Com abans s'elimina el vèrtiç v, i quatre colors dels vèrtiços restants. Si els quatre veïns de v són de diferents colors, per eixemple roig, vert, blau i groc en sentit horari, busquem una ruta alterna de vèrtiços de color roig i blau que una els veïns roig i blau. Tal camí es diu una cadena de Kempe. Pot haver una cadena de Kempe unint als veïns de color roig i blau, i pot haver una cadena de Kempe unint als veïns verts i grocs, pero no abdós, ya que estos dos camins necessàriament es creuen, i el vèrtiç a on s'intercepten no pot ser coloreat. Supongam que es tracta als veïns roges i blaus que no estan encadenats entre sí. Explora tots els vèrtiços conectats al veí roig pel roig-blau camins alterns, i després invertir els colors roig i blau en tots estos vèrtiços. El resultat seguix sent un vàlit de quatre colors, i ara v es pot agregar de nou i de color roig.
Açò deixa solament el cas en que G té un vèrtiç de grau 5; pero l'argument de Kempe era defectuós per a este cas particular. Heawood va notar l'error de Kempe i també va advertir que si s'estava satisfet en provar que solament cinc colors són necessaris, es podria usar l'argument anterior (canviant el contraeixemple per un que requerix 6 colors) i usar les cadenes de Kempe en el vèrtiç de grau 5 per a demostrar el teorema dels cinc colors:
Generalisacions
S'ha estudiat també el problema de colorear atres superfícies que no siguen equivalents a un pla. Para superfícies tancades (orientables o no orientables) en gènero positiu, el número màxim de colors p que es necessiten depén de la característica de Euler χ, donats per la següent fòrmula:
a on els paréntesis externs determinen la funció partix sancera.
Alternativament, per a una superfície orientable, la fòrmula pot ser donada en térmens del gènero de la superfície, g:
- (Weisstein).
Esta fòrmula, coneguda com conjectura de Heawood, va ser conjeturada per P. J. Heawood en 1890 i demostrada per als casos de superfícies orientables (i no orientables) no acotades per Gerhard Ringel i J. T. W. Youngs en 1968. L'única excepció a la fòrmula és la Botella de Klein, que té una característica de Euler 0 (d'ahí la fòrmula dona p=7) i requerix 6 colors, com ho va demostrar P. Franklin en 1934 (Weisstein). (Una Banda de Möbius, que la seua característica de Euler χ = 0, també requerix 6 colors, pero en este cas la fòrmula no és aplicable, ya que és una superfície acotada. (Weisstein))
El bou té una característica de Euler χ = 0 (i gènero g = 1) i per lo tant p = 7, de manera que no més de 7 colors són requerits per a colorear qualsevol mapa sobre un bou. El Poliedre de Szilassi és un atre eixemple que requerix 7 colors.
No hi ha extensió òbvia del problema de coloreo de regions de sòlits tridimensionals. Usant un conjunt de n varetes flexibles, un pot fer que cada vareta toque a cada una de les atres. El conjunt després requerirà n colores, o n+1 si es considera que l'espai buit també toca cada vareta. Per al número n pot prendre's un sancer tan gran com es vullga. tals eixemples varen ser proposts per Fredrick Gurthrie en 1880.Wilson (2002)
Falses refutació
La teorema dels quatre colors ha segut famós per atraure un gran número de proves i refutació falses en la seua llarga història. Al principi, The New York Claves es va negar, per política, a informar sobre la prova de Appel-Haken, tement que la prova es mostrara falsa com les anteriors.[10] Algunes supostes proves, com les mencionades de Kempe i Tait, varen estar baix l'escrutini públic durant més d'una década abans de ser refutadas. Pero moltes atres, d'autoria d'aficionats, mai varen aplegar a publicar-se.
Generalment, els contraeixemples més senzills, encara que no vàlits, intenten crear una regió que toque a totes les demés regions. Açò obliga a colorear les regions restants en només tres colors. Com la teorema dels quatre colors és cert, açò sempre és possible; no obstant, com la persona que dibuixa el mapa se centra en la regió gran, no es dona conte de que les regions restants poden colorearse en tres colors.
Este truc pot generalisar-se: hi ha molts mapes en els que, si se seleccionen de bestreta els colors d'algunes regions, resulta impossible colorear les restants sense sobrepassar els quatre colors. Un verificador casual del contraeixemple pot no pensar en canviar els colors d'estes regions, de modo que el contraeixemple apareixerà com a vàlit.
Tal volta un efecte subjacent a este error comú és el fet de que la restricció de color no és transitiva: una regió només té que ser de color diferent de les regions que toca directament, no les regions que toquen les regions que toca. Si esta anara la restricció, els grafos plans requeririen un número arbitrariamente gran de colors.
Atres falses refutació violen els supòsits de la teorema, com l'us d'una regió que consistix en múltiples parts desconectades, o no permetre que les regions del mateix color es toquen en un punt.
Referències
- ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- ↑ (en anglés) Fritsch, Rudolph; Fritsch, Gerda (1998). The Four Color Theorem: History, Topological Foundations, and Idea of Proof, pág. 5. Springer En Google Books.
- ↑ (en anglés) Scheinerman, Edward R. (2001) Mathematics: A Discrete Introduction, pág. 332. Cengage Learning En Google Books. Consultat el 5 d'abril de 2013.
- ↑ Paenza, Adrián (2004). Matemàtica ¿estàs ahí?, pág. 173 a 177. http://mate.dm.uba.ar/cepaenza/llibre/matemati4.pdf.
- ↑ Mathematics, Microsoft Encarta Online Encyclopedia, Microsoft Corporation, 2007. (en anglés)
- ↑ Thomas (1995);Robertson et al. (1996)).
- ↑ (), p. .
- ↑ Thomas (1999);Pegg et al. (2002)).
- ↑ (), p. .
- ↑ (), p. .
Bibliografia
- Erro en la seqüencia d'órdens: no existix el mòdul «Citas». (anglés)
- Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
- Four-Color Theorem en MathWorld. (anglés)
- Map coloring en MathWorld. (anglés)
- Howard Levi, An algebraic reformulation of the four color theorem [1] archivat en Wayback Machine. (anglés), publicat atítulo pòstum per Don Coppersmith, Melvin Fitting i Paul Meyer.
Vore també
Enllaços externs
Wikimedia Commons alberga contingut multimèdia sobre Teorema dels quatre colors.- Teorema dels quatre colors Artícul divulgatiu sobre l'història del problema dels quatre colors.
Referències
- Este artícul conté una traducció derivada de «Teorema de los cuatro colores» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.