El guía turístico vs. el repartidor del supermercado

Tanto el guía turístico cuando planifica la mejor ruta para pasear por el centro de la ciudad, como el repartidor del supermercado cuando decide en que orden entregará los pedidos del día entre sus clientes, se enfrentan a un problema topológico, que aunque parezcan muy similares, son conceptualmente diferentes. ¡Veamos por qué!

El guía turístico

El objetivo del guía es recorrer las calles más emblemáticas de la ciudad evitando pasar dos veces por el mismo sitio para no cansar a los turistas. Si consideramos las calles como aristas y las intersecciones como vértices de un grafo, entonces el problema es equivalente a recorrer todas las aristas del grafo sin repetir volviendo al punto de origen, pero pudiendo pasar por los vértices más de una vez. Su resolución se denomina ciclo euleriano, en honor al matemático Leonhard Euler tras  demostrar que el famoso problema de los puentes de Köningsberg no tenía solución. La formulación del problema decía algo así:

"Dado el mapa de Königsberg (actual Kaliningrado) con el río Pregolya dividiendo el plano en cuatro regiones distintas, que están unidas a través de los siete puentes, ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, de modo de recorrerlas todas pasando sólo una vez por cada puente, y regresando al mismo punto de origen?"

Los puentes de Köningsberg

El problema puede resolverse aplicando un método de fuerza bruta, lo que implica probar todos los posibles recorridos existentes. Sin embargo, Euler en 1736 en su publicación Solutio problematis ad geometriam situs pertinentis demuestra una solución generalizada del problema. Esta abstracción del problema ideada por Euler dio pie a la primera noción de grafo.

Euler determinó que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir más de un único punto conectado con un número impar de líneas.

En particular, como en este diagrama los cuatro puntos poseen un número impar de líneas incidentes, entonces se concluye que es imposible definir un camino con las características buscadas.

El repartidor del supermercado

Por el contrario, el repartidor del supermercado lo que desea es pasar por cada punto de entrega sin repetir para ahorrar tiempo. Haciendo la misma analogía que en el caso del guía, el objetivo es recorrer todos los nodos del grafo una sola vez volviendo al punto de origen, sin tener necesariamente que pasar por todas las aristas. Este problema se conoce como ciclo hamiltoniano, en honor William R. Hamilton, quien inventó el puzzle hamiltoniano, que consiste en encontrar un ciclo hamiltoniano en el grafo de un dodecaedro. El problema fue resuelto usando cuaterniones, que son una extensión de los números reales, algo así como números complejos que en vez de tener una sola unidad imaginaria i, tiene tres llamadas i, j y k. Desgraciadamente, esta solución no se puede generalizar a toods los grafos.

Ciclo hamiltoniano en un dodecaedro

De hecho, no existe una técnica para encontrar caminos hamiltonianos, sino métodos que resuelven casos concretos. Uno de estos métodos se basa en la técnica llamada de coloración de grafos. Apliquemos este método al conocido grafo de Herschel.

Grafo de Herschel

Coloreemos los vértices de dos colores, por ejemplo, rojo y azul, de forma que los vértices rojos sólo se comuniquen directamente con los azules y los azules con los rojos. Nos quedarán así seis vértices rojos y cinco azules. Pues bien, si empezamos por un vértice rojo nuestro última etapa será también de ese color, pero entonces no habrá comunicación con el punto de partida (no están enlazados los puntos del mismo color). Pero si empezamos con un vértice azul (sólo hay cinco) será peor, ya que quedaremos atascados mucho antes de completar el circuito. Por tanto, el grafo de Herschel no tiene ningún ciclo hamiltoniano.