Teorema de los cuatro colores

Ejemplo de un mapa de cuatro colores

El teorema de los cuatro colores (tambi??n conocido como el mapa de cuatro colores teorema) se??ala que, dado cualquier plano separado en regiones, tales como un mapa pol??tico de los estados de un pa??s, las regiones pueden ser coloreadas usando no m??s de cuatro colores de tal manera que no hay dos regiones adyacentes reciben el mismo color. Dos regiones se llaman adyacentes s??lo si comparten un segmento de frontera, no s??lo un punto. Cada regi??n debe estar contiguas: es decir, que no puede tener enclaves como algunos pa??ses reales, tales como Angola , Azerbaiy??n , el de Estados Unidos o Rusia .

A menudo es el caso que el uso de s??lo tres colores es inadecuada. Esto ya se aplica al mapa con una regi??n rodeada por otras tres regiones (aunque con un n??mero par de pa??ses que rodean tres colores son suficientes) y no es en absoluto dif??cil probar que cinco colores son suficientes para colorear un mapa.

El teorema de los cuatro colores fue la primera gran teorema no se ha demostrado que utilizar un ordenador, y la prueba no es aceptada por todos los matem??ticos, ya que ser??a inviable para un ser humano para verificar con la mano (ver asistida por ordenador la prueba). En ??ltima instancia, para poder creer la prueba, uno tiene que tener fe en la exactitud de la compilador y hardware de ejecutar el programa utilizado para la prueba.

La percepci??n de falta de elegancia matem??tica por la comunidad matem??tica general fue otro factor, y parafraseando a los comentarios de la ??poca, "una buena prueba matem??tica es como un poema-este es un directorio telef??nico! "

Historia

La conjetura fue propuesto por primera vez en 1852, cuando Francis Guthrie, mientras trata de colorear el mapa de los condados de Inglaterra , se dio cuenta de que se necesitaban s??lo cuatro colores diferentes. En ese momento, el hermano de Guthrie, Fredrick, era un estudiante de Augustus De Morgan en Universidad. Francis pregunt?? con Fredrick respecto a ella, que luego lo llev?? a DeMorgan. (Fredrick Guthrie gradu?? m??s adelante en 1852, y m??s tarde se convirti?? en profesor de matem??ticas en Sud??frica ). Seg??n De Morgan:

Un alumno m??o [Guthrie] me pidi?? hoy a darle una raz??n a un hecho que yo no sab??a era un hecho - y sin embargo no lo hago. ??l dice que si una figura se divide de todos modos y los compartimentos de color diferente para que figuras con cualquier parte de la l??nea l??mite com??n son de color diferente - cuatro colores pueden quer??an, pero no m??s, el siguiente es el caso en el que se quieren cuatro colores. Query puede no una necesidad para cinco o m??s se invent?? ...

La primera referencia publicado es por Arthur Cayley, quien a su vez acredita la conjetura de De Morgan.

Hubo varios intentos fallidos de principios de la prueba de la teorema . Una prueba del teorema fue dada por Alfred Kempe en 1879, que fue ampliamente aclamado; otra prueba fue dada por Peter Guthrie Tait en 1880. No fue sino hasta 1890 que la prueba de Kempe se demostr?? err??nea por Percy Heawood, y 1891 que la prueba de Tait se demostr?? err??nea por Julius Petersen-cada prueba falsa de pie sin respuesta desde hace 11 a??os.

En 1890, adem??s de la exposici??n de la falla en la prueba de Kempe, Heawood demostr?? que todos grafos planos son cinco veros??mil; ver cinco teorema de color.

Los resultados m??s significativos se produjeron mediante croata matem??tico Danilo Blanu??a en la d??cada de 1940 por la b??squeda de un original snark.

Durante la d??cada de 1960 y 1970 alem??n matem??tico Heinrich Heesch desarrollado m??todos de aplicaci??n de la inform??tica en la b??squeda de una prueba.

No fue sino hasta 1976 que la conjetura de los cuatro colores fue finalmente probada por Kenneth Appel y Wolfgang Haken en el Universidad de Illinois. Fueron asistidos en alg??n trabajo algor??tmico por John Koch.

Si la conjetura de los cuatro colores eran falsas, habr??a al menos un mapa con el menor n??mero posible de regiones que requiere de cinco colores. La prueba mostr?? que un contraejemplo tales m??nima no puede existir a trav??s de la utilizaci??n de dos conceptos t??cnicos:

• Un conjunto inevitable contiene regiones de tal manera que cada mapa debe tener al menos una regi??n de esta colecci??n.
• Una configuraci??n reducible es una disposici??n de los pa??ses que no pueden ocurrir en un contraejemplo m??nimo. Si un mapa contiene una configuraci??n reducible, y el resto del mapa puede ser de color con cuatro colores, a continuaci??n, todo el mapa puede ser coloreado con cuatro colores y por lo que este mapa no es m??nima.

El uso de normas y procedimientos matem??ticos basados en las propiedades de configuraciones reducibles (por ejemplo, la m??todo de descarga, anillos, cadenas Kempe, etc.), Appel y Haken encontr?? un conjunto inevitable de configuraciones reducibles, demostrando as?? que no podr??a existir un contraejemplo m??nimo a la conjetura de los cuatro colores. Su prueba reduce la infinidad de posibles mapas de 1936 configuraciones reducibles (m??s tarde reducido a 1476), que tuvo que ser comprobada uno por uno por equipo. Esta parte reducibilidad de la obra fue independiente doble comprobarse con diferentes programas y computadoras. Sin embargo, la parte inevitabilidad de la prueba fue de m??s de 500 p??ginas de venta libre contra-ejemplos-escritas a mano, gran parte de los cuales era el hijo adolescente de Haken Lippold verificaci??n colorantes gr??fico. El programa de ordenador corri?? durante cientos de horas.

Desde la experimentaci??n del teorema, algoritmos eficientes se han encontrado mapas de 4 colorantes que requieren s??lo O (n ²⁾ el tiempo, donde n es el n??mero de v??rtices. En 1996 , Neil Robertson, Daniel P. Sanders, Paul Seymour, y Robin Thomas crearon un algoritmo de tiempo cuadr??tica, utilizando El trabajo de Edward Belaga para mejorar un algoritmo basado en la prueba de cuarto grado Appel y Haken del. Esta nueva prueba es similar a Appel y Haken de pero m??s eficiente, ya que reduce la complejidad del problema y requiere la comprobaci??n s??lo 633 configuraciones reducibles. Tanto las partes inevitabilidad y reducibilidad de esta nueva prueba deben ser ejecutadas por ordenador y no son pr??cticos para comprobar a mano.

En 1980, George Spencer-Brown deposit?? su supuesta prueba del mapa de cuatro colores teorema en el Real Sociedad. La validez de esta prueba, que conforma el Anexo 5 de la traducci??n al alem??n de su libro " Leyes de la Forma "(L??beck 1997), es generalmente dudaban.

En el a??o 2004 Benjamin y Werner Georges Gonthier formaliz?? una demostraci??n del teorema dentro de la Coq asistente de prueba (Gonthier, sf). Esto elimina la necesidad de confiar en los diversos programas de ordenador utilizados para verificar los casos particulares; s??lo es necesario confiar en el kernel Coq.

Tambi??n hay algoritmos eficientes para determinar si 1 o 2 colores bastan para colorear un mapa. La determinaci??n de si 3 colores son suficientes, sin embargo, NP-completo, y por lo tanto es poco probable que un algoritmo r??pido. La determinaci??n de si un general (posiblemente no plana) gr??fico puede ser de 4 de color es igualmente NP-completo.

No por cart??grafos

Aunque el teorema de los cuatro colores fue descubierto en el proceso de colorear un mapa real, rara vez se utiliza en la pr??ctica cartograf??a. Seg??n Kenneth mayo, un historiador matem??tico que estudi?? una muestra de los atlas en la Biblioteca del Congreso, no existe una tendencia a minimizar el n??mero de colores utilizados. Muchos mapas utilizan el color para cosas distintas de las regiones pol??ticas. La mayor??a de los mapas utilizan m??s de cuatro colores, y cuando se utilizan solamente cuatro colores, por lo general el n??mero m??nimo de colores en realidad se necesita es menos de cuatro.

En la mayor??a de los mapas reales existen lagos, que todos deben estar en el mismo color. Este es entonces adicional a cualquier color que se requieren para las regiones pol??ticas. Si los lagos se cuentan como una sola regi??n, el teorema no se aplica. Puede ser aplicado a ??reas de tierra del mapa solo considerando los lagos como no perteneciente a las regiones de mapa, pero en los mapas reales varios no regiones mapa contiguos pueden pertenecer adem??s a un ??nico no conectada regi??n pol??tica y requieren el mismo color (ver m??s abajo ), por lo que, de nuevo el teorema no se aplica.

Los libros de texto sobre la cartograf??a y la historia de la cartograf??a no mencionan el teorema de los cuatro colores, a pesar mapa colorante es un tema de discusi??n. En general, los cart??grafos dicen que est??n m??s preocupados por la coloraci??n de los mapas pol??ticos de una manera equilibrada, por lo que no hay color ??nico domina. Ya sea que se utilizan cuatro, cinco, o m??s colores no es una preocupaci??n primordial.

Declaraci??n formal en la teor??a de grafos

Para declarar formalmente el teorema, es m??s f??cil de reformularla en la teor??a de grafos. A continuaci??n, se??ala que el v??rtices de cada grafo plano puede ser coloreada con un m??ximo de cuatro colores de modo que no hay dos v??rtices adyacentes reciben el mismo color. O "cada grafo plano es de cuatro plausible" para abreviar. Aqu??, cada regi??n del mapa se sustituye por un v??rtice de la gr??fica, y dos v??rtices est??n conectados por una borde si y s??lo si las dos regiones comparten un segmento de borde (no s??lo una esquina).

Refutaciones falsos

Al igual que muchos problemas abiertos famosos de las matem??ticas, el teorema de los cuatro colores ha atra??do a un gran n??mero de falsas pruebas y refutaciones en su larga historia. Algunos, como Kempe de Tait y del mencionado anteriormente, se puso bajo el escrutinio p??blico durante m??s de una d??cada antes de que fueran expuestas. Pero muchos m??s, escrito por los aficionados, nunca fueron publicadas en absoluto.

Este mapa se ha coloreado con cinco colores ...	... Pero es necesario cambiar al menos cuatro de las diez regiones para obtener una coloraci??n con s??lo cuatro colores.

En general, el "contraejemplos" intento m??s sencilla de crear una regi??n que toca todas las dem??s regiones. Esto obliga a las dem??s regiones a ser de color con s??lo tres colores. Debido a que el teorema de los cuatro colores es verdad, esto es siempre posible; sin embargo, porque la persona dibujar el mapa se centra en la regi??n grande, no se dan cuenta de que las regiones restantes pueden de hecho ser coloreados con tres colores.

Este truco se puede generalizar: hay muchos mapas en la que si se seleccionan los colores de algunas regiones de antemano, se hace imposible para colorear las regiones restantes sin exceder de cuatro colores. Un verificador casual del contraejemplo puede no pensar?? en cambiar los colores de estas regiones, por lo que el contraejemplo aparecer?? como si es v??lida.

Quiz??s uno de los efectos que subyace a este error com??n es el hecho de que la restricci??n de color no es transitiva: una regi??n s??lo tiene que ser de color diferente a las regiones lo que toca directamente, no a regiones que tocan regiones que toca. Si esto fuera la restricci??n, grafos planos requerir??an arbitrariamente un gran n??mero de colores.

Otros refutaciones falsas violan los supuestos del teorema de maneras inesperadas, tales como el uso de una regi??n que consiste en m??ltiples partes desconectadas, o no permitir regiones del mismo color se toquen en un punto.

Las generalizaciones

Al unirse las flechas individuales juntas y las flechas dobles juntos, se obtiene un toro con siete regiones mutuamente tocar; por lo tanto, siete colores son necesarios

Esta construcci??n muestra el toro divididas en un m??ximo de siete regiones, cada una de las cuales afecta a todos los dem??s.

Uno puede tambi??n considerar el problema de la coloraci??n sobre superficies que no sean el avi??n . El problema en la esfera o cilindro es equivalente a que en el plano. Por cerrado (orientable o no orientable) superficies con positivo g??nero, el n??mero p m??ximo de colores necesarios depende de la superficie caracter??stica de Euler χ acuerdo con la f??rmula

,

donde los corchetes denotan la ultraperif??ricas la funci??n del suelo. La ??nica excepci??n a la f??rmula es la botella de Klein , que tiene caracter??stica de Euler 0 y requiere 6 colores. Esto fue conocido inicialmente como el Conjetura Heawood y demostrado como El color de mapa Teorema por Gerhard Ringel y JTW Youngs en 1968.

Alternativamente, para una superficie orientable la f??rmula puede ser dada en t??rminos de la g??nero de una superficie, g:

Por ejemplo, el toro tiene caracter??stica de Euler χ = 0 (y g??nero g = 1) y por lo tanto p = 7, por lo que no se requieren m??s de 7 colores para colorear cualquier mapa de un toro.

La Cinta de Moebius tambi??n requiere seis colores.

No hay extensi??n ??til del problema de coloraci??n a las regiones s??lidos tridimensionales. Es trivial para construir un conjunto de n varillas flexibles, por ejemplo, de tal manera que cada varilla toca cada otra varilla. El conjunto requerir??a entonces n colores, o n + 1 si se tiene en cuenta el espacio vac??o que tambi??n toca cada varilla. n puede ser tomado como un entero, tan grande como se desee.

Regiones no contiguas

Ejemplo de un mapa con las regiones no contiguas

En el mundo real, no todos los pa??ses son contiguos (por ejemplo, Alaska como parte de la de Estados Unidos , Najichev??n como parte de Azerbaiy??n , y Kaliningrado como parte de Rusia ). Si el esquema de color elegido requiere que el territorio de un pa??s en particular debe ser del mismo color, cuatro colores pueden no ser suficientes. Por ejemplo, considere un mapa simplificado:

En este mapa, las dos regiones marcadas A pertenecen a un mismo pa??s, y debe ser el mismo color. Este mapa se requiere de cinco colores, ya que las dos regiones A juntos son contiguas a otras cuatro regiones, cada una de las cuales es contigua a todos los dem??s. Si A consisti?? en tres regiones, podr??an ser necesarios seis o m??s colores; uno puede construir mapas que requieren un n??mero arbitrariamente alto de colores.