Teoría de grafos aplicada al camión de la basura o al cartero

Cuando se trata de diseñar recorridos eficientes en una ciudad sin repetir calles, por ejemplo para el camión de la basura o el cartero (por lo del ahorro de tiempo, dinero y contaminación), las matemáticas nos ayudan. De hecho, este es un problema que tiene un papel especial en la historia de las matemáticas por ser el primero que se planteó y resolvió usando Teoría de Grafos, dando lugar al nacimiento de esta disciplina.

Era el siglo XVIII. En una ciudad prusiana llamada Könisberg -actualmente Kaliningrado- situada en la desembocadura del río Pregel había siete puentes. Bueno, hay que decir que la orografía de Könisberg era un tanto especial alrededor de los puentes, ya que la ciudad quedaba dividida en cuatro partes por el Pregel, como se muestra en la siguiente figura:

En aquellos tiempos, alguien formuló la siguiente pregunta: ¿Es posible, comenzando en cualquier sitio de la ciudad de Könisberg, elegir un recorrido que nos permita pasar una única vez por cada uno de los siete puentes sobre el río Pregel? Esta cuestión es conocida como el Problema de los puentes de Könisberg.

Fíjense que en la pregunta anterior no se impone que el punto de inicio coincida con el punto final del recorrido. Esa sería una pregunta diferente: ¿se puede diseñar un circuito, empezando y terminando en el mismo punto de la ciudad, que pase una, y solo una vez, por todos los puentes de Könisberg?

La respuesta a estas dos preguntas se la debemos a uno de los mejores matemáticos de la historia, Leonhard Euler, que dio origen en 1736 así a la Teoría de Grafos. De hecho el resultado no sirve solo para los puentes sobre el Pregel sino para saber muy fácilmente cuándo es posible y cuándo no diseñar un recorrido o un circuito en una ciudad sin pasar dos veces por la misma calle.

En realidad, el problema de los puentes se puede representar como en la siguiente figura: un vértice (punto) por cada zona de la ciudad y una arista (rayita) entre dos de esas zonas por cada puente que las una:

La pregunta sobre Könisberg se transforma en la siguiente pregunta: ¿se puede dibujar ese grafo rojo sin levantar el lápiz del papel y sin repetir ninguna de las líneas? ¿Y empezando y terminando en el mismo vértice?

La respuesta a ambas preguntas es no, según el teorema de Euler. De hecho, en su honor, a los grafos que tienen la propiedad de poder ser recorridos (empezando y terminando en el mismo vértice) sin repetir aristas se les conoce como grafos eulerianos. Pues bien, un grafo es euleriano si -y solamente si- el número de aristas (rayitas) que salen de cada vértices es un número par. Y un grafo tiene un camino euleriano (puede empezar en un vértice y terminar en otro) si -y solamente si- solo tiene dos vértices de los que sale un número impar de aristas.

Si miramos el grafo asociado a los puentes de Könisberg y contamos las aristas que salen de cada vértice, vemos que de todas salen un número impar de estas. Por lo tanto, no es euleriano (no se puede diseñar un circuito -empezando y terminando en el mismo vértice- sin repetir aristas, ni tiene un camino euleriano -empezando y terminando en vértices distintos-).

Aparte del acertijo de los puentes, el estudio del carácter euleriano o no de un determinado grafo tiene aplicaciones a cualquier problema de diseño de rutas que necesiten recorrer todas las calles, como el camión de la basura o el cartero, pero sin pasar más de una vez por ninguna de ellas. Cuando se pueda, claro, porque no siempre se puede: ya hemos dicho que si de algún vértice sale un número impar de aristas, es imposible hacer el circuito, y que si hay más de dos vértices con un número impar de aristas es imposible diseñar ningún recorrido en esas condiciones.

Bueno, y si se puede, ¿cómo lo hacemos? Es decir, si el grafo de mi ciudad tiene un número par de aristas en todos sus vértices, ¿cómo y por dónde pasa el circuito sin repetir calles?

Tenemos un método muy sencillo para hacerlo. Imaginemos que este es el grafo con las calles de nuestra ciudad (es una ciudad muy pequeña pero está bien para el ejemplo):

Si cuentan cuántas aristas salen de cada vértice, comprobarán que en todos hay un número par; se puede hacer, por lo tanto, un circuito euleriano, que pase una -y solo una- vez por cada arista, empezando y terminando en el mismo vértice. En este ejemplo tan simple, uno puede tratar de encontrar ese circuito a simple vista, pero cuando el grafo corresponde a ejemplos reales es mucho  más grande, así que vamos a buscar el circuito con nuestro algoritmo. Bueno, en realidad, con el algoritmo de Carl Hierholzer que, por cierto, fue el que demostró la parte difícil del teorema de Euler (este no lo demostró completo).

Primero buscamos un circuito (o ciclo) simple (no tiene que pasar por todos los vértices) que salga desde, por ejemplo, el vértice 1. El circuito (1,2,3) nos sirve. Llamaremos C al conjunto formado por esos vértices, C={1,2,3}.

A continuación, borramos ese circuito verde y buscamos otro que pase por algunos de los vértices que están ya en C. Por ejemplo, el circuito (1,5,6). Ahora, en el conjunto C, sustituimos el elemento 1, ponemos los elementos (1,5,6,1). Así C={1, 5, 6, 1, 2, 3}.

Borramos, de nuevo, el circuito verde y buscamos otro sencillito que pase por alguno de los vértices de C, (2,5,8), y sustituimos en C, el elemento 2, por (2,5,8,2): C={1, 5, 6, 1, 2, 5, 8, 2,3}.

Borramos el verde y nos quedamos por ejemplo, con el (3,7,8), entonces C={1, 5, 6, 1, 2, 5, 8, 2, 3, 7, 8, 3}. Y por último, el (6,7,4), con lo que C={1, 5, 6, 7, 4, 6, 1, 2, 5, 8, 2, 3, 7, 8, 3}. Ya tienen el circuito que pasa por todos las aristas, sin repetir ninguna, solo tienen que añadir un 1 al final del conjunto C.

Si su grafo no admite circuito euleriano, pero si recorrido, es decir, empezando y terminando en vértices diferentes, será porque tienen dos vértices de valencia impar: los llamamos X e Y. Ahora se inventan un vértice, Z, lo unen a X y a Y en su grafo, y aplican el método que acabamos de explicar. Cuando terminen, borran de C a X y a Y, y ya está, ahí tienen su recorrido.

Ya ven, si cuando les digo que las matemáticas sirven para todo...

Ahora les dejo que comprueben si en su barrio o en su ciudad es posible hacer un circuito de Euler o no.