Un árbol de expansión mínima conecta todos los vértices de un grafo ponderado utilizando aristas del grafo y logrando el menor costo total posible, sin formar ciclos.
Cuando una red ofrece muchas conexiones posibles, quizá no necesitemos conservarlas todas. Si el objetivo es mantener comunicados todos los puntos con el menor costo total de instalación, buscamos un árbol de expansión mínima.
También se lo denomina árbol generador mínimo o MST, por Minimum Spanning Tree. Es una estructura fundamental en diseño de redes, cableado, transporte y agrupamiento de datos.
Un árbol generador de un grafo no dirigido y conectado:
Un grafo puede tener muchos árboles generadores. El MST es aquel cuya suma de pesos es mínima.
Sea G = (V, E) un grafo no dirigido, conectado y ponderado. Un árbol generador T es mínimo si:
Se minimiza el costo total de las aristas elegidas, no la distancia entre un origen y cada destino.
Todo grafo no dirigido, ponderado y conectado tiene al menos un árbol de expansión mínima.
Si el grafo está desconectado, no existe un árbol capaz de cubrir todos sus vértices. En ese caso se obtiene un bosque de expansión mínima, con un MST para cada componente.
A diferencia de Dijkstra, los algoritmos de MST admiten pesos negativos. Una arista negativa simplemente resulta muy conveniente, siempre que su selección no impida formar un árbol.
Como un árbol no contiene ciclos y siempre utiliza V − 1 aristas, no existe el problema de repetir indefinidamente un ciclo para reducir el costo.
Pulsa cerca de las aristas para seleccionarlas. Debes conectar los siete vértices con seis aristas, sin ciclos y con costo total mínimo.
Verde indica un árbol seleccionado, rosa una selección con ciclo y celeste un MST. Los botones de ejemplo se calculan a partir de todas las combinaciones posibles del grafo.
Elegir siempre la arista más barata sin ninguna condición puede formar un ciclo o dejar aislada una parte del grafo. La decisión debe preservar la posibilidad de conectar todos los vértices.
Un corte divide los vértices en dos conjuntos no vacíos. Una arista cruza el corte cuando tiene un extremo en cada lado.
Si esa arista mínima es única, pertenece a todos los MST. Esta propiedad fundamenta las decisiones voraces de Prim y Kruskal.
Supongamos que un MST no contiene la arista mínima e que cruza el corte. Al agregar e aparece un ciclo. Ese ciclo debe contener otra arista f que también cruza el corte.
Podemos eliminar f y conservar la conectividad. Como e no pesa más que f, el nuevo árbol no es más costoso y también es mínimo.
La propiedad complementaria ayuda a descartar aristas:
Si estuviera elegida, podría reemplazarse por otra arista del ciclo de menor peso, manteniendo la conectividad y reduciendo el costo total.
Un grafo puede tener uno o varios árboles de expansión mínima. Si todos los pesos de las aristas son diferentes, el MST es único.
Los pesos repetidos no garantizan múltiples soluciones; solo hacen posible que existan empates.
| Algoritmo | Construcción | Decisión segura |
|---|---|---|
| Prim | Hace crecer un único árbol desde un origen | Arista más barata que sale del árbol |
| Kruskal | Une componentes de un bosque | Arista global más barata que no crea ciclo |
Ambos producen un MST, aunque pueden elegir árboles diferentes cuando hay empates.
Primero debemos verificar que la selección sea un árbol generador. Después se compara su costo con el mínimo conocido.
function esMST(vertices, aristas, conectado, tieneCiclo, costoMinimo) {
const costo = aristas.reduce((suma, arista) =>
suma + arista.peso, 0
);
return conectado &&
!tieneCiclo &&
aristas.length === vertices.length - 1 &&
costo === costoMinimo;
}Tener V − 1 aristas no es suficiente por sí solo: todavía debemos comprobar conectividad o ausencia de ciclos.
Un MST minimiza la suma total del árbol. Un árbol de caminos mínimos minimiza por separado la distancia desde un origen hacia cada vértice.
| Problema | Objetivo | Origen |
|---|---|---|
| Árbol de expansión mínima | Menor costo total para conectar todo | No necesita raíz |
| Árbol de caminos mínimos | Mejores rutas desde una fuente | Sí |
El camino entre dos vértices dentro de un MST no tiene por qué ser el camino mínimo del grafo original.
Si cambia el peso de una arista, el MST puede mantenerse o cambiar. Las propiedades de corte y ciclo ayudan a analizarlo sin recalcular todas las combinaciones.
Enumerar todos los árboles generadores es inviable en grafos grandes. Los algoritmos voraces evitan esa búsqueda exhaustiva.
| Algoritmo | Implementación habitual | Tiempo |
|---|---|---|
| Prim | Lista de adyacencia y montículo | O(E log V) |
| Kruskal | Ordenamiento y Union-Find | O(E log E) |
El árbol de expansión mínima conserva la conectividad global con el menor costo total. Sus propiedades de corte y ciclo justifican algoritmos voraces eficientes y evitan enumerar una cantidad enorme de árboles posibles.
En el próximo tema estudiaremos el algoritmo de Prim, que construye un MST haciendo crecer un único árbol.