Una breve incursión en el mundo de los grafos
Más de una vez has debido encontrarte una imagen parecida a ésta. Decenas de puntos, conectados unos a otros en un intrincado patrón. Pero, ¿qué pueden ser? ¿Y por qué son tan importantes?
Esta imagen es un grafo. Y, como explicaremos más adelante, es la manera en que un matemático puede representar y estudiar conexiones. Y es que el estudio de las conexiones ocupa un lugar privilegiado en las matemáticas.
En este artículo explicaremos cómo se estudian formalmente dichas conexiones — mediante grafos -, y por qué los matemáticos están obsesionados con ellos. Para ello, ilustraremos su ubicuidad y utilidad con varios ejemplos y ejercicios.
El arma secreta en las matemáticas para estudiar las conexiones son los grafos.
Los grafos son abstracciones, que convierten situaciones muy distintas a un formato común.
Déjame enseñarte un ejemplo:
¿Familiar? El mapa del metro de Madrid es un grafo, en el que los nodos (puntos) son estaciones, y las aristas (conexiones) son vías de metro.
Otro ejemplo:
Este ejemplo es más abstracto — este es un puzzle de 8 piezas. El puzzle empieza desordenado, y podemos deslizar las piezas para reemplazar el hueco.
Aquí los nodos son los posibles estados del puzzle, y las aristas unen estados que se pueden alcanzar en un único movimiento.
Pero, ¿qué ganamos representando algo como un grafo? ¿Qué tiene este formato común tan importante? Déjame ilustrarlo con dos ejemplos:
Supongamos que somos un transeúnte en Madrid, que quiere encontrar el camino con menos estaciones entre dos puntos
O supongamos que estoy resolviendo el puzzle del 8, y quiero encontrar la secuencia de movimientos más corta que me permitirá ordenar las piezas.
Estos son problemas aparentemente muy distintos. Uno concierne navegar estaciones y trenes, mientras que el otro trata de deslizar piezas en un puzzle.
Pero desde el punto de vista de los grafos, estos dos problemas son iguales. Ambos consisten en encontrar el camino más corto en el grafo. La ruta entre dos nodos que concierne la menor cantidad de nodos intermedios.
En un problema estos nodos corresponden a estaciones ; en el otro corresponden a estados intermedios del puzzle. Representando tanto el metro como el puzzle en este formato abstracto hemos descubierto su estructura común.
Y, aunque no entraré en detalles, matemáticos y científicos de la computación ya hemos estudiado maneras eficaces de resolver este problema en un grafo, que vamos a poder aplicar tanto al metro como al puzzle.
Repito esto: los grafos son un formato común, que revelan cómo muchos problemas siguen un patrón común y por ende pueden ser resueltos de la misma manera.
Ejercicio: te encuentras en Madrid y quieres ir a Valencia. Tu objetivo es pasar por la cantidad mínima posible de peajes durante el viaje. ¿Cómo puedes representar este problema mediante un grafo? ¿Qué problema debes resolver sobre el grafo resultante para resolver el problema inicial? (pista: ¡si te quedas atrancado, intenta hacer un dibujo con carreteras y peajes inventados!)
En la sección anterior partimos de dos problemas concretos que, al abstraer mediante un grafo, se convierten en el mismo problema abstracto.
Quiero ahora ejemplificar el camino contrario: ¿cuál es otro problema abstracto que podemos estudiar en un grafo y qué problemas concretos podemos resolver mediante su solución?
El problema que quiero ilustrar es el problema de encontrar nodos centrales en un grafo.
Por ejemplo, en este grafo tenemos 7 nodos, pero dos de ellos son más centrales que el resto. ¿Sabes cuáles?
El nodo 1 por ejemplo solo tiene dos vecinos. Pero los nodos 0 y 6 tienen cinco vecinos cada uno. En este sentido, los nodos 0 y 6 son más centrales.
¿Pero por qué nos iba a importar encontrar nodos centrales en un grafo?
Consideremos dos ejemplos:
1) Imagina que estás renovando las estaciones de Metro madrid, pero sólo tienes dinero para renovar dos estaciones. ¿Qué estaciones se beneficiarían más?
2) Quieres convencer a algunos de tus contactos en facebook de que promocionen un evento en facebook. Pero convencer a tus amigos toma trabajo, así que solo tendrás tiempo para convencer a dos amigos. ¿A quienes convences para que la promoción llegue al máximo número de personas?
En el primer caso queremos escoger estaciones centrales, que tengan muchas conexiones a otras estaciones. Después de todo, éstas son las que van a ver más tráfico.
En el segundo caso queremos escoger a contactos que tengan respectivamente la mayor cantidad de amigos en Facebook. Después de todo, estos son los contactos que van a tener más influencia.
Espera un momento, ¡es el mismo problema que el grafo! Queremos encontrar los nodos con mayor número de conexiones.
Ejercicio: representa el problema de la promoción en Facebook como un grafo. ¿Que representan los nodos? ¿Qué representan las aristas?
Y así acaba nuestro viaje por el mundo de los grafos.
Hemos visto dos problemas abstractos que podemos resolver usando grafos: encontrar el camino más corto entre dos nodos y encontrar nodos centrales. Muchos otros problemas existen: determinar si existe un camino entre dos nodos, encontrar el camino más corto que recorra todos los nodos de un grafo, determinar si existe un camino que recorra todas las aristas de un grafo sin repetir…
La lección fundamental a aprender: los grafos son una abstracción, que nos ayudan a ver la estructura (y solución) común a problemas muy distintos. Ésta es una lección fundamental en matemáticas que va más allá del estudio de grafos y conexiones.
En un sentido, este el objetivo último de las matemáticas: ocluir los detalles que no importan y poner en relevancia aquellos que sí.
Escrito por Jaime Sevilla, ESR de NL4XAI. Dedicado a Elena Molina, quien además ha servido como editora del artículo.
