¿Cuántos colores se necesitan para colorear gráficos biplanares?
El problema Tierra-Luna es un problema sin resolver sobre coloración de gráficos en matemáticas. Es una extensión del problema de coloración de mapas planos (resuelto mediante el teorema de los cuatro colores ) y fue planteado por Gerhard Ringel en 1959. [1] Una forma intuitiva del problema pregunta cuántos colores se necesitan para colorear mapas políticos de la Tierra. y Luna, en un futuro hipotético donde cada país de la Tierra 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 los grafos biplanares . Se sabe que este número es como mínimo 9 y como máximo 12.
El problema Tierra-Luna se ha ampliado a problemas análogos de colorear mapas de cualquier número de planetas. Para esta extensión, los límites inferior y superior del número de colores están más cerca, con una diferencia de dos entre sí. Una aplicación del mundo real del problema Tierra-Luna implica probar placas de circuito impreso .
En el problema de coloración de mapas, se deben colorear un número finito de regiones simplemente conectadas en el plano euclidiano o en un espacio topológicamente equivalente, como países en la superficie de la Tierra, 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 creando un vértice para cada región y un borde para cada dos regiones vecinas, produciendo un gráfico plano cuyos vértices se van a colorear. De acuerdo con el requisito de que las regiones adyacentes deben tener colores diferentes, los vértices adyacentes (los dos puntos finales de cualquier borde) deben tener colores diferentes. Según el teorema de los cuatro colores , el gráfico plano resultante (o cualquier gráfico plano) se puede colorear usando como máximo cuatro colores diferentes, sin importar cuántas regiones se den. [2]
En 1959, Gerhard Ringel publicó un libro sobre coloración de superficies, examinando los resultados de la época sobre el problema de los cuatro colores y la conjetura de Heawood sobre mapas de coloración en superficies no planas como el toroide y la botella de Klein . [1] 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 JWT Youngs ; [2] [3] el teorema de los cuatro colores evadió la demostración hasta 1976. [2] [4] Otro tema del libro de Ringel fue un resultado de Percy John Heawood de 1890, sobre el "problema del imperio": colorear mapas en los que cada imperio Tiene varias regiones distintas en la Tierra (un país de origen y colonias). Como demostró Heawood para , y Ringel lo demostró más tarde con Jackson en 1984 para , los colores son necesarios y suficientes. [2] [5] [6] [7] 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. [1] [2] En una formulación de Martin Gardner , las colonias están en cambio en Marte. [6]
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 a la disposición de las fronteras en la Tierra. Los países deben estar coloreados, usando el mismo color para cada país y su colonia, de modo que cuando dos países comparten frontera ya sea en la Tierra o en la Luna se les dan colores diferentes. El problema de Ringel pregunta: ¿cuántos colores se necesitan para garantizar que todos los países puedan colorearse, sin importar cómo estén dispuestas sus fronteras? [2] Ringel demostró que el número de colores necesarios era al menos 8 y como máximo 12, conjeturando que 8 era la respuesta correcta. [6]
Nuevamente, se puede formular la misma pregunta de manera equivalente a la de la teoría de grafos, con un solo vértice para cada par de un país y su colonia, y una arista para cada adyacencia entre países o colonias. Como en el caso plano, tras esta transformación son los vértices los que se deben colorear, siendo diferentes los colores de los extremos de cada arista. Las gráficas que resultan en esta versión del problema son gráficas biplanares , o equivalentemente gráficas de espesor dos: sus aristas se pueden dividir en dos subconjuntos (las aristas que provienen de las adyacencias de la Tierra y las que provienen de las adyacencias de la Luna) de modo que los dos subgrafos correspondientes ambos son planos. En términos matemáticos, el problema de Ringel pide el número cromático máximo de gráficos biplanares. [2]
Un gráfico biplanar en vértices tiene como máximo aristas (el doble del número que puede tener un gráfico plano), de lo que 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 no utilizado con el número más pequeño para el vértice eliminado conduce a una coloración con como máximo 12 colores; esta es la coloración codiciosa para un orden de degeneración del gráfico. Por tanto, los gráficos biplanares requieren como máximo 12 colores. [2]
Se puede construir un ejemplo de un gráfico biplanar que requiere 9 colores como la unión de un gráfico completo de 6 vértices y un gráfico cíclico 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 cíclico, lo que da 9 colores en total. [2] Esta construcción, realizada por Thom Sulanke en 1974, refutaba la conjetura de Ringel de que 8 colores siempre serían suficientes. [6] Posteriormente, se ha construido una familia infinita de gráficos biplanares de 9 críticos (gráficos mínimos que requieren nueve colores). [8] [9]
A pesar de la falta de mayores avances en el problema, en 2018 Ellen Gethner conjeturó que el número correcto de colores para este problema es 11. Sugiere varios candidatos para gráficos biplanares de 10 cromáticos, incluido el gráfico obtenido como producto fuerte de un gráfico cíclico. con una camarilla, y el gráfico obtenido eliminando cualquier vértice de . Se puede demostrar 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 una coloración con menos colores. Además, cumplen con los límites del número de aristas que puede tener un gráfico biplanar. Sin embargo, sigue siendo difícil representarlos como gráficos biplanares (o mapas Tierra-Luna). [10]
Una aplicación de la coloración 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 algo de cuidado, esta idea se puede utilizar para reducir el número de pruebas necesarias por circuito a sólo cuatro. [2] [11]
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. [12] [13] Los mapas con un planeta y múltiples regiones por país plantean el problema del imperio de Heawood. [2] [7] Los mapas con más de dos planetas pero sólo una región por planeta corresponden a gráficos cuyo espesor es como máximo igual al número de planetas. De estos gráficos se conocen resultados más precisos (aunque aún incompletos). Para las gráficas de espesor y los mapas de planetas correspondientes, el número cromático se basa como máximo en el mismo argumento de degeneración utilizado en el problema Tierra-Luna. Además, para , un gráfico completo con vértices tiene espesor , para mostrar algunos de estos gráficos requieren colores. Por lo tanto, en este caso, los límites superior e inferior están separados por dos colores entre sí. [14]
