Teorema de los cuatro colories

De Wikipedia
Saltar a navegación Saltar a la gueta
Exemplu de mapa coloriáu con cuatro colories
Mapa del mundu coloriáu de verde, naranxa, azul y moráu

En teoría de grafos, el teorema de los cuatro colories (o teorema de la minimalidad cromática) ye un teorema sobre la coloración de grafos qu'establez lo siguiente:

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 colories 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 colories, que la so demostración ye curtia y elemental, establez que cinco colories son abondos pa colorear un mapa y foi probáu nel sieglu XIX por Heawood.[1] Una serie de pruebes falses y falsos contraejemplos apaecieron dende'l primer enunciáu del teorema de los cuatro colories en 1852.

El problema del mapa de cuatro colories foi plantegáu, per primer vegada, pol estudiante Francis Guthrie en 1852, lo que foi comunicáu a Augustus de Morgan.[2] La conxetura fíxose famosa cola declaración de Arthur Cayley, en 1878, nel sentíu de que la encetara. Foi resueltu, a mediaos de 1970, por Kenneth Appel y Wolfgang Haken.[3]

Formulación precisa del teorema[editar | editar la fonte]

De primeres, toles esquines y puntos de mancomún que pertenecen a trés o más países, tienen de ser ignoraes. Ensin esta restricción, los mapes estraños (utilizando les rexones de la área finita pero perímetru infinitu) pueden riquir más de cuatro colories.

Exemplu d'un mapa de Azerbaijan 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, Nakhchivan como parte d'Azerbaixán, y Kaliningrado 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 colories podríen nun ser abondos. Por casu, considérese un mapa simplificáu:

4CT Inadequacy Example.svg

Nesti mapa, los dos rexones A pertenecen a un mesmu país, y poro, tienen de ser del mesmu color. Arriendes d'ello, esti mapa rique cinco colories, cuidao que los dos rexones A son allegantes coles otres cuatro rexones, y cada una d'estes rexones son allegantes ente sigo. Si hai tres región 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 colories establez que:

Teorema de los 4 colores. Si ye un grafo planu, entós

Esto ye, los vértices de cada grafo planu pueden ser coloriaos con un máximu de cuatro colories de cuenta que nun esistan dos vértices axacentes col mesmu color. χ(G) correspuende al númberu cromáticu.

Hestoria[editar | editar la fonte]

El teorema de los cuatro colories 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 erru 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 colories podíase colorear cualquier mapa.[4]

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[editar | editar la fonte]

El teorema de cuatro colories foi demostráu cola ayuda d'un ordenador. Sicasí, la demostración nun ye aceptada por tolos matemáticos cuidao 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 computador 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!».[5]

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[editar | editar la fonte]

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 colories 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 colories 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 colories pal casu particular de los grafos triangulares pa probalo a tolos grafos planos, y ensin perda de xeneralidá, suponemos qu'el grafo ye triangular.

Supongamos que v, a, y c ye'l númberu de vértices, arestes y rexones. Cuidao que cada rexón ye triangular y cada aresta ye compartida por dos rexones, tenemos que 2a = 3c. Esto, xuntu 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 vn ye'l númberu de vértices de grau n, y D ye'l grau máximu d'un vértiz, tiense:

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 colories el grafo modificáu más pequeñu, y de siguío, añedir 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 colories 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. Esquiza tolos vértices conectaos al vecín coloráu pol colloráu-azul caminos alternos, y depués invertir el colores coloráu y azul en toos estos vértices. La resultancia sigue siendo un válidu de cuatro colories, 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'erru de Kempe y tamién alvirtió que si se taba satisfechu con probar que namái cinco colories 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 colories:

Teorema de los cinco colories. Si ye un grafo planu, entós


Heawood (1890)

Xeneralizaciones[editar | editar la fonte]

Xuniendo les fleches simples y les fleches dobles, llógrase un toru con siete región colindantes, colo que son necesarios siete colories.
Esta construcción amuesa un toru estremáu nel máximu de siete región, caúna de les cualos 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 característica de Euler χ, daos pola siguiente fórmula:

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:

(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 caracterí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 característica de Euler χ = 0, tamién rique 6 colores, pero nesti casu la fórmula nun ye aplicable, cuidao que ye una superficie acutada. (Weisstein))

El toru tien una caracterí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)

Referencies[editar | editar la fonte]

  1. Thomas, Robin (1998), «An Update on the Four-Color Theorem», Notices of the American Mathematical Society 45 (7): 848–859, http://www.ams.org/notices/199807/thomas.pdf 
  2. (n'inglés) Fritsch, Rudolph; Fritsch, Gerda (1998). The Four Color Theorem: History, Topological Foundations, and Escurre of Proof, pág. 5. Springer En Google Books.
  3. (n'inglés) Scheinerman, Edward R. (2001) Mathematics: A Discrete Introduction, pág. 332. Cengage Learning En Google Books. Consultáu'l 5 d'abril de 2013.
  4. Paenza, Adrián (2004). Matemática ¿tas ende?, pág. 173 a 177. http://mate.dm.uba.ar/~cepaenza/llibru/matemati4.pdf.
  5. Mathematics, Microsoft Encarta Online Encyclopedia, Microsoft Corporation, 2007. (n'inglés)

Bibliografía[editar | editar la fonte]

Enllaces esternos[editar | editar la fonte]




Teorema de los cuatro colores