Tema
Árbol de expansión mínima
- Algoritmos
- Nivel intermedio
Un árbol de expansión mínima conecta todos los vértices de un grafo no dirigido con peso total mínimo y sin formar ciclos.
Nombre en inglés
Minimum spanning tree
Intuición
La propiedad del corte lo explica todo: Al partir los vértices en dos grupos cualesquiera, la arista más ligera que los cruza pertenece a algún árbol mínimo. Kruskal recorre las aristas de menor a mayor y acepta la que no cierre ciclo, mientras que Prim hace crecer un único árbol desde un vértice. Los dos son voraces y los dos son correctos por la misma razón.
Fórmula
n vertices dan n - 1 aristas ; Kruskal O(E log E) con conjuntos disjuntos ; Prim O(E log V) con monticulo
Ejemplo resuelto
Con cuatro vértices y aristas AB de peso 1, BC de peso 2, CD de peso 3 y AD de peso 4, Kruskal toma AB, después BC y después CD. La arista AD se descarta porque cerraría un ciclo. El peso total vale 1 más 2 más 3, es decir 6, y el árbol tiene 3 aristas, una menos que el número de vértices.
Errores frecuentes
- Suponer que el árbol mínimo contiene los caminos mínimos: Son objetivos distintos, y el camino entre dos vértices dentro del árbol puede resultar más largo que el camino mínimo del grafo.
- Olvidar la comprobación de ciclo en Kruskal: Sin la estructura de conjuntos disjuntos, el resultado deja de ser un árbol.
- Dar por única la solución: Con pesos repetidos puede haber varios árboles mínimos, aunque el peso total siempre coincide.
Ejercicio
Un grafo conexo tiene 9 vértices. ¿Cuántas aristas tiene cualquiera de sus árboles de expansión?
Ver la solución
Un árbol con n vértices tiene siempre n menos 1 aristas, y aquí n vale 9.
Respuesta: 8