¿Existe algún resultado tipo el teorema de los cuatro colores en tres dimensiones?

El teorema de los cuatro colores asegura que todo mapa plano puede colorearse con, a lo sumo, cuatro colores de forma que regiones con frontera común tengan colores distintos. Atentos: mapa plano. Es decir, un mapa que se pueda dibujar en un plano, en dos dimensiones (*). ¿Y qué ocurre si subimos una dimensión? Esto es, ¿existe algún resultado tipo el teorema de los cuatro colores para mapas formados por regiones tridimensionales?

Pues la respuesta es que no existe una cota para el número de colores necesario para colorear un mapa de regiones tridimensionales de forma que dos regiones con frontera común tengan colores distintos. Es decir, se pueden construir mapas de regiones tridimensionales para los cuales haga falta una cantidad de colores igual a un número natural cualquiera. Y la razón vuelve a estar, como en el caso del teorema para mapas planos, en la teoría de grafos.

Como ya vimos en la entrada de ayer sobre el teorema de los cuatro colores, todo mapa plano es equivalente a un grafo plano en el que cada vértice corresponde con una región del mapa inicial y en el que una arista una dos vértices representa que en el mapa inicial esas dos regiones tenían frontera común. Pero en general esa equivalencia se tiene con cualquier mapa, hasta con los tridimensionales, aunque en ese caso el grafo puede no ser plano. Por tanto en vez de un mapa tridimensional consideremos su grafo asociado.

La cuestión clave de este asunto es que cualquier grafo (plano o no) se puede representar en el espacio tridimensional de manera que no haya dos aristas que se corten en algún punto que no sea un vértice (esta propiedad se suele expresar diciendo que todo grafo es realizable en el espacio tridimensional). Entonces, por poner un par de ejemplos, los grafos completos son realizables en tres dimensiones (pero si tiene cinco o más vértices no lo son en dos dimensiones, es decir, no son planos). Un grafo completo, que suele representarse como K_n, es un grafo con n vértices que cumple que cada vértice está unido con todos los demás con una arista. Por ejemplo, aquí tenéis a K_5 y a K_6:

Si nos fijamos, por ejemplo, en K_5 vemos que el hecho de que cada vértice esté unido con los otros cuatro nos obliga a utilizar cinco colores para colorear sus vértices (si usamos menos siempre habría al menos dos vértices conectados con una arista que tendría el mismo color). ¿Y cuántos hacen falta para K_6? Pues, por la misma razón, nos harán falta seis colores. En general, para colorear los vértices de K_n de la forma descrita antes se necesitan n colores. Por tanto no hay cota del máximo número de colores necesarios para colorear los vértices de un grafo en tres dimensiones, y por tanto ocurre lo mismo con un mapa tridimensional. Asunto resuelto.

Con colores todo queda mucho mejor

Vale, sí, asunto resuelto, pero con colores todo queda mucho mejor, ¿verdad? Estamos todos de acuerdo en que usando grafos queda todo demostrado, pero si vemos el mapa tridimensional con sus colores seguro que nos quedara más claro. Pues vamos a ello. Vamos a ver un ejemplo que Claudi Alsina plantea en su libro Mapas del metro y redes neuronales en el que se ve que se pueden construir mapas tridimensionales para los cuales hagan falta tantos colores como un número natural cualquiera.

La construcción se va a hacer en forma de sucesión de conjuntos: construiremos uno para el que necesitamos un color, a partir de ése construiremos otros para el que hacen falta dos colores, y así sucesivamente. El primero de ellos va a ser una pieza cúbica, un cubo. Para pintarlo necesitamos un único color (usamos el amarillo). Le pegamos otro cubo al inicial y obtenemos el segundo conjunto. Ahora necesitamos dos colores (usamos el amarillo inicial y el naranja para el nuevo cubo). Y el tercero se obtiene pegándole a esos dos cubos una pieza como la que se ve pintada de azul a la derecha en la imagen siguiente (donde también aparecen los dos primeros conjuntos):

En ese tercer conjunto, como la pieza que añadimos tiene frontera común con las otras dos tenemos que se necesitan tres colores. Colocamos ahora una nueva pieza como aparece en la siguiente figura pintada de verde:

Necesitamos un nuevo color porque dicha pieza “toca” a las tres anteriores. Ya tenemos un mapa que necesita cuatro colores. Para construir uno que necesite cinco hacemos lo siguiente: duplicamos el mapa que necesita cuatro y lo pegamos debajo de ese mismo mapa por las partes verdes (que pasarán a ser una única pieza). Después añadimos una pieza tipo la verde anterior. La cosa queda más o menos así:

La pieza que acabamos de añadir está en contacto con todas las anteriores, por lo que debe ir en un color distinto a los que teníamos ya (gris en este caso). Ya tenemos uno que necesita cinco colores.

Y siguiendo de la misma forma (duplicamos el mapa anterior, pegamos por las partes correspondientes a la última pieza que se añadió y se coloca una nueva pieza que tiene parte común con todas las anteriores) obtenemos mapas que van necesitando cada vez más colores. El que necesita seis colores quedaría así:

En él hemos pintado la nueva pieza de color dorado. Y el que necesita siete colores (con la nueva pieza en rosa) queda de la siguiente forma:

Con este procedimiento podemos construir mapas tridimensionales que necesitan una cantidad cualquiera de colores para colorearlos de forma que regiones con frontera común tengan colores distintos. Por tanto no hay cota para el número máximo de colores necesarios para ello.


(*) En un plano…o en una esfera tridimensional, ya que cualquier mapa dibujado en una esfera en tres dimensiones tiene su equivalente en dos dimensiones a través de la proyección estereográfica.


Quinta aportación a la Edición 4.123 del Carnaval de Matemáticas, que organiza el blog Eulerianos.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

10 Comentarios

  1. Bonito ejemplo. El que yo utilizo para verlo consiste en capas planas con un cilindro que sobresale hacia arriba y abajo. Puedo superponer tantas capas como quiera con los cilindros de cada una atravesando (y tocando) todas las demás.

    Vamos, como una tarta de capas y pinchos de lo mismo que las capas que la atraviesan.

    Publica una respuesta
  2. En la página 15 de esta presentación se da un ejemplo debido a Tietze.
    http://www.ehu.es/~mtwmastm/Colores_Durango_21febrero2011.pdf
    La propuesta de Tietze consistía en tomar barras numeradas de 1 hasta n.
    Se sitúan, ordenadas de manera horizontal como muestra la figura, y sobre ellas se colocan n barras numeradas de 1 hasta n en sentido vertical.
    De este modo, tenemos un mapa tridimensional con n “países”, y que necesita exactamente n colores para no contradecir las reglas de la conjetura…

    Publica una respuesta
  3. Yo ese ejemplo no lo veo claro. Indica una forma de ir añadiendo colores, pero no es la única forma de colorearlos.

    Yo puedo crear un razonamiento para ir rellenando con muchos colores, pero eso no garantiza que sea el mínimo.

    De hecho la última imagen en la que se utilizan 7 colores, es posible colorearla fácilmente con 6 colores. Y la anterior de 6 colores se puede rellenar usando sólo 5.

    Por tanto…algo anda mal en el razonamiento, no?

    Publica una respuesta
  4. Cartesiano, me parece que en la última imagen solo hay siete piezas, que al ser tridimensionales están conectadas por detrás. Por eso cada una está en contacto con las otras seis y no se pueden usar seis colores.

    Al menos yo lo entiendo así.

    Publica una respuesta
  5. Mmonchi, realmente eso no tiene importancia, ya que no es la pieza trasera la que estorba.

    Parece obvio que un mapa tridimensional puede dualizarse en un grafo con múltiples conexiones entre vértices que no se cortan entre sí, no como en un grafo plano. Por eso una pieza trasera podría tambalear todo el coloreado con 4 colores.

    Pero el caso es que esa construcción particular se puede colorear con menos de lo que indica.

    Vamos a verlo en el ejemplo de 6 colores:
    1. Partimos de los colores en orden:
    – amarillo
    – rojo (naranja oscuro)
    – azul
    – verde
    – gris
    – naranja
    2. En la figura construida, sustituimos el color gris por el rojo
    3. Donde habia frontera entre gris y rojo, ponemos el rojo en gris.
    4. Cambiamos el naranja por el gris.
    5. Ha desaparecido el color naranja de la figura.

    El color azul que está por detrás está tocando a todos, pero todos los colores ya no son 6, si no 5 (incluido el azul).

    Lo mismo se puede hacer con la última figura de 7 colores.

    Sin embargo, un ejemplo en concreto no generaliza todo un conjunto. Está mucho más claro con el ejemplo que dice Marta con las barras de NxN. Es muy visual. 🙂

    Publica una respuesta
  6. Cartesiano, dices “3. Donde habia frontera entre gris y rojo, ponemos el rojo en gris.” Pero solo hay una pieza roja, que asoma por ocho sitios diferentes. No puedes cambiar unos sitios y otros no porque solo hay una pieza roja. Solo hay una amarilla, una azul, una verde… La tridimensionalidad hace que una pieza se cruce con otras, quizás faltarían unas líneas ocultas, o la vista inferior, para que estuviera más claro.

    Desde luego el ejemplo de Marta se entiende mucho mejor.

    Publica una respuesta
  7. Cartesiano caótico, en tu ejemplo hay dos regiones con frontera común coloreadas con el mismo color: la que era roja, que has coloreado en gris, y la que era naranja, que también has coloreado en gris.

    Publica una respuesta
  8. Como una imagen vale más que mil palabras…
    A ver si funciona:
    https://docs.google.com/drawings/d/1O7Sg59-RFaFQO0cWaOIm_OVQ3YEC3DuZ2NfusYTCnFE/edit?usp=sharing

    Sigo sin ver que la pieza azul, por mucho que se extienda por detrás pueda fastidiarme el invento.

    Buff, lo acabo de ver ahora mismo tras estudiar los comentarios de Mmonchi. Desde luego que ni el dibujo, ni la explicación sugiere que las piezas amarillas y rojas sean una sola cada una. Yo entendí que al duplicar el dibujo la pieza verde era una sola, y no las demás.

    Fallo mío. Lo más importante para resolver un problema es comprenderlo bien 🙂

    Publica una respuesta
  9. Un tal Gutrie o algo asi, demostro esto a principio del siglo XX…

    Publica una respuesta
  10. ¡Qué pena no haber visto este debate para intervenir antes!

    El caso es por cierto que sea lo que se dice en la primera parte del artículo, este ejemplo no me lo trago.¿No vemos que en realidad no estamos haciendo un razonamiento tridimensional sino bidimensional? Lo cierto es que el azul sólo aporta un color más y a partir del verde la ampliación que hacemos es sólo en dos dimensiones: a lo largo y a lo alto, pero no a lo ancho. No me voy a poner a buscar formas de colorearlo, al menos de momento, porque el hecho de que sea posible pintarlo con menos colores no queiere decir que sea fácil de hacer y menos aún de explicar, pero decir que la última figura necesita 7 colores para ser pintada implicaría que la cara superior (plana) necesitaría 6 colores, todos menos el azul.
    Hay cientos de supuestos contraejemplos parecidos a éste que pretenden negar el teorema de los cuatro colores en dos dimensiones y aunque la construcción sea enrevesada y al principio parezca sólida, está demostrado que existe una alternativa con sólo 4 colores, aunque sea difícil de encontrar.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: El teorema de los cuatro colores asegura que todo mapa plano puede colorearse con,…
  2. ¿Existe algún resultado tipo el teorema de los cuatro colores en tres dimensiones? - [...] ¿Existe algún resultado tipo el teorema de los cuatro colores en tres dimensiones? [...]
  3. ¿Existe algún resultado tipo el t... - [...]   [...]
  4. ¿Existe algún resultado tipo el t... - [...] El teorema de los cuatro colores asegura que todo mapa plano puede colorearse con, a lo sumo, cuatro colores…
  5. Gaussianos cumple 7 años de vida - Gaussianos | Gaussianos - [...] En abril hablamos sobre Bayes y las pruebas de detección de enfermedades, os presentamos a Grace Murray Hopper, la…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *