Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarle el uso de la web mediante el análisis de sus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúa navegando, consideramos que acepta nuestra Política de cookies .

Actualidad científica

Síguenos
  • Google+
  • RSS
  • Investigación y Ciencia
  • Febrero 2017Nº 485
Juegos matemáticos

Teoría de grafos

Gratuito

La travesura juvenil de una medallista Fields

Con 19 años, Maryam Mirzakhani obtuvo un resultado en teoría de grafos cuya validez perdura hasta hoy.

Menear
Nota de los editores: El 15 de julio de 2017 nos sorprendió la triste muerte por cáncer de mama de la joven Maryam Mirzakhani (Teherán, 1977), la primera mujer galardonada con la medalla Fields (considerada el equivalente al Nobel de matemáticas), por sus trabajos sobre las superficies de Riemann. El presente artículo recuerda uno de sus primeros éxitos: un resultado en teoría de grafos obtenido cuando solo contaba 19 años.
 
En 2014, durante el último Congreso Internacional de Matemáticos, la catedrática de Stanford Maryam Mirzakhani se convirtió en la primera mujer de la historia galardonada con la medalla Fields, considerada a menudo el «premio Nobel de matemáticas». Su brillante carrera comenzó muy pronto. A continuación repasaremos un resultado en teoría de grafos logrado por la iraní en 1996, cuando aún era una estudiante de 19 años.
 
La República Islámica de Irán no se ha distinguido por la promoción de la ciencia y, desde luego, tampoco por la de la mujer. No obstante, Maryam Mirzakhani, nacida en Teherán en 1977, no se ve como una víctima del sistema. Con ayuda de la directora de su escuela, logró participar en las Olimpiadas Internacionales de Matemáticas de 1994 y 1995. En ambas ocasiones volvió a casa con una medalla de oro. Tras licenciarse en 1999 en la Universidad Tecnológica de Sharif, marchó a Harvard para doctorarse con Curtis McMullen, uno de los medallistas Fields de 1998. En su tesis doctoral de 2004 resolvió preguntas que habían dejado abiertas expertos de la talla de Edward Witten y Maxim Kontsevich, medallistas Fields en 1990 y 1998, respectivamente. Tras estancias en el Instituto Clay de Matemáticas y en Princeton, Mirzakhani es, desde 2008, profesora en Stanford. En 2014 obtuvo la medalla Fields por sus contribuciones al estudio de las superficies de Riemann. [Cortesía de Maryam Mirzakhani, Universidad Stanford]

El trabajo de Mirzakhani parte de una pregunta relacionada con el célebre problema de los cuatro colores. Este puede enunciarse del siguiente modo: dado un mapa geográfico cualquiera, ¿es posible colorear todos los países usando solo cuatro colores, de tal modo que dos naciones del mismo color nunca compartan frontera? (Por «frontera» debemos entender aquí «más que un punto».)

El primer paso para resolverlo consiste en reformularlo en términos de un grafo. Para ello, sustituimos cada país por un punto («vértice») y, después, conectaremos dos de ellos con una línea («arista») si y solo si los países correspondientes son adyacentes. De esta manera, habremos transformado nuestro mapa original en un grafo.

La teoría de grafos constituye un área muy fértil de las matemáticas. Ello se debe a que sus objetos son abstractos (las aristas y los vértices no poseen ninguna propiedad, más allá de que las primeras conectan los segundos), lo que permite derivar todo tipo de resultados. Y, en numerosas aplicaciones, conviene ignorar las características de los objetos y concentrarse solo en sus relaciones.

Por ejemplo, los resultados sobre coloraciones de grafos no afectan únicamente a los cartógrafos. En las redes de telefonía móvil, dos operadores cuyas áreas de influencia se superpongan no deberían utilizar la misma frecuencia si desean evitar interferencias. Una situación similar aparece en el diseño de programas informáticos; en este caso, los recursos limitados del sistema son los registros, los espacios de memoria del procesador que pueden modificarse con gran rapidez y en los que, por ejemplo, se van almacenando las sumas parciales.

Si se trata de mapas, redes de telefonía móvil y otros problemas, los grafos correspondientes son «simples»: contienen un número finito de vértices; ninguna arista conecta un vértice consigo mismo; entre dos vértices cualesquiera no media más que una arista; y estas no poseen características adicionales, como un número o un sentido de recorrido asociado. En este caso, sin embargo, sí habremos de asignar una propiedad a cada vértice: su color. Es como si, en cada vértice, alguien hubiera dispuesto un surtido de botes de pintura y tuviéramos que elegir uno de ellos, satisfaciendo la condición de que dos vértices conectados nunca pueden quedar pintados del mismo color.

En 1976, los matemáticos de la Universidad de Illinois en Urbana-Champaign Kenneth Appel y Wolfgang Haken demostraron, con ayuda de John B. Koch, el teorema de los cuatro colores. Este establece que todo grafo plano (es decir, que pueda representarse en un plano sin que sus aristas se crucen) es «4-coloreable»: puede colorearse usando solo cuatro colores. Por tanto, basta con que en cada vértice se encuentre disponible la misma paleta de cuatro tonalidades.

Dado que una parte considerable de la demostración de Appel y Haken se basaba en cálculos por ordenador, su resultado originó un debate sobre hasta qué punto deberíamos confiar en una prueba semejante. La cuestión quedó definitivamente zanjada en 2005, cuando Georges Gonthier, de Microsoft, y Benjamin Werner, de la Escuela Politécnica de París, presentaron una demostración formal del teorema usando el lenguaje de programación Coq.

Listas de colores

En los comienzos de su carrera, Mirzakhani se ocupó de una versión más enrevesada del problema de los cuatro colores: ¿podemos encontrar una coloración válida (es decir, en la que no haya dos vértices adyacentes del mismo color) si la paleta de colores disponibles es distinta en cada vértice?

El problema puede verse como una partida entre dos jugadores: un pintor, que intenta generar una coloración correcta con los colores suministrados en cada vértice, y un malvado proveedor, que selecciona los botes de pintura precisamente con el propósito de impedirlo. Que gane uno u otro dependerá de la estructura del grafo. Decimos que un grafo es «k-coloreable por listas» si el pintor siempre puede ganar, con la condición de que, en cada vértice, el proveedor suministre exactamente k colores (los cuales puede elegir a voluntad).

Todo grafo k-coloreable por listas es automáticamente k-coloreable, ya que colocar los mismos k colores en cada vértice es una de las opciones a disposición del proveedor, y el pintor tiene respuesta para todas ellas. No obstante, lo contrario no es cierto. A modo de ejemplo, consideremos el primer grafo representado aquí, al que llamaremos K2,4 (véase la figura). Este grafo es 2-coloreable, ya que podemos pintar los vértices de la izquierda de amarillo y los de la derecha de azul. Sin embargo, no es 2-coloreable por listas: resulta sencillo comprobar que, si nuestro proveedor suministra en cada vértice los colores que se muestran en la figura, no podremos encontrar ninguna coloración válida.

 Grafo K2,4: Ejemplo sencillo de un grafo 2-coloreable que, sin embargo, no es 2-coloreable por listas. Con las listas indicadas en la figura, resulta imposible encontrar una combinación en la que no haya dos vértices adyacentes del mismo color. [Christoph Pöppe, según Michael Joswig/Universidad Técnica de Berlín y Benjamin Lorenz]

En 1996, Mirzakhani presentó un grafo plano (y, por tanto, 4-coloreable en virtud del teorema de Appel y Haken) con 63 vértices que, sin embargo, no era 4-coloreable por listas. Paul Erdös, Arthur L. Rubin y Herbert Taylor ya habían sospechado la existencia de este tipo de grafos en 1979, y Margit Voigt, hoy en la Universidad de Ciencias Aplicadas de Dresde, lo había confirmado en 1993 con una estructura con 238 vértices. La construcción de Mirzakhani supuso una mejora, ya que se las arregló con un número considerablemente menor de vértices. Sin embargo, lo más interesante de su grafo es que —a diferencia del de Voigt— también es 3-coloreable, lo que sirvió para dar respuesta a una pregunta que por entonces aún se encontraba abierta. Por último, Carsten Thomassen, de la Universidad Técnica de Dinamarca, demostró que todo grafo plano es 5-coloreable por listas.

De 17 a 63 vértices

¿Cómo encontró Mirzakhani un grafo plano 3-coloreable que no era 4-coloreable por listas? El elemento principal de su construcción es el grafo B que reproducimos aquí (véase la figura). Sus 17 vértices pertenecen a dos clases: los «interiores», con cuatro vecinos y cuatro colores para elegir (los cuales constituyen la paleta completa de colores disponibles), y los «exteriores», con solo tres colores y tres o siete vecinos.

Grafo B: Grafo básico de 17 vértices empleado en la construcción de Mirzakhani. Es 3-coloreable pero no 3-coloreable por listas. Para ver lo primero, basta con pintar todos los vértices «interiores» de rojo y los «exteriores» alternativamente de amarillo y azul. No obstante, no existen coloraciones válidas para las listas mostradas en la figura. [Christoph Pöppe, según Michael Joswig/Universidad Técnica de Berlín y Benjamin Lorenz]

 

Puede verse sin gran esfuerzo que este grafo es 3-coloreable: si, por ejemplo, pintamos todos los vértices interiores de rojo y los exteriores alternativamente de amarillo y azul, no incurriremos en ninguna violación de las reglas. Sin embargo, si nos restringimos a las listas de colores que se indican en la figura, no podremos encontrar ninguna coloración válida. Para asegurarse de ello, en principio nuestro pintor tendría que probar una a una todas las combinaciones posibles. No obstante, es posible proceder más rápido de lo que parece, ya que hay conjuntos de coloraciones que se reducen a otras mediante, por ejemplo, una rotación del grafo y un intercambio de colores.

Una vez disponemos de este componente básico, la construcción del grafo de 63 vértices es sencilla. Primero tomamos cuatro copias de B y otro vértice más, el cual conectaremos con todos los vértices exteriores. Ahora elegimos cuatro nuevos colores, a los que llamaremos a, b, c y d, de manera que haya un total de ocho. En la primera copia de B añadimos a todos los vértices exteriores el color a como cuarto de la paleta; en la segunda incluiremos el color b, y así sucesivamente. Por último, el vértice extra recibirá los cuatro nuevos colores, a, b, c y d. De esta manera, obtenemos un grafo plano con 4×17+1=69vértices, en cada uno de los cuales hay una lista de cuatro colores.

El problema de coloración por listas que acabamos de obtener carece de solución. La razón se debe al papel que desempeña el vértice adicional. Supongamos que lo pintásemos del color a. En tal caso, a estaría prohibido para todos los vértices exteriores de la copia a de B. Por tanto, en este subgrafo nos enfrentaríamos al mismo problema de coloración por listas de B que, más arriba, vimos que carecía de solución. Lo mismo ocurre si al vértice adicional le asignamos uno de los colores restantes.

Así pues, el grafo de 69 vértices que hemos construido no es 4-coloreable por listas. En cambio, sí es fácilmente 3-coloreable. Para verlo, basta con aplicar la coloración mencionada antes a las cuatro copias de B y, después, teñir el vértice adicional de rojo, al igual que los vértices interiores.

Ya casi hemos terminado. Efectuando algunos pequeños retoques, podemos unir entre sí las cuatro copias de B y reducir en 6 el número de vértices. Por último, solo tendremos que modificar hábilmente las listas de colores tal y como indicamos aquí (véase la figura). El resultado es un grafo M con 69 – 6 = 63 vértices y listas de cuatro colores, tomadas de un total de cinco.

Grafo M: Construcción de Mirzakhani. Con 63 vértices, se trata del grafo plano más pequeño conocido que no es 4-coloreable por listas, aunque sí es 3-coloreable. Consta de cuatro copias de B unidas de la manera indicada, así como de un vértice adicional (abajo a la derecha) conectado a cada uno de los vértices exteriores de las copias de B. Para ilustrar su estructura, en las listas de los vértices exteriores de las copias de B se ha marcado con un asterisco el color que determina a qué copia de B pertenece cada vértice. [Christoph Pöppe, según Michael Joswig/Universidad Técnica de Berlín y Benjamin Lorenz]

El nuevo grafo constituye una pequeña joya matemática. Hasta donde sabemos, no ha sido superado aún; es decir, no se conoce ningún grafo de menor tamaño que sea 3-coloreable pero no 4-coloreable por listas. El talento de Mirzakhani queda patente aquí gracias a la sutileza y la sencillez de la construcción.

Puede conseguir el artículo en:

Artículos relacionados

BOLETÍN ACTUALIDAD¿Quieres estar al día de la actualidad científica? Recibe el nuevo boletín de actualidad con nuestros mejores contenidos semanales gratuitos (noticias y posts). Si lo deseas también puedes personalizar tu suscripción. BOLETÍN ACTUALIDAD¿Quieres estar al día de la actualidad científica? ¡Recibe el nuevo boletín de contenidos gratuitos! Ver más boletines.