Grafos: Las Redes que mueven el mundo

Las calzadas romanas, la red eléctrica y, recientemente, Internet. Todas las redes que el ser humano ha diseñado para su comunicación y progreso tienen algo en común: se pueden representar mediante grafos que nos ayudan a modelar y comprender mejor cómo funcionan.

Para entender qué es un grafo, viajemos al año 1736, cuando Leonard Euler publica la solución del “problema de los puentes de Könisberg”.  En él se planteaba cómo cruzar los siete viaductos de la ciudad que vadeaban el río Pregolya, pasando exclusivamente una vez por cada uno. Euler se ayuda de un grafo donde las distintas áreas de la ciudad son los “nodos” o “vértices”, y los puentes que los unen son “aristas” o “arcos”. Recomiendo prestar un minuto de atención a la figura adjunta, donde se puede ver el problema original y su grafo correspondiente. Es más, os animo a coger lápiz y papel, y buscar la solución del dilema.

Nótese que Euler marcó los nodos en Mayúsculas y los arcos en minúsculas

Explosión combinatoria

Encontrar caminos en un grafo tan simple como este puede tomarnos unos minutos en papel y un instante en el ordenador. Podemos escribir todas las combinaciones posibles de arcos que parten de A, y luego ir eliminando los caminos imposibles. Así, descartamos el primero de todos, “a-b-c-d-e-f-g”, porque no se puede ir del arco f al g debido a que nos encontramos en la región B. Antes de que hagáis la lista advierto que hay 7! = 5040 combinaciones. Cuando el tiempo de resolución de un problema depende de un factor exponencial del número de elementos, se llama “np-completo” ( “np” viene de “no polinómico”).

La fuerza bruta del ordenador puede quedarse pequeña a poco que aumentemos el tamaño del grafo. Por suerte, algunos problemas de esta índole se pueden resolver usando métodos análogos que empleen tiempos polinómicos. Nadie ha podido demostrar o refutar que siempre exista esta correspondencia. Es más, se ha convertido en uno de los grandes problemas de las matemáticas, por el que el Clay Mathematics Institute ofrece un millón de dólares a quien consiga una demostración en algún sentido.

¿Qué ocurre en la práctica? Las empresas que necesitan de estas técnicas hacen de tripas corazón y se conforman con una solución que les sea factible, aunque sepan que no es la mejor. Para que se hagan una idea, el problema de Könisberg se simplifica si se permite pasar dos veces por un puente.

Topologías
Según se conecten los nodos tendremos distintas topologías. La más simple es una lista ordenada de objetos, donde un nodo sigue a otro. Si unimos el primero y último de ellos, tendremos un grafo cíclico. En algunos casos necesitamos evitar por todos los medios estos bucles. Cobran así importancia ciertos grafos con una característica muy especial: los árboles.

Como en la naturaleza, un árbol es un grafo que parte de un nodo padre (raíz), y desde éste un único arco (ramas) a cada uno de sus nodos hijos. Esta ley se puede aplicar de nuevo, formando un nuevo nivel de nodos. Un esquema, un análisis sintáctico, un reparto de tareas… hay miles de problemas que se pueden modelar con un árbol.

Podemos representar nuestro problema con un árbol donde las ramas son los puentes y los nodos representan el área donde nos encontramos al atravesarlo. En la figura se muestran dos niveles incompletos del mismo. Si conseguimos llegar al séptimo nivel, habremos encontrado la deseada respuesta.

Para mayor claridad, se han dejado sin desarrollar los nodos marcados con “…”

Mover, pensar, repartir

En la actualidad solo quedan cinco puentes en Könisberg. Pero, ¿Y si fueran levadizos? La configuración del grafo cambiaría dinámicamente. Apenas hemos comenzado a estudiarlos, y los modelos que se han propuesto no satisfacen plenamente las necesidades generadas en la vida real, sobre todo en su aplicación a la estructura de Internet y a la de las redes sociales. Con ello se pretende encontrar nodos aislados o que sean centro de atención, caminos redundantes… Más aún, según la teoría de la percolación estamos aprendiendo más sobre cómo se propagan las catástrofes naturales; algo muy importante para saber cómo detenerlas. Resulta paradójico, pero existe cierto orden en estas redes generadas de forma caótica.

¿Y si a estos nodos les damos capacidad de cómputo? Los investigadores en redes neuronales artificiales, partiendo de un modelo simplificado del comportamiento de estas células del cerebro, han conseguido resolver con solvencia problemas de aprendizaje de patrones, previsión, control, clasificación… y hasta soluciones a problemas np-completos.

Los métodos centralizados, pues, dejan de tener sentido con estos algoritmos distribuidos donde cada nodo realiza una parte de la tarea. De hecho, es así como se computa el camino para encontrar a otro ordenador en Internet, y cada vez más tareas complejas con sencillos ordenadores. De esta forma nació el más pionero de estos programas, el proyecto SETI@home; que pide a los usuarios de Internet el tiempo que está su ordenador inactivo para analizar muestras de señales de radio procedentes del espacio exterior en busca de patrones que den indicios de vida inteligente en su emisión. Aunque no se han encontrado las deseadas señales, el modelo es tan interesante que se ha copiado para otros proyectos científicos.

En casi tres siglos, el estudio de teoría de grafos se ha topado con la complejidad extrema, con problemas irresolubles, o cuya solución abarcan tiempos inaceptables. Hemos comenzado a comprender cómo se comportan estos mecanismos relacionales, y a sacar partido de ello. Las redes dinámicas y los procesos distribuidos son nuestro presente. Estamos continuamente tejiendo hilos que conforman nuestras relaciones profesionales y personales de las que tan solo estamos comenzando a comprender cómo son estas redes, y cómo mueven el mundo.

Nota: Para aquellos que aún no lo han averiguado: El problema de los puentes de Könisberg es irresoluble. No hay forma de pasar una sola vez por cada puente. Su demostración, llena de ingenio imposible de reproducir por las máquinas, puede leerse aquí.

Jorge J. Frías Perles

jorgejfrias