Árboles de expansión mínima

En 1926, a Otakar Borůvka le pidieron planificar la red eléctrica del sur de Moravia al menor coste posible. Su pregunta, cómo conectar cada lugar con la menor longitud total de línea, es el problema del árbol de expansión mínima, y tiene algunas de las respuestas más sencillas y elegantes de toda la informática.

Un grafo cuyas aristas tienen longitudes, con las aristas cortas de un árbol en crecimiento resaltadas, una arista saltada que cerraría un ciclo discontinua en rojo, y debajo la lista de aristas que quedan por probar
Un grafo cuyas aristas tienen longitudes, con las aristas cortas de un árbol en crecimiento resaltadas, una arista saltada que cerraría un ciclo discontinua en rojo, y debajo la lista de aristas que quedan por probar

El problema

Toma un grafo conexo cuyas aristas tienen longitudes, o costes. Un árbol de expansión es un conjunto de aristas que conecta todos los nodos y no contiene ningún ciclo; con n nodos siempre tiene exactamente n − 1 aristas, porque cada arista conecta un nodo más. De todos los árboles de expansión, un árbol de expansión mínima tiene la menor longitud total. Un grafo puede tener un número enorme de árboles de expansión, pero no hace falta probarlos todos.

Por qué funciona la estrategia voraz

Divide los nodos en dos grupos como quieras. La arista más corta que cruza entre los grupos siempre pertenece a algún árbol de expansión mínima: si un árbol usara en su lugar una arista más larga entre los grupos, cambiarla por la más corta conectaría los mismos nodos por menos. Es la propiedad del corte. La otra cara de la moneda es la propiedad del ciclo: la arista más larga de un ciclo nunca hace falta. Los dos algoritmos de abajo solo aplican estas reglas una y otra vez.

Un ejemplo

Toma las aristas A–B de longitud 1, B–C 2, A–C 3, C–D 4 y B–D 5. El algoritmo de Kruskal toma A–B, luego B–C, luego salta A–C, porque A y C ya están conectados y cerraría un ciclo, y luego toma C–D. El árbol tiene tres aristas para cuatro nodos, así que ha terminado, con longitud total 7, y B–D ni siquiera se mira. El algoritmo de Prim desde A añade primero B por A–B; la arista B–C (2) de B gana a A–C (3) como camino a C, así que C se une por B–C; la arista C–D (4) de C gana a B–D (5), así que D se une por C–D. El mismo árbol, el mismo 7.

Kruskal, Prim y Borůvka

El algoritmo de Kruskal, publicado por Joseph Kruskal en 1956, ordena las aristas y usa una estructura union-find para saltar las aristas dentro de un mismo trozo, así que su trabajo crece con E log E. El algoritmo de Prim lo describió primero Vojtěch Jarník en 1930 y lo redescubrieron Robert Prim en 1957 y Edsger Dijkstra en 1959; con un montículo binario su trabajo crece con E log V, y con un simple array con V², lo que va bien para grafos densos. El algoritmo de Borůvka, de 1926, deja que cada trozo tome a la vez su arista saliente más corta, lo que encaja con los ordenadores paralelos.

Otakar Borůvka en 1981. En 1926 le pidieron planear lo más barato posible la red eléctrica de Moravia meridional, y dio el primer algoritmo de árbol recubridor mínimo.
Otakar Borůvka en 1981. En 1926 le pidieron planear lo más barato posible la red eléctrica de Moravia meridional, y dio el primer algoritmo de árbol recubridor mínimo.

Usos

Los árboles de expansión mínima sirven para diseñar redes baratas de cables, tuberías y carreteras. Agrupan datos en clústeres: quita las aristas más largas del árbol y los trozos que quedan son los clústeres. Dan enseguida una ruta para el problema del viajante que, como mucho, es el doble de larga que la mejor cuando las distancias cumplen la desigualdad triangular. Y el algoritmo de Kruskal o el de Prim sobre una cuadrícula con longitudes de arista aleatorias es una forma clásica de generar un laberinto.

Pruébalo

Abre la aplicación, elige Kruskal o Prim y pulsa Paso. Con Kruskal, las aristas que quedan por probar aparecen bajo el grafo de la más corta a la más larga; las aristas que cerrarían un ciclo se dibujan discontinuas en rojo. Con Prim, aparecen los nodos en espera con la longitud de su mejor arista, que se dibuja discontinua. Ejecuta los dos sobre el mismo grafo y compara: el orden cambia, pero la longitud total siempre es la misma.

Preguntas frecuentes

¿Cuántas aristas tiene un árbol de expansión?

Exactamente una menos que el número de nodos. Con menos aristas no se podrían conectar todos los nodos, y una más siempre crearía un ciclo.

¿Cuál es más rápido, Kruskal o Prim?

El algoritmo de Kruskal, que ordena las aristas, suele ser más sencillo y rápido en grafos dispersos, con pocas aristas. El algoritmo de Prim con un montículo funciona bien en grafos densos, y con un simple array necesita unos V² pasos, haya las aristas que haya.

¿Qué es union-find?

Una estructura de datos que sabe qué nodos están en el mismo trozo. Responde a «¿están conectados estos dos?» y une dos trozos casi al instante, justo lo que el algoritmo de Kruskal necesita para cada arista.

¿Sirve un árbol de expansión mínima para grafos dirigidos?

No tal cual. Para grafos con aristas de un solo sentido, el problema correspondiente es la arborescencia de expansión mínima, que resuelve el algoritmo de Chu–Liu/Edmonds.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Construye un árbol de expansión mínima