Gstinoco at 20:12, 27 December 2025

2025-12-27T20:12:16Z

Rbojeda: Rbojeda moved page Review 614603433199 to Calderon Juarez 2025a

2025-12-22T14:44:46Z

Rbojeda moved page Review 614603433199 to Calderon Juarez 2025a

Tereca at 05:31, 22 December 2025

2025-12-22T05:31:07Z

Show changes

Tereca at 20:20, 18 December 2025

2025-12-18T20:20:29Z

Show changes

Tereca: Tereca moved page Draft Calderon Juarez 956810406 to Review 614603433199

2025-12-15T05:50:57Z

Tereca moved page Draft Calderon Juarez 956810406 to Review 614603433199

Tereca: Created page with " ==Abstract== La ''colo..."

2025-12-15T05:35:30Z

Created page with "  ==Abstract== La ''colo..."

Show changes

@@ Line 1: / Line 1: @@
+==1 Introducción==
-<!-- metadata commented in wiki content
-==Coloración en gráficas de mapas en la Tierra y mapas en la Luna==
-−
-'''Ana Teresa Calderón Juárez'''
--->
-−
-==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 ''<math>3</math>-coloración'' de la Tierra-Luna es ''NP-completo'', mediante una reducción desde ''<math>3</math>-SAT'', lo que implica que no existe un algoritmo eficiente para resolverlo en general (suponiendo <math display="inline">P \neq NP</math>). 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 extiendel 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 <math display="inline">G</math> que es la unión de dos grafos planares (sobre el mismo conjunto de vértices).  Se demuestra mediante inducción que <math display="inline">G</math> es 12-coloreable, como observó Heawood. Ringel conjeturó que el Problema de la Tierra-Luna era <math display="inline">8</math>-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.
-−
-''Palabras clave:'' Problema de la Tierra-Luna; Coloración en grafos; Teorema de los cinco colores; Teorema de los cuatro colores; Complejidad computacional; Problemas de Satisfacción de restricciones; 3SAT; Reducción de problemas; Clases de problemas.
-−
-==2 Introducción==
 La coloración de mapas de la tierra es uno de los problemas de optimización más estudiados en la Teoría de Grafos. El problema de la coloración de un mapa consiste en asignar un color a cada vértice (país) de tal manera que dos vértices conectados por una arista obtengan colores diferentes, minimizando el número total de colores utilizados.
@@ Line 111: / Line 90: @@
 |}
-==3 Complejidad computacional de problemas que involucran coloración en grafos.==
+==2 Complejidad computacional de problemas que involucran coloración en grafos.==
 Comenzaremos con algunas definiciones antes de pasar a los resultados principales. Tanto en las matemáticas como en la teoría de la informática se han estudiado diferentes aspectos de los ''problemas de decisión''. Algunos de estos estudios se enfocan en determinar si existen ''algoritmos'' eficientes para resolverlos y en qué medida algunos problemas de decisión son más difíciles de resolver que otros. Al analizar estos problemas, encontramos que algunos presentan mayor complejidad que otros. Un problema de decisión importante dentro de la teoría de grafos, que será el principal objeto de estudio en esta sección, es el llamado ''3-coloración de grafos planares''. Este problema consiste en:
@@ Line 173: / Line 152: @@
 Existen clases distintas de problemas; aquellos cuyos algoritmos tienen tiempo de ejecución polinomial, o no.
-==4 Clases de problemas==
+==3 Clases de problemas==
 A continuación definimos las clases de problemas más usados, para preparar esta sección nos basamos en las notas del curso ''Design and Analysis of Algoritms'' del Profesor Erick Demaine <span id='citeF-6'></span>[[#cite-6|[6]]].
@@ Line 337: / Line 316: @@
 Otra forma de demostrar que los problemas de <math display="inline">3</math>-coloración en grafos son NP es modelar este problema como un problema de satisfacción de restricciones, dado que estos últimos son NP. En general, aunque en 2017 se demostró que, en el caso de que P <math display="inline">\neq </math> NP <span id='citeF-8'></span>[[#cite-8|[8]]], los problemas de satisfacción de restricciones pertenecen a la clase de problemas en los que se satisface la dicotomía; es decir, son P o son NP.
-==5 Problemas de Satisfacción de Restricciones.==
+==4 Problemas de Satisfacción de Restricciones.==
 ''Los Problemas de Satisfacción de Restricciones'' (CSP, por sus siglas en inglés) constituyen un área fundamental en la teoría de la computación. Estos se definen como conjuntos de objetos que deben satisfacer una serie de restricciones o limitaciones.
@@ Line 549: / Line 528: @@
 Y, dado que 3-SAT es NP-completo, concluimos que el problema de 3-coloración en grafos planares también es NP-completo.
-==6 El Problema de la Tierra-Luna (Earth-Moon Problem).==
+==5 El Problema de la Tierra-Luna (Earth-Moon Problem).==
 El problema de la Tierra-Luna es un problema que permanece abierto dentro del ámbito de la coloración de grafos, planteado por Gerhard Ringel en 1959 <span id='citeF-1'></span>[[#cite-1|[1]]]. Como vimos en la introducción este problema es una extensión del problema de la coloración de mapas planos, cuya solución se obtiene a través del Teorema de los Cuatro Colores (véase teorema [[#theorem-C2T4coloreable|1]]).
@@ Line 773: / Line 752: @@
 Con el objetivo de analizar su complejidad computacional, en la siguiente sección presentaremos la modelación del Problema de la Tierra-Luna como un CSP, con el propósito de demostrar que es un problema de complejidad NP-hard.
-==7 Problema de la Tierra-Luna a través de los CSP.==
+==6 Problema de la Tierra-Luna a través de los CSP.==
 Empezamos esta sección construyendo el siguiente ejemplo. Tenemos una porción de países europeos: Alemania, Austria, Bélgica, Francia, Países Bajos, Luxemburgo, Polonia, República Checa y Suiza (véase figura [[#img-7|7]]). El problema consiste en colorear los países utilizando el mínimo número de colores de tal manera que no haya dos países colindantes que compartan el mismo color.
@@ Line 1,038: / Line 1,017: @@
 Hasta ahora, hemos demostrado que un problema <math display="inline">3</math>SAT puede reducirse al Problema de la Tierra-Luna de forma general. Dado que <math display="inline">3</math>SAT es un problema NP-completo, la reducción implica que el Problema de la Tierra-Luna también es NP-completo.
-==8 Conclusión==
+==7 Conclusión==
 Este trabajo ha ofrecido una revisión sobre los problemas de coloración en grafos. Que se profundiza más en la tesis de la cual se deriva este artículo.
@@ Line 1,066: / Line 1,045: @@
 Finalmente, se abordó el problema de colorear mapas de la Tierra-Luna, que ilustra la evolución del pensamiento en la teoría de grafos y la necesidad de seguir investigando áreas abiertas para avanzar en nuestra comprensión de la coloración de grafos. Se concluye con la demostración <math display="inline">3\hbox{SAT} \leq _p</math> Problema Tierra-Luna, es decir, que se el problema <math display="inline">3</math>SAT se puede reducir en tiempo polinómico a una instancia del Problema Tierra-Luna, de dicha reducción se puede concluir que este problema último es NP-completo. La demostración se hizo en colaboración con mi asesora Edith Vargas y el profesor Mike Behrisch, hasta la fecha dicha demostración no ha sido encontrada en alguna bibliografía. Se continuó investigando y podemos afirmar que el problema de colorear mapas en la Tierra-Luna es un problema NP-completo para <math display="inline">n=4</math>, <math display="inline">n=5</math> y <math display="inline">n=6</math> colores. Las pruebas de estas afirmaciones se encontrarán en un futuro artículo.
-===BIBLIOGRAPHY===
+===BIBLIOGRAFÍA===
 <div id="cite-1"></div>

← Older revision	Revision as of 14:44, 22 December 2025
(No difference)

← Older revision	Revision as of 05:50, 15 December 2025
(No difference)

Calderon Juarez 2025a - Revision history

Gstinoco at 20:12, 27 December 2025

Rbojeda: Rbojeda moved page Review 614603433199 to Calderon Juarez 2025a

Tereca at 05:31, 22 December 2025

Tereca at 20:20, 18 December 2025

Tereca: Tereca moved page Draft Calderon Juarez 956810406 to Review 614603433199

Tereca: Created page with " ==Abstract== La ''colo..."