Teorema de los cuatro colores

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:

Exemplu de mapa coloriáu con cuatro colores

Mapa del mundu coloriáu de verde, naranxa, azul y moráu

Dadu cualesquier mapa xeográficu con rexones continues, este puede ser coloriáu con cuatro colores 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. Una serie de pruebes falses y falsos contraejemplos apaecieron dende'l primer enunciáu del teorema de los cuatro colores en 1852.

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. 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.

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.

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:

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.

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 pa cada rexón y una 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 del grafo. Esti grafo ye 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 de los 4 colores. Si $G\,$ ye un grafo planu, entós $\chi (G)\leq 4$

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 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.

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. 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:

«una bona prueba matemática ye similar a un poema —¡pero esto ye una guía telefónica!».

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 d'un vértiz ye'l númberu de les arestes incidentes. Si v_n ye'l númberu de vértices de grau n, y D ye'l grau máximu d'un vértiz, tiense:

$6v-2a=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.$

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 de los cinco colores. Si $G\,$ ye un grafo planu, entós $\chi (G)\leq 5$ Heawood (1890)

Xeneralizaciones

Xuniendo les fleches simples y les fleches dobles, llógrase un toru con siete rexones colindantes, colo que son necesarios siete colores.

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. Para superficies zarraes (orientables o non orientables) con 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:

$p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,$

onde los paréntesis esternos determinen la función parte entera.

Alternativamente, pa una superficie orientable, la fórmula puede ser dada en términos del xéneru de la superficie, g:

$p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor$ (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 (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. (Weisstein))

El 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. (Wilson, 2002)

Bibliografía

• Gonthier, Georges, «Formal Proof--The Four-Color Theorem», Notices of the American Mathematical Society 55 (11): 1382–1393, http://www.ams.org/notices/200811/tx081101382p.pdf 
• Wilson, Robin, Four Colors Suffice, London: Penguin Books, ISBN 0-691-11533-8 
• Weisstein, Eric W. «Four-Color Theorem» (inglés). MathWorld. Wolfram Research.
• Weisstein, Eric W. «Map coloring» (inglés). MathWorld. Wolfram Research.

Enllaces esternos

• Wikimedia Commons acueye conteníu multimedia sobre Teorema de los cuatro colores.
• Teorema de los cuatro colores (enllaz rotu disponible n'Internet Archive; ver l'historial y la última versión). Artículu divulgativu sobre la hestoria del problema de los cuatro colores.

• Datos: Q184410
• Multimedia: Four-color theorem