La optimización de tiempos ¿replanteada por Shitov?

La teoría de grafos es una rama matemática que profundizó también en las ciencias de la computación, la cual estudia las propiedades de los grafos, que son vértices (o nodos) agrupados por aristas (o arcos) para representar relaciones binarias. Por tal razón, sus aplicaciones llegan incluso a temas relacionados con la Administración y logística, ya que trata acerca de la optimización de recorridos, procesos, flujos, entre otros, que hacen parte del análisis de redes.

El primer ejemplo de la aplicación de la teoría fue intentar resolver el famoso problema de Königsberg: esta ciudad tenía 7 puentes, y sus pobladores se cuestionaban sobre si era posible recorrerlos solo pasando una única vez por todos, partiendo desde su casa y volviendo a ella. El camino no existía, solución propuesta por el famoso matemático alemán Leonhard Euler en 1735.

Gráficamente es más sencillo explicarlo por medio de un ejemplo: tal vez muchos recordarán el problema de dibujar una casa (que es la que está después de este párrafo), partiendo de cualquier vértice, sin levantar el lápiz. Como se podrá dar cuenta el lector, este es un problema sencillo, claro está, de la teoría de grafos.

En Administración, más específicamente en logística, se ha visto mayor grado de aplicación: por ejemplo, optimizar las rutas de un vehículo, la clasificación de objetos u optimizar procesos. En estos dos últimos casos, se podría plantear una variante al problema de la casa, que es el coloreo de redes: las letras deben pintarse con el menor número de colores posible (por lo cual pueden haber dos o más letras del mismo color), pero una arista no puede unir dos letras del mismo color.

Si cada letra es una tarea por terminar por varios trabajadores, y una arista une dos tareas que deben ser realizadas por un mismo operario, y cada color es una destinación de tiempo diferente, entonces el problema puede ser aplicable para optimizar procesos, y se buscará que exista el menor número de colores para lograr ese objetivo.

¿Y si ya no fuera una sino dos casas, y la otra es diferente? ¿cambia el número de colores mínimo al juntarlas? Aunque parezca sencillo, realmente no lo es, ya que crear una teoría para responderlo ha necesitado más de un siglo en hacerlo: solo hasta hace 53 años, y para cierto tipo de grafos, el profesor Stephen Hedetniemi propuso una solución (no demostrada formalmente hasta ahora) a partir de Productos Tensoriales, señalando que ese resultado no puede ser inferior al número de colores usado para alguno de los grafos que intervienen en el cálculo: es decir, si la casa 1 tiene 4 colores y la casa 2 tiene 5, el producto no podrá ser inferior a 4 colores.

Sin embargo, el joven matemático ruso Yaroslav Shitov demostró, con un contraejemplo, que la conjetura de Hedetniemi era falsa y por eso no se había podido probar: es posible encontrar un Producto tensorial con un menor número de colores que el de cada uno de los grafos que intervino, es decir, usando las mismas casas, el producto podría ser 3 colores.

Entonces se plantea una inquietud: si son dos procesos, uno tarda 15 minutos y el otro 12, hasta ahora su producto (bajo ciertas condiciones) debía ser 12 minutos; pero a la luz de lo descubierto por Shitov, parecería que la optimización podría ser incluso inferior a esos 12 minutos. ¿Es posible aplicar esta solución? Solo el propio tiempo lo dirá…