Grafos

Un grafo es una red: un conjunto de nodos o vértices unidos por aristas. A diferencia del árbol, aquí no hay raíz, no hay jerarquía y cualquier nodo puede conectarse con cualquier otro. Es el modelo natural de una red de carreteras, de una red de comunicaciones o de las relaciones entre usuarios de una red social.

Un árbol es un caso particular de grafo: un grafo conexo y acíclico en el que se ha designado una raíz.

Las tres medidas del grafo se preguntan juntas y se confunden entre sí, sobre todo porque «orden» y «grado» significan aquí cosas distintas de lo que significaban en los árboles.

En el grafo el orden cuenta vértices; en el árbol el orden era el máximo de hijos por nodo. Es la misma palabra para dos cosas distintas y hay que leer bien el enunciado.

Hay dos formas clásicas y la elección no es de estilo: cambia lo que ocupa el grafo y lo que tarda cada consulta.

La matriz de adyacencia es una tabla de tantas filas y columnas como vértices, donde la celda de la fila i y la columna j indica si existe arista entre esos dos vértices (o cuánto pesa, si el grafo es ponderado). Es inmediata de consultar, pero reserva espacio para todas las conexiones posibles aunque casi ninguna exista, así que desperdicia mucha memoria en grafos grandes y poco conectados.

La lista de adyacencia es un array de vértices en el que cada posición cuelga una lista enlazada con los vecinos de ese vértice. Solo ocupa lo que hay, pero comprobar si dos vértices concretos están unidos obliga a recorrer la lista de uno de ellos.

El problema es el del navegador de un coche: dado un grafo ponderado, encontrar la ruta de menor coste entre dos puntos. Los algoritmos se distinguen por dos cosas: si resuelven un origen contra todos los destinos o todos los pares a la vez, y si admiten pesos negativos.

• Dijkstra: es voraz y va cerrando el vértice más cercano todavía no visitado. Resuelve un origen contra todos los destinos y es el más usado, pero no admite pesos negativos, porque su decisión de dar un vértice por definitivo deja de ser válida.
• Bellman-Ford: también parte de un origen, pero en lugar de decidir en firme relaja repetidamente todas las aristas. Es más lento que Dijkstra y a cambio sí admite pesos negativos, y además detecta si existe un ciclo de peso negativo, en el que el camino mínimo no estaría definido.
• Floyd-Warshall: calcula de una vez el camino mínimo entre todos los pares de vértices del grafo, no solo desde un origen. Su resultado es una matriz completa de distancias.
• Johnson: resuelve también todos los pares admitiendo pesos negativos, pero por otra vía: reajusta los pesos para dejarlos no negativos y después lanza Dijkstra desde cada vértice. Compensa en grafos dispersos.
• A*: es Dijkstra al que se le añade una heurística que estima lo que falta hasta el destino, de modo que explora primero por donde parece prometedor. Es el habitual en videojuegos y en navegación cuando interesa un destino concreto y no todos.
• Viterbi: aplica programación dinámica para hallar la secuencia de estados más probable en un modelo de Markov oculto, problema que equivale a buscar el camino óptimo en un grafo por capas. Se usa en reconocimiento del habla y en decodificación de señales.

Si aparecen pesos negativos, Dijkstra queda descartado: la respuesta es Bellman-Ford si hay un solo origen y Floyd-Warshall o Johnson si se piden todos los pares.

Aquí el problema es otro y conviene no mezclarlo con el anterior. Partiendo de un grafo conexo y ponderado, se busca el subconjunto de aristas que conecta todos los vértices con el menor coste total posible. El resultado es un árbol, porque conectar todo sin ciclos es precisamente lo que define un árbol.

El caso típico es tender una red (cableado, tuberías, fibra) que llegue a todos los puntos gastando el mínimo de material. Los dos algoritmos clásicos son voraces y llegan siempre a un coste total óptimo, aunque el árbol concreto puede variar si hay aristas empatadas.

• Prim: crece desde un vértice inicial. En cada paso añade la arista más barata que une el árbol ya construido con un vértice que aún no está dentro.
• Kruskal: no crece desde ningún sitio. Ordena todas las aristas de menor a mayor y las va aceptando si no forman ciclo, de modo que durante el proceso hay varios fragmentos sueltos que acaban uniéndose.

Camino mínimo y recubrimiento mínimo responden a preguntas distintas: el primero minimiza el coste de ir de un punto a otro, el segundo minimiza el coste total de conectarlo todo. El camino entre dos nodos dentro de un árbol de recubrimiento mínimo no tiene por qué ser el camino mínimo entre ellos.

El problema del flujo máximo trata las aristas como conductos con una capacidad limitada y pregunta cuánto se puede enviar de un origen a un destino sin superar ninguna capacidad. Sirve para dimensionar redes, tráfico o cadenas logísticas.

Ford-Fulkerson lo resuelve buscando repetidamente un camino desde el origen al destino que todavía admita más caudal, aumentando el flujo por él y descontando la capacidad usada. Se repite hasta que no queda ningún camino con capacidad libre. Edmonds-Karp es la versión concreta que elige siempre el camino con menos aristas, buscándolo en anchura, con lo que acota el número de repeticiones.

El algoritmo de Tarjan resuelve algo distinto: en un grafo dirigido, localiza sus componentes fuertemente conexas, que son los grupos de vértices en los que desde cualquiera se puede llegar a cualquier otro y volver. Lo hace en un solo recorrido en profundidad. Es la herramienta para detectar bucles de dependencias, por ejemplo entre módulos de software o entre tareas de un plan.

V es el número de vértices y E el de aristas. Estas cifras son las que explican por qué se elige uno u otro y son las que más se preguntan de este bloque.

Floyd-Warshall es cúbico pero resuelve todos los pares de una vez, así que en un grafo denso puede salir más barato que lanzar Dijkstra desde cada vértice.