A veces conviene andarse por las ramas...

Ilustración de Raquel Garcia Ulldemolins

CLARA GRIMA.- El 10 de Mayo de 1499 se publicaron las primeras cartas geográficas de Americo Vespucio y no se me ocurre mejor forma de celebrarlo este año que paseando por las calles de Alicante empapándome de Ciencia, ¿no?

Vale, ya sé que no tiene mucho que ver pero no se me ocurría cómo empezar esta entrada.

Pero, ahora que lo pienso, y hablando de mapas y paseos por Alicante, puede que no sea tan descabellada la asociación. A ver, si hay muchos sitios que visitar en este evento y disponemos sólo de 3 días, mucho nos conviene planear la ruta con cierta precaución para llegar lo antes posible a la actividad elegida, ¿no?

Es éste mi momento preferido, en el que la vida me plantea la necesidad de usar un poco de Teoría de Grafos para resolver con eficiencia algún reto.

Puesto que aún no disponemos del programa definitivo de eventos asociados a tan magno acontecimiento científico vamos a simular la situación.

Supongamos que tenemos 11 actividades a las que queremos asistir enmarcadas dentro de las categorías generales de: Astronomía, Cristalografía, Física, Geología, Matemáticas, Microbiología, Nanotecnología, Neurología, Paleontología y Química, por poner un ejemplo.

Vamos a representar en un grafo la situación. Un vértice (punto) por cada una de las áreas mencionadas y aristas indicando las posibles rutas que las unen. En dichas aristas marcaremos además la distancia en metros de dichas ruta. Todo es ficticio, puesto que no disponemos de la información real, todavía.

Supongamos ahora que vivimos justo al lado de la actividad de Oceanografía, o bien que aquí queda el sitio del Beer for Science y vamos a salir desde allí con nuestros amigos. Vamos a construir todos los caminos de recorrido mínimo desde nuestra posición, Oceanografía, hasta cada una de las otras 10 actividades.

El resultado de esta construcción será un árbol, de ahí lo de andarse por las ramas.  Es decir, nos quedaremos con un subconjunto de las aristas del mapa inicial cumpliendo las siguientes condiciones:

• Todos los vértices (actividades) aparecen conectados con esas aristas y se puede ir de uno a cualquier otro paseando por las aristas (ramas) del árbol.
• No se forman ciclos de aristas, es decir, no hay ningún recorrido circular como el que aparece marcado con trazo rojo en la siguiente imagen.

Eso es un árbol en teoría de grafos, un grafo conexo (se puede llegar de un vértice a cualquier otro a través de sus aristas) y sin ciclos.

Pues bien, el árbol que vamos a construir, partirá de Oceanografía y atrapará desde ahí al resto de actividades usando el camino de mínima longitud.

¿Cómo? Allá vamos. 

En un primer paso, vamos a construir una tablita que nos ayudará a conseguir nuestra meta. En dicha tabla y para cada una de las restantes actividades, anotaremos la distancia a Oceanografía en el árbol que estamos construyendo, y el último punto visitado antes de llegar a la citada actividad. Por lo tanto, en la primera tabla tenemos esto:

Las actividades que no están conectadas con Oceanografía, las marcamos a distancia infinito porque aún no tenemos camino para llegar. Entre las que están conectadas con Oceanografía, hay dos a la misma distancia 180 metros, que es la mínima, Paleontología y Geología. Nos quedamos, por ejemplo con la primera.

Hemos coloreado en amarillo todas las actividades accesibles desde Oceanografía  y  Paleontología.

Ya tenemos la primera arista del árbol que tratamos de construir, aparece en verde en la figura anterior. Además, hemos capturado a 2 nuevas actividades a las que podemos llegar pasando por Paleontología: Neurología y Cristalografía, a las cuales les asignaremos en nuestra tabla la suma de las distancias de Oceanografía a Paleontología y de Paleontología a ellas.

Si elegimos el siguiente punto a cazar con nuestro árbol mirando en la columna de distancias a Oceanografía, éste será Geología, que la dejamos mirando antes.

De paso capturamos dos nuevas áreas: Química y Nanotecnología. Actualizamos nuestra tabla para elegir el siguiente vértice del árbol. La distancia que asignamos a Química es la suma de las distancias Oceanografía-Geología y Geología-Nanotecnología, porque, por el momento, es la única ruta posible para llegar hasta allí. Y lo mismo con Nanotecnología.

Y, ¡OJO!, ahora hay dos formas de llegar a Neurología, o bien vía Paleontología (180 m. + 198 m. = 378 m.), o bien vía Geología (180 m. + 267 m. = 447 m.). Nos quedamos con el menor, lógicamente.

Nuestro siguiente invitado, por lo tanto, es Microbiología que, además, nos permitirá llegar a nuestra amada Física.

Tablita al canto, ¿no?

Habría que considerar, para ser rigurosos, las nuevas posibilidades de llegar a Matemáticas, por ejemplo, vía Microbiología y Paleontología, pero son mayores en los dos casos.

Hombre, no es por nada, pero ya tenía ganas de llegar a Matemáticas...

Hay que actualizar la tabla pero, de nuevo, ya hay dos caminos para llegar a Física, a través de Microbiología o de Matemáticas; y dos caminos para llegar a Cristalografía, a través de Paleontología o de Matemáticas. En ambos casos, Física y Cristalografía, nos quedamos con el más corto de ellos.

El siguiente nodo sería, como se deduce de la tabla anterior, Astronomía, que nos aporta, además nuevas rutas hacia Física y Química que habría que tener en cuenta a la hora de actualizar la tabla.

No vamos a reproducir aquí la construcción completa del árbol, se ve como sigue, ¿no?

En cualquier caso, como se trata de un grafo sencillito podéis intentar terminarlo mientras os tomáis un café y hacéis un descanso.

Al final, os quedará el siguiente árbol de recorrido mínimo desde Oceanografía a cualquiera de las otras 10 actividades.

Y todo gracias a nuestro amigo Dijkstra y su algoritmo para caminos mínimos en grafos.

¿Y si vivimos cerca de la 'plaza' de Matemáticas? ¿Cuál sería el árbol que nos daría los recorridos mínimos desde ahí a cualquiera de las otras 10 actividades? Ea, eso da para entretenerse en otro café.

En cualquier caso, vivas donde vivas, lo que es seguro es que si te gusta la ciencia y tienes ganas de pasarlo bien, ese fin de semana de Mayo no puedes encontrar nada mejor que hacer que venir a Alicante.

¡Nos vemos allí!

* Conoce más a la matemática Clara Grima visitando su blog y su excelente y premiado espacio: Mati y sus Matiaventuras.