| Line 1: | Line 1: | ||
== Abstract == | == Abstract == | ||
| − | La | + | La ''coloración de mapas'' es un problema clásico en la ''Teoría de Grafos'', donde cada país se |
| − | modela como un vértice y las fronteras entre países como aristas. El | + | modela como un vértice y las fronteras entre países como aristas. El ''Teorema de los Cuatro |
| − | Colores | + | Colores'' establece que cualquier mapa plano puede colorearse con cuatro colores sin que dos |
regiones adyacentes compartan el mismo color. | regiones adyacentes compartan el mismo color. | ||
En este artículo, exploramos la generalización del problema de coloración de mapas al caso de la | En este artículo, exploramos la generalización del problema de coloración de mapas al caso de la | ||
| − | Tierra y la Luna, conocido como el | + | Tierra y la Luna, conocido como el '''Earth Moon Problem''', propuesto por Ringel. Este problema |
busca determinar el número mínimo de colores necesarios para colorear un mapa donde cada | busca determinar el número mínimo de colores necesarios para colorear un mapa donde cada | ||
país en la Tierra y su colonia lunar deben recibir el mismo color, respetando la restricción de que | país en la Tierra y su colonia lunar deben recibir el mismo color, respetando la restricción de que | ||
las regiones adyacentes en cualquiera de los dos cuerpos celestes deben tener colores distintos. | las regiones adyacentes en cualquiera de los dos cuerpos celestes deben tener colores distintos. | ||
| − | Nuestro principal aporte es demostrar que el problema de la | + | Nuestro principal aporte es demostrar que el problema de la ''3-coloración'' de la Tierra-Luna es |
| − | + | ''NP-completo'', mediante una reducción desde ''3-SAT'', lo que implica que no existe un algoritmo | |
| − | eficiente para resolverlo en general (suponiendo | + | eficiente para resolverlo en general (suponiendo ''P ≠ NP''). Además, complementamos |
demostraciones previas que aparecían incompletas en la literatura y modelamos el problema | demostraciones previas que aparecían incompletas en la literatura y modelamos el problema | ||
| − | como un | + | como un ''problema de satisfacción de restricciones'' (CSP), lo que permite un análisis más |
profundo de su complejidad computacional. | profundo de su complejidad computacional. | ||
| Line 23: | Line 23: | ||
sobre su dificultad para diferentes números de colores. | sobre su dificultad para diferentes números de colores. | ||
| − | Por último, describir el problema de coloración de la Tierra-Luna a través de grafos, un caso abierto en la coloración de grafos que extiende el problema de la coloración de mapas planos. En términos de grafos, esto se puede reformular como la búsqueda del | + | Por último, describir el problema de coloración de la Tierra-Luna a través de grafos, un caso abierto en la coloración de grafos que extiende el problema de la coloración de mapas planos. En términos de grafos, esto se puede reformular como la búsqueda del número cromático máximo de un grafo ''G'' que es la unión de dos grafos planares (sobre el mismo conjunto de vértices). Se demuestra mediante inducción que ''G'' es 12-coloreable, como observó Heawood. Ringel conjeturó que el Problema de la Tierra-Luna era ''8''-coloreable pero Sulanke reportó un ejemplo que requiere 9 colores, aún no se conoce si existen configuraciones que requieran 10, 11 o 12 colores. |
== Document == | == Document == | ||
<pdf>Media:Draft_Calderon Juarez_591692200-2681-document.pdf</pdf> | <pdf>Media:Draft_Calderon Juarez_591692200-2681-document.pdf</pdf> | ||
Latest revision as of 22:46, 25 November 2025
Abstract
La coloración de mapas es un problema clásico en la Teoría de Grafos, donde cada país se modela como un vértice y las fronteras entre países como aristas. El Teorema de los Cuatro Colores establece que cualquier mapa plano puede colorearse con cuatro colores sin que dos regiones adyacentes compartan el mismo color.
En este artículo, exploramos la generalización del problema de coloración de mapas al caso de la Tierra y la Luna, conocido como el Earth Moon Problem, propuesto por Ringel. Este problema busca determinar el número mínimo de colores necesarios para colorear un mapa donde cada país en la Tierra y su colonia lunar deben recibir el mismo color, respetando la restricción de que las regiones adyacentes en cualquiera de los dos cuerpos celestes deben tener colores distintos.
Nuestro principal aporte es demostrar que el problema de la 3-coloración de la Tierra-Luna es NP-completo, mediante una reducción desde 3-SAT, lo que implica que no existe un algoritmo eficiente para resolverlo en general (suponiendo P ≠ NP). Además, complementamos demostraciones previas que aparecían incompletas en la literatura y modelamos el problema como un problema de satisfacción de restricciones (CSP), lo que permite un análisis más profundo de su complejidad computacional.
Este trabajo no solo aporta una nueva demostración de que el problema de coloración de la Tierra-Luna con 3 colores es NP-completo, sino que también abre la puerta a futuros estudios sobre su dificultad para diferentes números de colores.
Por último, describir el problema de coloración de la Tierra-Luna a través de grafos, un caso abierto en la coloración de grafos que extiende el problema de la coloración de mapas planos. En términos de grafos, esto se puede reformular como la búsqueda del número cromático máximo de un grafo G que es la unión de dos grafos planares (sobre el mismo conjunto de vértices). Se demuestra mediante inducción que G es 12-coloreable, como observó Heawood. Ringel conjeturó que el Problema de la Tierra-Luna era 8-coloreable pero Sulanke reportó un ejemplo que requiere 9 colores, aún no se conoce si existen configuraciones que requieran 10, 11 o 12 colores.
Document
Document information
Published on 25/11/25
Licence: CC BY-NC-SA license
