El pasado 29 de septiembre, participamos en la Noche Europea de los Investigadores, en Almería, con un taller sobre Problemas de Grafos y Aplicaciones en Realidad Virtual.
En este taller, propusimos a los visitantes varios problemas famosos de grafos sobre el papel, y también en el espacio, utilizando el software de realidad virtual Neotrie VR.
La teoría de grafos es de gran utilidad para plantear y resolver problemas de la vida cotidiana, que puedan modelarse mediante grafos. Un grafo es esencialmente una estructura formada por nodos (vértices) y conexiones entre ellos (aristas). En nuestro stand, os invitaremos a colorear grafos, a encontrar caminos eulerianos y ciclos hamiltonianos, entre otros juegos divertidos.
Uno de los problemas más importantes de coloración de grafos es el teorema de los 4 colores, gracias al cual, podemos colorear cualquier mapa con tan solo 4 colores, de forma que países fronterizos tengan diferente color. ¿Os animáis a colorear mapas en papel? ¿Y si os damos poliedros y otras figuras 3D en realidad virtual? En ese caso, habrá mapas que necesitarán 5 o más colores, como ya veréis.
El problema de encontrar caminos eulerianos tiene su origen en el famoso problema de los 7 puentes de Königsberg. El reto, que resolvió exitosamente Leonard Euler, consistía en pasear por los 7 puentes sin pasar dos veces por el mismo. Traducido a un problema de grafos, os propondremos dibujar grafos sin levantar el lápiz del papel, y en el espacio, en realidad virtual, tendremos grafos que habrá que dibujar de un solo trazo.
El problema del viajante hace referencia a la situación a la que se enfrentan diariamente los comerciantes, cuando tienen que visitar sus tiendas sin repetir. La versión en grafos consiste en encontrar un camino, llamado hamiltoniano, que pasa por todos los vértices, pero solamente una vez.
