Una serie de problemas de la teoría de grafos se denominan Árbol de extensión mínima. En la teoría de grafos, un árbol es una forma de conectar todos los vértices entre sí, de manera que haya exactamente un camino desde cualquier vértice a cualquier otro vértice del árbol. Si el grafo representa una serie de ciudades conectadas por carreteras, se podría seleccionar un conjunto de caminos de modo que se pueda llegar a cada ciudad desde cualquier otra, pero sin que existan caminos redundantes entre dos ciudades (es decir, sin ciclos).

Definición

Sea G un grafo no dirigido y conexo con un conjunto de aristas que tienen asignados pesos (costes, distancias, tiempos, etc.). Un árbol generador o árbol de expansión de G es un subgrafo que incluye todos los vértices de G y es un árbol (con exactamente |V|-1 aristas). Un árbol generador mínimo (también llamado árbol de expansión mínima o árbol de mínima extensión) es un árbol generador cuyo total de pesos de las aristas es mínimo entre todos los árboles generadores posibles del grafo.

Propiedades clave

  • Existencia: si G es conexo y las aristas tienen peso, siempre existe al menos un árbol generador mínimo.
  • Unicidad: si todos los pesos de las aristas son distintos, el árbol generador mínimo es único. Si hay pesos iguales, pueden existir varios árboles generadores mínimos con el mismo peso total.
  • Propiedad del corte (cut property): para cualquier partición de los vértices en dos conjuntos, la arista de menor peso que conecta ambos conjuntos pertenece a algún árbol generador mínimo.
  • Propiedad del ciclo (cycle property): para cualquier ciclo en el grafo, la arista de mayor peso de ese ciclo no pertenece a ningún árbol generador mínimo (si ese máximo es único).
  • Si el grafo no es conexo, lo que existe es un bosque generador mínimo: el conjunto de árboles generadores mínimos de cada componente conexa.

Algoritmos para encontrar un árbol generador mínimo

Los algoritmos más usados son de tipo voraz (greedy). Los más conocidos:

  • Kruskal: ordena todas las aristas por peso y las añade en orden creciente, siempre que no formen un ciclo con las aristas ya seleccionadas. Suele implementarse con una estructura de conjuntos disjuntos (union-find). Complejidad típica: O(E log E) ≈ O(E log V).
  • Prim: parte de un vértice y va creciendo un árbol añadiendo en cada paso la arista de menor peso que conecta el árbol con el resto del grafo. Implementado con una cola de prioridad (heap) alcanza O(E + V log V) o O(E log V) según implementación.
  • Borůvka: inicialmente considera cada vértice como componente y, en cada fase, añade la arista más barata que sale de cada componente; las fases se repiten hasta unir todo. Es útil en implementaciones paralelas y tiene buen rendimiento asintótico.

Complejidad y consideraciones prácticas

En la práctica la elección entre Kruskal y Prim depende de la representación del grafo (lista de adyacencia, matriz) y del número relativo de vértices y aristas. Para grafos dispersos (E cercano a V) Prim con heap binario o Kruskal con ordenación rápida suelen ser eficientes. Para grafos muy densos, algunas implementaciones de Prim son más adecuadas.

Aplicaciones

  • Diseño de redes (telefonía, electricidad, carreteras) minimizando coste total.
  • Clusterización en análisis de datos (construir un dendrograma mínimo, filtrado en clustering jerárquico).
  • Procesamiento de imágenes y segmentación (algoritmos basados en grafos).
  • Sistemas de distribución y planificación de infraestructuras.
  • Algoritmos aproximados para problemas NP-Hard (por ejemplo, como paso en aproximaciones al viajante).

Ejemplo intuitivo

Imagine varias ciudades conectadas por carreteras con distintos costes de construcción. Un árbol generador mínimo selecciona un subconjunto de carreteras que conecta todas las ciudades y que minimiza el coste total. Si todas las carreteras cuestan lo mismo, cualquier árbol generador es mínimo; si todos los costes son distintos, hay una única selección óptima.

Notas finales

Los conceptos de corte y ciclo y la demostración de corrección de los algoritmos voraces (Kruskal, Prim) se basan en la propiedad de optimalidad local: elegir la arista más barata que no viola la conectividad óptima conduce a una solución global óptima. Los pesos pueden ser negativos; eso no impide definir o encontrar un árbol generador mínimo siempre que el grafo sea conexo. Para grafos dirigidos existe un problema análogo (árbol arborescente de coste mínimo, p. ej. algoritmo de Edmonds) con características distintas.