Ver la fonte de Teorema de los cuatro colores

[[Ficheru:Four Colour Map Example.svg|thumb|Exemplu de mapa coloriáu con cuatro colores]]
[[Ficheru:World map with four colours.svg|thumb|Mapa del mundu coloriáu de verde, naranxa, azul y moráu]]

En [[teoría de grafos]], el '''teorema de los cuatro colores''' (o teorema de la minimalidad cromática) ye un [[teorema]] sobre la [[coloración de grafos]] qu'establez lo siguiente:
{{teorema
|1= Dadu cualesquier [[mapa]] xeográficu con rexones continues, este puede ser [[coloración de grafos|coloriáu]] con cuatro [[color]]es distintos, de forma que nun queden rexones ''axacentes'' col mesmu color.
}}
Dando por fechu que les rexones axacentes comparten non solo un puntu, sinón tou un segmentu de cantu (frontera) de mancomún.

Trés colores son abondos pa mapes simples, pero en dellos casos ye necesariu un cuartu color adicional, esto ye, cuando una rexón a colorear queda zarrada por un númberu impar de rexones que se toquen formando un ciclu. El [[teorema de los cinco colores]], que la so demostración ye curtia y elemental, establez que cinco colores son abondos pa colorear un mapa y foi probáu nel sieglu XIX por Heawood.<ref>{{Obra citada |last=Thomas|first=Robin |títulu=An Update on the Four-Color Theorem |periodical=Notices of the American Mathematical Society |url = http://www.ams.org/notices/199807/thomas.pdf |añu=1998 |volume=45|pages=848–859|authorlink=Robin Thomas (mathematician) |issue=7}}</ref> Una serie de pruebes falses y falsos [[contraejemplos]] apaecieron dende'l primer enunciáu del teorema de los cuatro colores en [[1852]].

<!-- El teorema de los cuatro colores foi probada en [[1976]] por [[Kenneth Appel]] y [[Wolfgang Haken]]. Foi'l primera gran teorema que se probó usando un ordenador. Enfoque Appel y Haken empezó amosando qu'hai un conxuntu particular de 1.936 mapes, cada unu de los cualos nun pueden ser parte d'un contraejemplo de menor tamañu col teorema de los cuatro colores. Appel y Haken utilizó un programa informáticu de propósitu especial pa confirmar que cada unu d'estos mapes teníu esta propiedá. Adicionalmente, cualquier mapa (independientemente de si ye un contraejemplo o non) tienen de tener una parte que se ve como unu d'estos mapes de 1.936. Amosando esto cientos de páxines riquíes d'analises de la mano. Appel y Haken llegó a la conclusión de que nun esistíen más pequeños contraejemplos porque cualesquier tien de contener, sicasí, nun contienen, unu d'estos mapes de 1936. Esta contradicción significa que nun hai contraejemplos a toos, y que polo tanto'l teorema ye verdaderu. Nun principiu, la so prueba nun foi aceptada por tolos matemáticos porque la prueba asistida por ordenador yera imposible pa un ser humanu pa comprobar a mano ( Swart [[1980]] ). De magar, la prueba ganó amplia aceptación, anque persisten les duldes ( Wilson [[2002]] , 216-222). -->
El ''problema del mapa de cuatro colores'' foi plantegáu, per primer vegada, pol estudiante [[Francis Guthrie]] en 1852, lo que foi comunicáu a [[Augustus de Morgan]].<ref>(n'inglés) [https://books.google.es/books?id=oGuXAkR6tlMC&printsec=frontcover&dq=Four+color+theorem&hl=en&sa=X&ei=8PteUa_DH9GEhQeL_IDgCA&ved=0CCwQ6AEwAA#v=onepage&q=Four%20color%20theorem&f=false Fritsch, Rudolph; Fritsch, Gerda (1998). ''The Four Color Theorem: History, Topological Foundations, and Idea of Proof'', páx. 5. Springer] En Google Books.</ref> La conxetura fíxose famosa cola declaración d'[[Arthur Cayley]], en [[1878]], nel sentíu de que la encetara. Foi resueltu, a mediaos de [[1970]], por [[Kenneth Appel]] y [[Wolfgang Haken]].<ref>(n'inglés) [https://books.google.es/books?id=DZBHGD2sEYwC&printsec=frontcover&dq=Scheinerman&hl=en&sa=X&ei=-fleUf76KomAhQe04oFg&ved=0CCwQ6AEwAA#v=onepage&q=map&f=false Scheinerman, Edward R. (2001) ''Mathematics: A Discrete Introduction'', páx. 332. Cengage Learning] En Google Books. Consultáu'l 5 d'abril de 2013.</ref>

==Formulación precisa del teorema==

De primeres, toles esquines y puntos de mancomún que pertenecen a trés o más países, tienen de ser inoraes. Ensin esta restricción, los mapes estraños (utilizando les rexones del área finita pero perímetru infinitu) pueden riquir más de cuatro colores.
[[Image:Aj-map.png|thumb|Exemplu d'un mapa d'[[Azerbaixán]] con rexones non continues]]
De segundes, pal propósitu del teorema cada "país" tien que ser una rexón a cencielles conexa o continua. Nel mundu real, esto nun ye ciertu (por casu, [[Alaska]] como parte de los [[Estaos Xuníos]], [[Naxçıvan]] como parte d'[[Azerbaixán]], y [[Kaliningráu]] como parte de [[Rusia]] nun son rexones continues). Por cuenta de que el territoriu d'un país en particular tien de ser del mesmu color, si dexárense "países" non continuos, cuatro colores podríen nun ser abondos. Por casu, considérese un mapa simplificáu:
[[Image:4CT Inadequacy Example.svg|center]]
Nesti mapa, les dos rexones A pertenecen a un mesmu país, y poro, tienen de ser del mesmu color. Arriendes d'ello, esti mapa rique cinco colores, yá que les dos rexones A son allegantes coles otres cuatro rexones, y cada una d'estes rexones son allegantes ente sigo. Si hai tres rexones A, entós precísense seis o más colores; pueden construyise mapes que riquen un númberu arbitrariamente alzáu de colores. Un escenariu similar tamién puede dase si'l color azul acutar pa l'agua.
[[Ficheru:Four Colour Planar Graph.svg|400px|thumb|Mapa y [[grafo dual]] acomuñáu]]
Una versión más simple del teorema utiliza la [[teoría de grafos]]. El conxuntu de les rexones d'un mapa puede representase de manera más astracta como un [[grafo]] simple non empobináu acomuñando un [[Vértiz (teoría de grafos)|vértiz]] pa cada rexón y una [[Aresta (teoría de grafos)|aresta]] pa cada par de rexones que comparten un segmentu de cantu. Esta representación del mapa con vértices y arestes ye un [[grafo dual]] y el problema de colorear países camudar pola [[Coloración de grafos|coloración del grafo]]. Esti grafo ye [[Grafo planu|planu]], esto ye, que puede dibuxase nel planu ensin encruz d'arestes por aciu l'allugamientu de cada vértiz nun llugar escoyíu arbitrariamente dientro de la rexón a la que correspuende. Cola terminoloxía de la teoría de grafos, el teorema de cuatro colores establez que:
{{teorema
|1= '''Teorema de los 4 colores'''. Si <math>G \,</math> ye un grafo planu, entós <math>\chi(G) \le 4</math> 
}}
Esto ye, ''los vértices de cada grafo planu pueden ser coloriaos con un máximu de cuatro colores de cuenta que nun esistan dos vértices axacentes col mesmu color''. χ(G) correspuende al [[númberu cromáticu]].

== Historia ==

El teorema de los cuatro colores surdió como conxetura. En 1852, Francis Guthrie yera un estudiante de Augustus De Morgan y formuló esa conxetura, que nun pudo ser probada por Guthrie, nin pol so hermanu Frederick, que fuera tamién estudiante de De Morgan, nin por [[William Rowan Hamilton|''sir'' William Rowan Hamilton]], a quien De Morgan escribiólu formulando la conxetura.

En [[1879]] Alfred Bray Kempe anunció na revista Nature que tenía una demostración pa la conxetura. En [[1890]], Percy John Heawood atopó un error na demostración de Kempe. Heawood nun pudo demostrar que la conxetura nun yera válida, pero siguió trabayando nel coloreo de mapes, pudiendo probar que con cinco colores podíase colorear cualquier mapa.<ref>Paenza, Adrián (2004). Matemática ¿tas ende?, páx. 173 a 177. http://mate.dm.uba.ar/~cepaenza/llibru/matemati4.pdf.</ref>

En [[1976]] la conxetura tuvo demostración, gracies a [[Kenneth Appel]] y [[Wolfgang Haken]], qu'utilizaron un ordenador pa la demostración, lo cual xeneró múltiples discutinios nel ambiente matemático.

=== La polémica demostración ===

El [[teorema]] de cuatro colores foi demostráu cola ayuda d'un [[Ordenador electrónicu|ordenador]]. Sicasí, la demostración nun ye aceptada por tolos matemáticos yá que sería impracticable pol so gran cantidá de detalles, de manera que una persona veríase imposibilitada pa verificalo manualmente. Solo queda aceptar la exactitú del programa, del compilador y del ordenador nel cual executóse la prueba.

Otru aspeutu de la demostración, que puede ser consideráu negativu, ye la so falta d'elegancia. Una crítica que fala sobre la elegancia de la mesma, comentada na dómina de la so publicación, diz: 
{{cita|«una bona prueba matemática ye similar a un [[poema]] —¡pero esto ye una [[guía telefónica]]!».<ref>[https://web.archive.org/web/20090820230437/http://encarta.msn.com/encyclopedia_761578291_12/Mathematics.html Mathematics], Microsoft Encarta Online Encyclopedia, Microsoft Corporation, 2007. (n'inglés)</ref>}}

Na actualidá realizó otra demostración, tamién faciendo usu de cálculos per ordenador, lo cual verifica la prueba orixinal; pero sigue ensin esistir una demostración matemática.

== Resume de les idees de la demostración ==

El siguiente resume ta basáu nel llibru ''Every Planar Map is Four Colorable'' de Appel y Haken publicáu en [[1989]]. Anque la prueba del teorema de los cuatro colores dada por Kempe contenía un fallu, apurrió dalgunes de les ferramientes básiques utilizaes darréu pa demostralo. La esplicación que se da equí reformulóse utilizando términos modernos de la teoría de grafos. 

L'argumentu de Kempe ye'l siguiente. De primeres, si'l grafo tien rexones o cares planes non triangulares, esto ye, nun tienen tres arista como fronteres, pueden amestase arestes al grafo (ensin introducir nuevos vértices) de manera que cada rexón del grafo sía triangular, incluyida la rexón esterior. Si esti [[grafo triangular]] llográu del orixinal almite una coloración con cuatro colores o menos, entós el grafo inicial tamién almite la mesma coloración (o una coloración con menos colores), una y bones la coloración sigue siendo válida si esaníciense les arestes introducíes. Asina que basta demostrar el teorema de los cuatro colores pal casu particular de los grafos triangulares pa probalo a tolos grafos planos, y ensin perda de xeneralidá, suponemos que'l grafo ye triangular. 

Supongamos que ''v'', ''a'', y ''c'' ye'l númberu de vértices, arestes y rexones. Yá que cada rexón ye triangular y cada aresta ye compartida por dos rexones, tenemos que ''2a = 3c''. Esto, xunto cola fórmula del [[teorema de Euler pa poliedros]] (''v - a + c = 2'') puede utilizase pa demostrar que ''6v - 2a = 12''. Agora bien, el [[Grau (teoría de grafos)|grau d'un vértiz]] ye'l númberu de les arestes incidentes. Si ''v<sub>n</sub>'' ye'l númberu de vértices de grau ''n'', y ''D'' ye'l grau máximu d'un vértiz, tiense:
:<math>6v - 2a = 6\sum_{i=1}^D v_i - \sum_{i=1}^D iv_i = \sum_{i=1}^D (6 - i)v_i = 12.</math>
Pero ''12 > 0'', ye un númberu positivu y ''"6 - i ≤ 0"'' pa tou ''"i ≥ 6"'', esto demuestra qu'esiste siquier un vértiz de grau 5 o menos. 

Si esiste un grafo que rique 5 colores, entós esiste un grafo ''minimal'', onde la eliminación de cualesquier vértiz facer cuatro colorable. Llamemos a esti grafo G. El grafo G nun puede tener un vértiz de grau 3 o menos, porque si ''g(v) ≤ 3'', podemos esaniciar ''v de G'', y colorear con cuatro colores el grafo modificáu más pequeñu, y de siguío, añader de nuevu'l vértiz ''v'' y colorearlo con un color distintu al de los sos vecinos.

Kempe tamién demostró que G nun puede tener nengún vértiz de grau 4. Como antes esaníciase'l vértiz ''v'', y cuatro colores de los vértices restantes. Si los cuatro vecinos de ''v'' son de distintos colores, por casu coloráu, verde, azul y mariellu en sentíu horariu, buscamos una ruta alterna de vértices de color coloráu y azul qu'una los vecinos colorao y azul. Tal camín llámase una [[cadena de Kempe]]. Puede haber una cadena de Kempe xuniendo a los vecinos de color coloráu y azul, y puede haber una cadena de Kempe xuniendo a los vecinos verdes y mariellos, pero non dambos, una y bones estos dos caminos necesariamente crúciense, y el vértiz onde s'intercepten nun puede ser coloriáu. Supongamos que se trata a los vecinos coloraes y azules que nun tán encadenaos ente sigo. Esplora tolos vértices coneutaos al vecín coloráu pol colloráu-azul caminos alternos, y depués invertir los colores coloráu y azul en toos estos vértices. La resultancia sigue siendo un válidu de cuatro colores, y agora ''v'' puede amestase de nuevu y de color coloráu.

Esto dexa namái'l casu en que G tien un vértiz de grau 5; pero l'argumentu de Kempe yera defectuosu pa esti casu particular. Heawood notó l'error de Kempe y tamién alvirtió que si se taba satisfechu con probar que namái cinco colores son necesarios, podría usase l'argumentu anterior (camudando'l contraejemplo por unu que rique 6 colores) y usar les cadenes de Kempe nel vértiz de grau 5 pa demostrar el [[teorema de los cinco colores]]:
{{teorema|'''Teorema de los cinco colores'''. Si <math>G \,</math> ye un grafo planu, entós <math>\chi(G) \le 5</math> 
|[[Percy John Heawood|Heawood]] (1890)
}}

== Xeneralizaciones ==

[[Ficheru:Torus with seven colours.svg|thumb|300px|Xuniendo les fleches simples y les fleches dobles, llógrase un toru con siete rexones colindantes, colo que son necesarios siete colores.]]
[[Ficheru:Projection color torus.png|480px|thumb|Esta construcción amuesa un toru estremáu nel máximu de siete rexones, caúna de les cuales toca a les otres.]]

Estudióse tamién el problema de colorear otres superficies que nun sían equivalentes a un [[Planu (xeometría)|planu]]. Para [[Superficie (matemática)#Superficie zarrada|superficies zarraes]] (orientables o non orientables) con [[xéneru (matemátiques)|xéneru positivu]], el númberu máximu de colores ''p'' que se precisen depende de la [[carauterística de Euler]] χ, daos pola siguiente fórmula:

:<math>p=\left\lfloor\frac{7 + \sqrt{49 - 24 \chi}}{2}\right\rfloor,</math>
onde los paréntesis esternos determinen la [[función parte entera]].

Alternativamente, pa una [[Superficie (matemática)#Superficie orientable|superficie orientable]], la fórmula puede ser dada en términos del xéneru de la superficie, ''g'':
::<math>p=\left\lfloor\frac{7 + \sqrt{1 + 48g }}{2}\right\rfloor</math> ([[#Reference-Mathworld-Map_coloring|Weisstein]]).

Esta fórmula, conocida como [[conxetura de Heawood]], foi conxeturada por [[P. J. Heawood]] en 1890 y demostrada pa los casos de superficies orientables (y non orientables) non acutaes por [[Gerhard Ringel]] y [[J. T. W. Youngs]] en [[1968]]. La única esceición a la fórmula ye la [[Botella de Klein]], que tien una carauterística de Euler 0 (d'ende la fórmula da p=7) y rique 6 colores, como lo demostró P. Franklin en [[1934]] ([[#Reference-Mathworld-Map_coloring|Weisstein]]). (Una [[Banda de Möbius]], que la so carauterística de Euler χ = 0, tamién rique 6 colores, pero nesti casu la fórmula nun ye aplicable, yá que ye una superficie acutada. ([[#Reference-Mathworld-Map_coloring|Weisstein]]))

El [[toru (xeometría)|toru]] tien una carauterística de Euler χ = 0 (y xéneru ''g'' = 1) y polo tanto ''p'' = 7, de manera que non más de 7 colores son riquíos pa colorear cualquier mapa sobre un toru. El [[Poliedru de Szilassi]] ye otru exemplu que rique 7 colores.

Nun hai estensión obvia del problema de coloreo de rexones de sólidos tridimensionales. Usando un conxuntu de ''n'' banielles flexibles, unu puede faer que cada baniella toque a caúna de les otres. El conxuntu depués va riquir ''n'' colores, o ''n''+1 si considérase que l'espaciu vacíu tamién toca cada baniella. Pal númberu ''n'' puede tomase un enteru tan grande como se quiera. tales exemplos fueron propuestos por Fredrick Gurthrie en 1880. {{Harv|Wilson|2002}}

== Referencies ==
{{llistaref}}

==Bibliografía==

* {{Obra citada |last=Gonthier |first=Georges |títulu=Formal Proof--The Four-Color Theorem |periodical=Notices of the American Mathematical Society |volume=55 |añu=2008|url=http://www.ams.org/notices/200811/tx081101382p.pdf |issue=11 |pages=1382–1393}}
*{{Obra citada |last=Wilson |first=Robin |authorlink=Robin Wilson (mathematician) |títulu=Four Colors Suffice |place=London |publisher=Penguin Books |añu=2002 |isbn=0-691-11533-8}}
* {{MathWorld|títulu=Four-Color Theorem|urlname=Four-ColorTheorem}}
* {{MathWorld|títulu=Map coloring|urlname=MapColoring}}

== Enllaces esternos ==

{{Commonscat|Four-color theorem}}
* {{Enllaz rotu|1=''Teorema de los cuatro colores'' |2=http://descubriendo.fisica.unlp.edu.ar/afayando/index.php/F%C3%ADsica_y_Matem%C3%A1tica |date=August 2024 |bot=InternetArchiveBot }} Artículu divulgativu sobre la hestoria del problema de los cuatro colores.







{{Tradubot|Teorema de los cuatro colores}}

{{control d'autoridaes}}
[[Categoría:Mapes]]
[[Categoría:Teoremas de teoría de grafos|Cuatro colores]]
[[Categoría:Coloreo de grafos]]
[[Categoría:Grafos planares]]
[[Categoría:Ciencia y teunoloxía de Sudáfrica]]