teorema de los cuatro colores
En matemáticas , el teorema de los cuatro colores , o el teorema del mapa de cuatro colores , establece que no se requieren más de cuatro colores para colorear las regiones de cualquier mapa, de modo que no haya dos regiones adyacentes que tengan el mismo color. Adyacente significa que dos regiones comparten un segmento de curva límite común, no simplemente una esquina donde se encuentran tres o más regiones. [1] Fue el primer teorema importante que se demostró usando una computadora . Inicialmente, esta prueba no fue aceptada por todos los matemáticos porque la prueba asistida por computadora era inviable para que un ser humano la verificara a mano . [2]La prueba ha ganado una amplia aceptación desde entonces, aunque quedan algunos escépticos. [3]
El teorema de los cuatro colores fue probado en 1976 por Kenneth Appel y Wolfgang Haken después de muchas pruebas falsas y contraejemplos (a diferencia del teorema de los cinco colores , probado en el siglo XIX, que establece que cinco colores son suficientes para colorear un mapa). Para disipar cualquier duda restante sobre la prueba de Appel-Haken, Robertson, Sanders, Seymour y Thomas publicaron en 1997 una prueba más simple que usa las mismas ideas y aún se basa en computadoras. En 2005, Georges Gonthier también demostró el teorema con un software de prueba de teoremas de propósito general .
En términos de teoría de grafos, el teorema establece que para un grafo plano sin bucles , su número cromático es .
La declaración intuitiva del teorema de los cuatro colores: "dada cualquier separación de un plano en regiones contiguas, las regiones se pueden colorear utilizando como máximo cuatro colores para que no haya dos regiones adyacentes que tengan el mismo color", debe interpretarse adecuadamente para que sea correcta. .
Primero, las regiones son adyacentes si comparten un segmento límite; dos regiones que comparten solo puntos límite aislados no se consideran adyacentes. En segundo lugar, no se permiten regiones extrañas, como las que tienen un área finita pero un perímetro infinitamente largo; los mapas con tales regiones pueden requerir más de cuatro colores. [4] (Para estar seguros, podemos restringirnos a regiones cuyos límites consisten en un número finito de segmentos de línea recta. Se permite que una región rodee por completo una o más regiones). Tenga en cuenta que la noción de "región contigua" (técnicamente: subconjunto abierto conectado del plano) no es lo mismo que el de un "país" en los mapas regulares, ya que los países no necesitan ser contiguos (por ejemplo, la provincia de Cabinda como parte de Angola ,Najicheván como parte de Azerbaiyán , Kaliningrado como parte de Rusia y Alaska como parte de los Estados Unidos no son contiguos). Si requerimos que todo el territorio de un país reciba el mismo color, entonces cuatro colores no siempre son suficientes. Por ejemplo, considere un mapa simplificado:
En este mapa, las dos regiones etiquetadas con A pertenecen al mismo país. Si quisiéramos que esas regiones recibieran el mismo color, entonces se requerirían cinco colores, ya que las dos regiones A juntas son adyacentes a otras cuatro regiones, cada una de las cuales es adyacente a todas las demás. Se puede modelar forzar dos regiones separadas para que tengan el mismo color agregando un 'mango' que las une fuera del plano.
