El problema Tierra-Luna es un problema sin resolver sobre la coloración de grafos en matemáticas. Es una extensión del problema de coloración de mapas planos (resuelto por el teorema de los cuatro colores), y fue planteado por Gerhard Ringel en 1959. Una forma intuitiva del problema pregunta cuántos colores se necesitan para colorear los mapas políticos de la Tierra y la Luna, en un futuro hipotético en el que cada país Terrestre tiene una colonia lunar a la que se le debe dar el mismo color. En términos matemáticos, busca el número cromático de grafos biplanares. Se sabe que este número es al menos 9 y como máximo 12.

El problema Tierra–Luna se ha extendido a problemas análogos de colorear mapas en cualquier número de planetas. Para esta extensión, los límites inferiores y superiores del número de colores están más cerca, dentro de dos entre sí. Una aplicación real del problema Tierra-Luna implica probar placas de circuito impreso.

Formulación e historia En el problema de coloración de mapas, un número finito de regiones simplemente conectadas en el plano euclidiano o en un espacio topológicamente equivalente, como los países en la superficie de la Tierra, deben colorearse de modo que, cuando dos regiones comparten un límite de longitud distinta de cero, tengan colores diferentes. Se puede transformar en un problema de coloración de gráficos haciendo un vértice para cada región y un borde para cada dos regiones vecinas, produciendo un grafo plano cuyos vértices se van a colorear. En correspondencia con el requisito de que las regiones adyacentes tengan colores diferentes, los vértices adyacentes (los dos puntos finales de cualquier borde) deben tener colores diferentes. De acuerdo con el teorema de los cuatro colores, el grafo plano resultante (o cualquier gráfico plano) se puede colorear usando como máximo cuatro colores diferentes, sin importar cuántas regiones se den.

En 1959, Gerhard Ringel publicó un libro sobre colorantes de superficies, examinando los resultados en ese momento sobre el problema de los cuatro colores y la conjetura de Heawood sobre mapas para colorear en superficies no planas como el toro y la botella de Klein. Ambos habían sido conjeturados durante mucho tiempo, pero no estaban resueltos en ese momento. El propio Ringel demostró más tarde la conjetura de Heawood en un artículo de 1968 con J. W. T. Youngs; el teorema de los cuatro colores eludió la prueba hasta 1976. Otro tema del libro de Ringel fue el resultado de Percy John Heawood de 1890, sobre el "problema del imperio": colorear mapas en los que cada imperio tiene algún número de distintas regiones de la Tierra (un país de origen y colonias ). Como Heawood demostró para , y Ringel demostró más tarde con Jackson en 1984, para , los colores son necesarios y suficientes. Quizás inspirado por este problema y los albores de la era espacial, Ringel incluyó el problema Tierra-Luna en su libro como una variante del problema del imperio en el que las colonias están en la Luna en lugar de en la Tierra. En una formulación de Martin Gardner, las colonias están en cambio en Marte.

En el problema Tierra–Luna de Ringel, cada país de la Tierra tiene una colonia correspondiente en la superficie de la Luna, a la que se le debe dar el mismo color. Estas colonias pueden tener fronteras que son completamente diferentes de la disposición de las fronteras en la Tierra. Los países deben ser coloreados, usando el mismo color para cada país y su colonia, de modo que cuando dos países comparten una frontera, ya sea en la Tierra o en la Luna, se les den colores diferentes. El problema de Ringel pregunta: ¿Cuántos colores se necesitan para garantizar que todos los países puedan ser coloreados, sin importar cómo estén dispuestas sus fronteras? Ringel demostró que el número de colores necesarios era de al menos 8 y como máximo 12, conjeturando que 8 era la respuesta correcta.

Nuevamente, se puede formular la misma pregunta de manera equivalente a una en teoría de grafos, con un solo vértice para cada par de un país y su colonia, y un borde para cada adyacencia entre países o colonias. Como en el caso plano, después de esta transformación, son los vértices los que deben colorearse, con diferentes colores para los extremos de cada arista. Los gráficos que dan como resultado esta versión del problema son gráficos biplanares, o equivalentemente gráficos de grosor dos: sus bordes se pueden dividir en dos subconjuntos (los bordes provenientes de las adyacencias de la Tierra y los que provienen de las adyacencias de la Luna) de modo que los dos subgrafos correspondientes sean ambos planos. En términos matemáticos, el problema de Ringel pide el número cromático máximo de grafos biplanares.

Límites Un grafo biplanar en vértices tiene como máximo aristas (el doble del número que puede tener un grafo plano), de lo cual se deduce de la fórmula de suma de grados que tiene al menos un vértice con como máximo 11 vecinos. Eliminar este vértice, colorear el gráfico restante de forma recursiva y luego usar el color sin usar con el número más pequeño para el vértice eliminado conduce a una coloración con un máximo de 12 colores; esta es la coloración codiciosa para un ordenamiento degenerado del gráfico. Por lo tanto, los gráficos biplanares requieren como máximo 12 colores. miniaturadeimagen|490x490px|Mapa Tierra-Luna de nueve colores de Sulanke (izquierda y derecha), con adyacencias descritas por la unión de un grafo completo de 6 vértices y un grafo ciclo de 5 vértices (centro) Un ejemplo de un gráfico biplanar que requiere 9 colores se puede construir como la unión de un grafo completo de 6 vértices y un grafo ciclo de 5 vértices. Esto significa que estos dos subgrafos están conectados por todos los bordes posibles de un subgrafo al otro. El gráfico resultante tiene 11 vértices y requiere 6 colores para el subgrafo completo y 3 colores para el subgrafo del ciclo, lo que da 9 colores en total. Esta construcción, de Thom Sulanke en 1974, refutó la conjetura de Ringel de que 8 colores siempre serían suficientes. Posteriormente, se ha construido una familia infinita de gráficos biplanares de 9 críticos (gráficos mínimos que requieren nueve colores).

A pesar de la falta de avances adicionales en el problema, en 2018, Ellen Gethner conjeturó que el número correcto de colores para este problema es 11. Ella sugiere varios candidatos para gráficos biplanares de 10 colores, incluido el gráfico obtenido como el producto fuerte de un gráfico de ciclo con una camarilla, y el gráfico obtenido eliminando cualquier vértice de . Se puede mostrar que estos gráficos requieren 10 colores, porque no tienen un conjunto independiente lo suficientemente grande como para ser la clase de color más grande en un colorante con menos colores. Además, cumplen los límites del número de aristas que puede tener un gráfico biplanar. Sin embargo, una representación de ellos como gráficos biplanares (o mapas Tierra–Luna) sigue siendo difícil de alcanzar. En 2023, se confirmó que este último gráfico no es biplanar.

Aplicación Una aplicación de colorantes de gráficos biplanares implica probar placas de circuito impreso en busca de cortocircuitos. Los conductores eléctricos dentro de estas placas incluyen cruces, pero (para placas de circuito impreso de doble cara) se puede suponer que sus adyacencias forman un gráfico biplanar. Después de colorear este gráfico, se pueden detectar cortocircuitos entre conductores adyacentes agregando circuitos adicionales para conectar todos los conductores con los mismos colores entre sí y probando las conexiones entre pares de diferentes colores. Con cierto cuidado, esta idea se puede utilizar para reducir el número de pruebas necesarias por circuito a solo cuatro.

Generalizaciones También se han considerado varias generalizaciones del problema, incluidas versiones del problema con más de dos planetas o con países que pueden tener más de una región por planeta. Los mapas con un planeta y varias regiones por país dan el problema del imperio de Heawood. Los mapas con más de dos planetas pero solo una región por planeta corresponden a grafos cuyo grosor es como máximo igual al número de planetas. Para estos gráficos, se conocen resultados más precisos (aunque aún incompletos). Para los gráficos de espesor y los mapas de planetas correspondientes, el número cromático es como máximo por el mismo argumento de degeneración utilizado en el problema Tierra-Luna. Además, para , un gráfico completo con vértices tiene un grosor , mostrar algunos de estos gráficos requiere colores. Por lo tanto, en este caso, los límites superior e inferior están dentro de dos colores entre sí.

Referencias

Enlaces externos

Categoría:Teoría de grafos Categoría:Color Categoría:Problemas matemáticos Categoría:Grafos