Teorema de los cuatro colores

El teorema de los cuatro colores establece que cualquier mapa ubicado en un plano o en una esfera se puede colorear con un máximo de cuatro colores diferentes (pinturas), de modo que dos áreas cualesquiera con un segmento límite común tengan un color diferente. Al mismo tiempo, las áreas deben estar conectadas [1] (es decir, el área no puede constar de dos o más "piezas" separadas), y el borde no debe ser un punto (en un punto, tantas áreas como desee). puedan tocar con sus esquinas, incluidas las pintadas del mismo color).

En 1852, Francis Guthrie , mientras compilaba un mapa de los condados de Inglaterra, notó que cuatro colores eran suficientes para tal propósito. Su hermano Frederick informó esta observación al famoso matemático Augustus de Morgan , quien se lo contó a la comunidad matemática. La formulación exacta de la hipótesis fue publicada por Arthur Cayley (1878) [2] . Tomó mucho tiempo probar el teorema. Se hicieron muchos intentos tanto para probar como para refutar, y este problema se denominó el problema de los cuatro colores [3] .

Para mapas simples, tres colores son suficientes y se requiere un cuarto color, por ejemplo, cuando hay un área rodeada por un número impar de otras que se tocan, formando un ciclo. El teorema de los cinco colores, que establece que cinco colores son suficientes, tuvo una demostración breve y sencilla y fue probado a finales del siglo XIX, pero la demostración del teorema para el caso de cuatro colores encontró importantes dificultades.

El teorema de los cuatro colores fue probado en 1976 por Kenneth Appel y Wolfgang Haken en la Universidad de Illinois . Fue el primer teorema matemático importante en ser probado por una computadora. El primer paso de la prueba fue demostrar la existencia de cierto juego de cartas de 1936, ninguna de las cuales podía contener una carta más pequeña que refutara el teorema. Los autores usaron un programa de computadora especial para probar esta propiedad para cada una de las tarjetas de 1936. La prueba de este hecho tomó cientos de páginas. Después de eso, Appel y Haken llegaron a la conclusión de que no existe el contraejemplo más pequeño del teorema, porque de lo contrario tendría que contener una de estas tarjetas de 1936, lo cual no es así. Esta contradicción dice que no hay ningún contraejemplo en absoluto.

Inicialmente, la prueba no fue aceptada por todos los matemáticos, ya que no se puede verificar a mano. Posteriormente ganó mayor aceptación, aunque algunos tuvieron dudas durante mucho tiempo. Para disipar cualquier duda que pudiera quedar, en 1997 Robertson, Sanders, Seymour y Thomas publicaron una prueba más simple utilizando ideas similares, pero todavía por computadora. Además, en 2005, la prueba fue realizada por Georges Gonteer utilizando un software especializado ( Coq v7.3.1) [4] .

Formulaciones equivalentes

En teoría de grafos, el enunciado del teorema de los cuatro colores tiene las siguientes formulaciones:

• El número cromático de un grafo plano no excede de 4 [5] .
• Los bordes de una triangulación arbitraria de una esfera se pueden colorear en tres colores para que todos los lados de cada triángulo se coloreen en diferentes colores. [6]

Se conocen muchas más formulaciones equivalentes [5] .

Intentos históricos de prueba

Los intentos de prueba más famosos son:

• Alfred Campe propuso una prueba en 1879 [7] , fue refutada en 1890, pero sobre la base de sus ideas fue posible probar que cualquier mapa puede ser coloreado en 5 colores [3] .
• Peter Tait propuso otra prueba en 1880 [3] [8] y fue refutada en 1891.
• Maliev M. El problema de los cuatro colores , 1914.

Variaciones y generalizaciones

Otras superficies

Problemas similares para otras superficies ( toroide , botella de Klein , etc.) resultaron ser mucho más simples. Para todas las superficies cerradas, a excepción de la esfera (y su plano y cilindro equivalentes) y la botella de Klein , el número requerido de colores se puede calcular a partir de su género utilizando la siguiente fórmula, propuesta en 1890 por Percy John Heawood : [9]

El límite superior se obtiene de manera bastante simple, lo demostró el propio Heawood (para una esfera, la fórmula da la respuesta correcta: 4, pero la prueba de Heawood no se aplica a ella). La inferior se prueba empotrando el gráfico completo en la superficie correspondiente; la prueba fue construida en 1952-1968 por un grupo de matemáticos, el último paso fue realizado por Gerhard Ringel y John Youngs . [10] [11] [12]

Para la tira de Möbius (así como para el plano proyectivo ) se requieren 6 colores. Para superficies de una cara del género , [11]

Para una botella de Klein (género ), el número es 6 (y no 7, según la fórmula); esto fue demostrado por P. Franklin en 1934. [13]

Mapa de la isla

Del teorema de los cuatro colores se deduce que un mapa de una isla en la que cada país tiene acceso al mar se puede colorear con 3 colores. Esta afirmación, sin embargo, también tiene una prueba elemental.

Problema del imperio

Percy John Heawood consideró un problema similar para los mapas con imperios coloniales (es decir, con países que constan de varias "piezas" separadas en el mapa, cuyo número es m ) . Cuando responda . La cota superior se obtiene de forma bastante sencilla; fue demostrada por el mismo Heawood. La inferior se prueba empotrando el gráfico completo en la superficie correspondiente; la prueba la dan Gerhard Ringel y Brad Jackson. [catorce]

Queda abierta la variante del problema de los imperios con colonias en otros planetas. Por ejemplo, si todos los países de la Tierra tienen una colonia en la Luna, solo se conocen estimaciones

Dimensiones superiores

En dimensiones superiores , no existe una generalización razonable del problema, ya que es fácil generar un mapa tridimensional con un número arbitrario de áreas que se tocan entre sí. .

El juego de los "cuatro colores"

Stephen Barr propuso un juego de lógica en papel para dos jugadores llamado "Cuatro colores". En palabras de Martin Gardner  , “No conozco mejor manera de entender las dificultades que implica resolver el problema de los cuatro colores que simplemente jugando a este curioso juego” [15] .

Este juego requiere cuatro lápices de colores. El primer jugador comienza el juego dibujando un área vacía arbitraria. El segundo jugador lo pinta con cualquiera de los cuatro colores y a su vez dibuja su área vacía. El primer jugador pinta el área del segundo jugador y agrega una nueva área, y así sucesivamente: cada jugador pinta el área del oponente y agrega la suya. En este caso, las áreas que tienen un borde común deben pintarse en diferentes colores. Pierde el que en su turno se vea obligado a tomar el quinto color.

En este juego, la pérdida de uno de los jugadores no es en absoluto una prueba de la incorrección del teorema (cuatro colores no fueron suficientes), sino solo una ilustración del hecho de que las condiciones del juego y los teoremas son muy diferentes. . Para verificar la exactitud del teorema para el mapa obtenido en el juego, debe verificar la conectividad de las áreas dibujadas y, después de eliminar los colores, averiguar si es posible arreglárselas con solo cuatro colores para pintar el resultado. mapa (el teorema establece que es posible).

También existen las siguientes variaciones del juego:

1. El mapa se divide aleatoriamente en áreas de varios tamaños. En cada movimiento, el jugador que pinta el área cambia y, en estricta secuencia, cambia el color. Así, cada jugador pinta la carta con sólo dos colores. El jugador pierde un turno si no puede pintar un área para que el color de las áreas adyacentes sea diferente. El juego termina cuando ninguno de los jugadores puede hacer más movimientos. El ganador es el que tiene la mayor área total de las áreas sombreadas.
2. Un cuadrado con lados de diferentes colores en uno de cuatro colores se divide en varios cuadrados (generalmente 4 × 4). El primer movimiento pinta sobre el cuadrado adyacente al lado, en movimientos posteriores puede pintar sobre el cuadrado adyacente a uno de los cuadrados rellenos. No puede pintar sobre un cuadrado con los colores sobre los que está pintado uno de los cuadrados adyacentes o el lado adyacente al cuadrado. El jugador que hace el último movimiento gana.

En la cultura

• La isla de los cinco colores es un cuento fantástico de Martin Gardner .

Véase también

• Informática de prueba
• Problema de Nelson-Erdős-Hadwiger

Notas

1. ↑ Frank Harari. Conjetura de los cuatro colores // Teoría de grafos = Teoría de grafos. - M .: Mir , 1973. - S. 17-18.
2. ↑ Samokhin A.V. El problema de los cuatro colores: una historia inconclusa de la prueba  // Revista educativa Sorovsky. - 2000. - T. 6 , N º 7 .
3. ↑ 1 2 3 J. J. O'Connor, EF Robertson. El teorema de los cuatro colores . MacTutor Archivo de Historia de las Matemáticas . Escuela de Matemáticas y Estadística, Universidad de St Andrews, Escocia (septiembre de 1996). (indefinido)
4. ↑ Georges Gonthier. Una prueba verificada por computadora del Teorema de los cuatro colores  . Investigación de Microsoft Cambridge (2005). Archivado desde el original el 5 de junio de 2022.
5. ↑ 1 2 Shor N. Z. , Donets G. A. Sobre el problema de los cuatro colores // Matemáticas hoy / ed. profe. A. Ya. Dorogovtseva  - Kiev, escuela Vishcha, 1982. - Circulación 3000 copias. - C. 33-53
6. ↑ Lakeev A. V. Elementos de la teoría de grafos ordinarios. - Irkutsk: Editorial IGU, 2014. - P. 7. - 92 p.
7. ↑ AB Kempe. Sobre el problema geográfico de los cuatro colores  (inglés)  // Amer. Matemáticas J. . - 1879. - Vol. 2 . - P. 193-200 .
8. ↑ PG Tait. Nota sobre un teorema en geometría de posición   // Trans . Roy. soc. Edimburgo _ - 1880. - Vol. 29 . - P. 657-660 .
9. ↑ Percy John Heawood. Teorema del color del mapa  (inglés)  // Quarterly Journal of Mathematics, Oxford. - 1890. - Vol. 24 . - P. 332-338 .
10. ↑ G. Ringel, JWT Youngs. Solución del problema de coloración de mapas de Heawood   // Proc . Nat. Academia ciencia EE.UU. - 1968. - vol. 60 , edición. 2 . - Pág. 438-445 . -doi : 10.1073/ pnas.60.2.438 . — PMID 16591648 .
11. ↑ 1 2 Ringel G. Teorema de coloración de mapas / Traducido del inglés por V. B. Alekseev. — M .: Mir, 1977. — 256 p.
12. ↑ Boltyansky, 1982 , p. 77.
13. ↑ P. Franklin. Un problema de seis colores  //  J. Math. física - 1934. - Vol. 13 _ - Pág. 363-369 .
14. ↑ Jackson, Brad; Ringel, Gerhard. El problema del imperio de Heawood  //  J. Combin. Teoría Ser. B.- 1985.- vol. 38 , núm. 2 . - pág. 168-178 .
15. ↑ Martín Gardner. El problema de los cuatro colores // Acertijos matemáticos y diversiones = Acertijos matemáticos y diversiones: [trad. del  ingles ]. - 2ª ed. - M.  : Mir , 1999. - S. 389-390. — 447 pág. — ISBN 5-03-003340-8 .
16. ↑ Martín Gardner. La isla de los cinco colores . N.Y .: Fantasia Mathematica , 1958.

Literatura

• Ian Stewart . Los grandes problemas matemáticos = Los grandes problemas matemáticos. - M. : Dinastía : ANF, 2015. - 459 p. : il., tab. — ISBN 978-5-91671-318-3
• A. A. Zykov. Fundamentos de la teoría de grafos. - M. : libro Vuzovskaya, 2000. - S. 367-386.
• R. Courant, G. Robbins ¿Qué son las matemáticas?
• Samokhin A. V. El problema de los cuatro colores: una historia inconclusa de la prueba  // SOZH . - 2000. - Nº 7 . - S. 91-96 .  (Consultado: 7 de noviembre de 2018)
• Rodionov VV Métodos para colorear en cuatro colores los vértices de gráficos planos. - M. : KomKniga, 2000. - 48 p. - 2005 ejemplares.  — ISBN 5-484-00127-7 .
• Thomas, Robin El teorema de los cuatro colores Archivado el 21 de diciembre de 2007 en Wayback Machine .
• Ringel G. Teorema de coloración de mapas / Traducido del inglés por V. B. Alekseev. — M .: Mir, 1977. — 256 p.  - un libro con una prueba del problema para todas las superficies excepto el plano y la esfera
• Boltyansky V. G. , Efremovich V. A. Topología visual. — M .: Nauka, 1982. — 160 p. - ( Biblioteca "Cuántica" ).
• Donets GA, Shor NZ Sobre un enfoque algebraico del problema de colorear gráficos planos. - Kiev: Naukova Dumka , 1982. - 144 p.
• Harari F. Teoría de grafos. - M., Mir, 1973. - 304 p.

diccionarios y enciclopedias	Gran catalán gran chino gran ruso Britannica (en línea) Britannica (en línea) universalis