El Teorema de Cuatro Colores

Source page: people.math.gatech.edu/~thomas/FC/fourcolor.html

Esta página ofrece un breve resumen de una nueva prueba del Teorema de los Cuatro Colores y un algoritmo de cuatro coloración encontrado por  Neil Robertson,  Daniel P. Sanders, Paul Seymour y  Robin Thomas.



Tabla de contenido:

 1. Historia.

 2. ¿Por qué una nueva prueba?

 3. Esquema de la prueba.

 4. Principales características de nuestra prueba.

 5. Configuraciones.

 6. La descarga de reglas.

 7. Punteros.

 8. Un algoritmo cuadrático.

 9. Discusión.

10. Referencias.

Historia.

El problema de los cuatro colores se remonta a 1852, cuando Francis Guthrie, al tratar de colorear el mapa de los condados de Inglaterra advirtió que cuatro colores fueron suficientes. Le pidió a su hermano Federico, si bien era cierto que  cualquier  mapa puede ser coloreado con cuatro colores de tal manera que las regiones adyacentes (es decir, aquellos que comparten un segmento de frontera común, no sólo un punto) reciben diferentes colores. Frederick Guthrie comunica entonces la conjetura de De Morgan. La primera referencia impresa se debe a Cayley en 1878.

Un año más tarde el primer `prueba’ por Kempe apareció; su incorrección fue señalado por Heawood 11 años después. Otra prueba no se debe a Tait en 1880; un hueco en el argumento fue señalado por Petersen en 1891. Ambas pruebas fallidas tenían algún valor, sin embargo. Kempe descubrió lo que se conocía como cadenas Kempe, y Tait encontró una formulación equivalente del color teorema de los cuatro en términos de 3-borde-colorante.

El siguiente gran contribución vino de Birkhoff cuyo trabajo permitió Franklin en 1922 para probar que la conjetura de los cuatro colores es cierto para los mapas con a lo sumo 25 regiones. También fue utilizado por otros matemáticos para hacer diversas formas de avanzar en el problema de los cuatro colores. Hay que mencionar específicamente Heesch que desarrolló los dos ingredientes principales necesarios para la prueba definitiva – reducibilidad y descarga. Aunque el concepto de capacidad de reducción fue estudiado por otros investigadores, así, parece que la idea de la descarga, que es crucial para la parte inevitabilidad de la prueba, se debe a Heesch, y que fue él quien conjeturó que un adecuado desarrollo de este método resolver el problema de los cuatro colores.

Esto fue confirmado por Appel y Haken en 1976, cuando publicaron su prueba del Teorema de los Cuatro Colores  [1,2].

¿Por qué una nueva prueba?

Hay dos razones por las cuales la prueba Appel-Haken no es completamente satisfactoria.

• Parte de la prueba de Appel-Haken usa una computadora, y no puede ser verificada a mano, y

• incluso la parte que supuestamente es comprobable a mano es extraordinariamente complicado y tedioso, y por lo que sabemos, nadie ha verificado en su totalidad.

De hecho, hemos intentado comprobar la prueba de Appel-Haken, pero pronto se rindió. Comprobación de la pieza de la computadora no sólo requiere una gran cantidad de programación, sino también inputing las descripciones de 1476 gráficos, y que no era ni siquiera la parte más controvertida de la prueba.

Decidimos que sería más rentable que trabajar nuestra propia prueba. Así lo hicimos y se nos ocurrió una prueba y un algoritmo que se describe a continuación.

Esquema de la prueba.

La idea básica de la prueba es la misma que Appel y Haken de. Se exhibe un conjunto de 633 “configuraciones”, y probar cada uno de ellos es “reducibles”. Este es un concepto técnico que implica que ninguna configuración con esta propiedad puede aparecer en un contraejemplo mínimo para el Teorema de los Cuatro Colores. También se puede utilizar en un algoritmo, para si una configuración reducible aparece en un gráfico planar G, a continuación, uno puede construir en tiempo constante un gráfico planar menor G ‘tal que cualquier cuatro coloración de G’ se puede convertir en una de cuatro coloración de G en el tiempo lineal.

Se ha sabido desde 1913 que cada contraejemplo mínimo para el Teorema de los Cuatro Colores es una triangulación interna 6-conectado. En la segunda parte de la prueba se demuestra que al menos uno de nuestros 633 configuraciones aparece en cada triangulación plano interno 6-conectada (no necesariamente un contraejemplo mínimo para el 4CT). Esto se llama prueba de inevitabilidad, y utiliza el “método de la descarga”, sugerida por primera Heesch. Aquí nuestro método difiere de la de Appel y Haken.

Principales características de nuestra prueba.

Confirmamos una conjetura de que Heesch para demostrar la inevitabilidad, una configuración reducible se puede encontrar en el segundo entorno de un vértice “sobrecargada”; esta es la forma evitamos problemas de “inmersión” que eran una fuente importante de complicación para los Appel y Haken. Nuestro conjunto inevitable tiene un tamaño de 633 en comparación con el conjunto de 1476 miembro de Appel y Haken, y nuestro método de descarga utiliza sólo 32 reglas de descarga, en lugar de los más de 300 de Appel y Haken. Por último, se obtiene un algoritmo cuadrático a los gráficos de cuatro colores planas (descrito más adelante), una mejora sobre el algoritmo quartic de Appel y Haken.

Configuraciones.

A  cerca de la triangulación  es un gráfico plano despoblado conectado no nulo tal que cada región finita es un triángulo. Una  configuración K consta de un G-cerca de triangulación y un mapa g de V (G) a los enteros con las siguientes propiedades:

1. para cada vértice v, G\v tiene como máximo dos componentes, y si hay dos, entonces el grado de v es g(v)-2,

2. para cada vértice v, si v no es incidente con la región infinita, entonces g(v) es igual al grado de v, y de otra manera g(v) es mayor que el grado de v; y en ambos casos g(v)> 4,

3. K tiene tamaño de anillo por lo menos 2, donde el  anillo de tamaño  de K se define como la suma de g(v)-deg(v)-1, sumado sobre todos los vértices v incidentes con la región infinita tal que G\v está conectado.

Al dibujar imágenes de configuraciones que utilizamos una convención introducida por Heesch. Las formas de vértices indican el valor de g (v) como sigue: Un círculo negro sólido significa g(v)=5, un punto (o lo que aparece en la imagen como símbolo de no en todos) significa g(v)=6, un círculo hueco significa g(v)=7, un cuadrado hueco significa g(v)=8, un triángulo significa g(v)=9, y un pentágono significa g(v)=10. (No necesitamos vértices v con g(v)>11, y sólo un vértice con g(v)=11, para el que no se utiliza ningún símbolo especial.) En la imagen siguiente 17 de nuestros 633 configuraciones reducibles se muestran utilizando la convención indicada. Todo el conjunto se puede ver haciendo clic  aquí. (Nos referimos a (3.2) de nuestro trabajo [7]  para el significado de “bordes gruesos” y “medias bordes” en esas imágenes.)



Cualquier isomorfo de configuración para uno de los  633 configuraciones  expuestas en  [7]  se llama una  buena configuración. Sea T una triangulación. Una configuración K=(G,g) aparece  en T si G es un subgrafo inducido de T, cada región finita de G es una región de g(v) es igual al grado de v en T para cada vértice v de G probamos las dos afirmaciones siguientes.

TEOREMA 1.  Si T es un contraejemplo mínimo para el color teorema de los cuatro, entonces no hay buena configuración aparece en T.

TEOREMA 2.  Por cada triangulación T internamente 6-conectados, algunas buena configuración aparece en T.

A partir de los dos teoremas anteriores se deduce que no existe un contraejemplo mínimo, y por lo que el 4CT es cierto. La primera prueba necesita un ordenador. El segundo se puede comprobar con la mano en unos pocos meses, o, utilizando un ordenador, se puede verificar en unos 20 minutos.

La descarga de reglas.

Sea T una triangulación interna 6-conectado. Inicialmente, cada vértice v se le asigna una carga de 10 (6-deg (v)). Se deduce de la fórmula de Euler que la suma de las cargas de todos los vértices es de 120; en particular, es positivo. Ahora tenemos redistribuir las cargas de acuerdo con las siguientes reglas, de la siguiente manera. Siempre que T tiene un subgrafo isomorfo a uno de los gráficos en la figura siguiente satisfacer las especificaciones de grado (por un vértice v de una regla con un signo menos junto a v esto significa que el grado de la correspondiente vértice de T es como máximo el valor especifica por la forma de v, y de manera análoga para vértices con un signo más al lado de ellos, no se requiere la igualdad para vértices con ninguna señal al lado de ellos) un suplemento de una (dos en el caso de la primera regla) se va a enviar a lo largo de la borde marcado con una flecha.



Este procedimiento define un nuevo conjunto de cargos con la misma suma total. Dado que la suma total es positivo, hay un vértice v en T cuya carga positiva es nueva. Se demuestra que una buena configuración aparece en el segundo entorno de v.

Si el grado de v es a lo sumo 6 o al menos 12, entonces esto se puede ver con bastante facilidad por un argumento directo. Para el resto de casos, sin embargo, las pruebas son mucho más complicadas. Por lo tanto, hemos escrito las pruebas en un lenguaje formal para que puedan ser verificados por un ordenador. Cada paso de estas pruebas es humano verificable, pero las mismas pruebas no son realmente comprobable con la mano, debido a su longitud.

Punteros.

La parte teórica de nuestra prueba se describe en  [7]. Un 10 páginas  encuesta  está disponible en línea. Los datos de la computadora y los programas utilizados para ubicarse en un servidor FTP anónimo, pero que el servidor ha sido eliminado. Los mismos archivos están ahora disponibles en  http://www.math.gatech.edu/~thomas/OLDFTP/four/  y se pueden  ver cómodamente. Un conjunto independiente de los programas fue escrito por  Gasper Fijavz  bajo la guía de  Bojan Mohar.

Un algoritmo cuadrático.

La entrada al algoritmo será un G plano triangulación con n vértices. (Esto es, sin pérdida de generalidad, como cualquier gráfico planar puede ser triangulada en tiempo lineal.) La salida será una coloración de los vértices de G con cuatro colores.

Si G tiene a lo sumo cuatro vértices colorear cada vértice de un color diferente. De lo contrario, si G tiene un vértice x de grado k<5, entonces el circuito de C que lo rodea es un `k-ring’. Ir a la análisis de los anillos k continuación. De lo contrario G tiene grado mínimo de cinco. Para cada vértice calculamos su carga como se explicó anteriormente, y encontramos un vértice v de carga positiva. Se deduce de nuestra demostración del teorema 2 que, o bien una buena configuración aparece en la segunda zona de v (que cuyo caso se puede encontrar en el tiempo lineal), o una k-anillo que viola la definición de 6-conexión interna se puede encontrar en tiempo lineal. En el último caso vamos al análisis de los anillos K por debajo, en el primer caso aplicamos recursión a un cierto gráfico más pequeño. A cuatro coloración de G puede entonces ser construido a partir de cuatro coloración de este gráfico más pequeño en el tiempo lineal.

Dado un anillo k R violar la definición de 6-conexión interna de un procedimiento desarrollado por Birkhoff se puede utilizar. Aplicamos recursión para dos subgraphs cuidadosamente seleccionados de G. A cuatro coloración de G a continuación, se puede construir a partir de los cuatro colorantes de los dos gráficos más pequeños en tiempo lineal.

Discusión.

Hay que mencionar que tanto nuestros programas utilizan sólo la aritmética de enteros, por lo que no necesita preocuparse por los errores de redondeo y peligros similares de la aritmética de punto flotante. Sin embargo, un argumento puede ser hecho que nuestra `prueba’ no es una prueba en el sentido tradicional, ya que contiene pasos que no pueden ser verificadas por los seres humanos. En particular, no hemos demostrado la corrección del compilador hemos compilado nuestros programas en, ni hemos demostrado la infalibilidad del hardware nos encontramos en nuestros programas. Estos tienen que ser tomadas en la fe, y son posiblemente una fuente de error. Sin embargo, desde un punto de vista práctico, la posibilidad de un error del equipo que aparece consistentemente exactamente de la misma manera en todas las carreras de nuestros programas en todos los compiladores bajo todos los sistemas operativos que nuestros programas se ejecutan en es infinitesimalmente pequeña en comparación con la posibilidad de un error humano durante la misma cantidad de caso de cheques. Además de esta posibilidad hipotética de un ordenador dando constantemente una respuesta incorrecta, el resto de nuestra prueba se puede verificar en la misma forma que las demostraciones matemáticas tradicionales. Admitimos, sin embargo, que la verificación de un programa de ordenador es mucho más difícil de lo que realiza una prueba matemática de la misma longitud.

Expresiones de gratitud.

Estamos en deuda con Thomas Fowler, Christopher Carl Heckman y Barrett Walls por su ayuda en la preparación de esta página. Nuestro trabajo ha sido parcialmente financiado por la Fundación Nacional de Ciencia.

Referencias.

  1. K. Appel y W. Haken, Todo mapa plano es de cuatro coloreable. Parte I. descarga, Illinois J. Math. 21 (1977), 429-490.
  2. K. Appel, W. Haken y J. Koch, Cada mapa planar es de cuatro colorable. Parte II. Reducibilidad, Illinois J. Math. 21 (1977), 491-567.
  3. K. Appel y W. Haken, Todo mapa plano es de cuatro coloreable, contemporáneo de Matemáticas. 98 (1989).
  4. GD Birkhoff, la reducibilidad de los mapas, Amer. J. Math. 35 (1913), 114-128.
  5. H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810/a/b, Bibliographisches Institut, Mannheim 1969.
  6. AB Kempe, sobre el problema geográfica de los cuatro colores, Amer. J. Math., 2 (1879), 193-200.
  7. N. Robertson, DP Sanders, PD Seymour y R. Thomas, el teorema de cuatro colores, J. Combin. Ser teoría. B. 70 (1997), 2-44.
  8. N. Robertson, DP Sanders, PD Seymour y R. Thomas,  Una nueva prueba del teorema de cuatro colores,  Electrón. Res. Announc.Amer. Mates. Soc. 2 (1996), 17-25 (electrónico).
  9. TL Saaty, Trece variaciones de colores en la conjetura de los cuatro colores de Guthrie, Amer. Mates. Mensual 79 (1972), 2-43.
  10. TL Saaty y PC Kainen, El problema de los cuatro colores. Asaltos y conquista, Dover Publications, Nueva York 1986.
  11. PG Tait, Nota sobre un teorema de geometría de posición, Trans. Roy. Soc. Edimburgo 29 (1880), 657-660.
  12. H. Whitney y WT Tutte, cadenas Kempe y los cuatro problema de color”, en estudios en el Gráfico Theory, Parte II (ed. DR Fulkerson), Math. Assoc. de América, 1975, 378-413.

13 de noviembre de 1995

 

A través de laberintos para Matemáticas

Original: http://www.math.stonybrook.edu/~tony/mazes/

Este sitio web ha sido incluido en  Intute – Ingeniería de Ciencia y Tecnología  (noviembre de 2007).
 -Esta página en rumano.
Cherez labirinty k matematike  (esta página en Ruso).
Cherez labirinty V matematiky  (otra traducción Rusa).
[Texto de Georgia]  (esta página en Georgiano).
Kroz laberintos matematike  (esta página en Bosnia).
Esta página en  Macedonia .
Skozi Labirinti za matematiko  (esta página en Esloveno).
Esta página en  Ucrania .

    A través de laberintos  a Matemáticas

 


Esta tarde laberinto manuscrito del siglo 12 (13 cm de diámetro) se encuentra en la Bayerische Staatsbibliothek de Múnich (CLM. 14731, Fol 82 v.). El texto anterior del laberinto lee  CUM MINOTHAURO PUGNAT TESEO [EN] LABORINTO . = Teseo lucha con el Minotauro en el laberinto.

Haga clic  para ampliar la imagen.

El diseño del laberinto fue pensado claramente para ser el 12 de nivel  simple, alterna, laberinto de tránsito  con  secuencia de nivel  0 3 2 1 4 7 6 5 8 11 10 9 12, un laberinto común en los manuscritos medievales, pero el nivel 11 fue tomado por la imagen central (rastros de ella son todavía visibles); nivel 8 es llevado directamente al centro; los niveles 9 y 10 están aislados del resto de la ruta, y se han sumado por separado al centro. El significado topológico del laberinto se ha sacrificado para el impacto visual de la composición.


Volver a  página inicial de Tony