Árboles de Expansión Mínima

Un árbol de expansión mínima conecta todos los vértices de un grafo ponderado y conectado con el menor peso total posible de las aristas; algoritmos voraces como los de Kruskal y Prim lo calculan eficientemente.

Definition

Un árbol de expansión mínima de un grafo conectado y ponderado por aristas es un subconjunto de aristas que conecta todos los vértices, no contiene ciclos y tiene el peso total mínimo entre todos los árboles de expansión de este tipo.

Scope

Este tema abarca el problema del árbol de expansión mínima y sus soluciones voraces clásicas —el algoritmo de Kruskal, que añade aristas en orden de peso creciente utilizando una estructura de conjuntos disjuntos, y el algoritmo de Prim, que hace crecer un único árbol utilizando una cola de prioridad—, junto con las propiedades de corte y ciclo que demuestran la corrección de estos algoritmos. También aborda la estructura de datos de conjuntos disjuntos (unión-búsqueda) que los soporta.

Core questions

• ¿Qué es un árbol de expansión y qué lo convierte en uno de peso mínimo?
• ¿Por qué las adiciones voraces de aristas producen un árbol de expansión globalmente mínimo?
• ¿Cómo justifican la propiedad de corte y la propiedad de ciclo los algoritmos de MST?
• ¿En qué se diferencian los algoritmos de Kruskal y Prim en estrategia y estructuras de datos?
• ¿Cómo hace la estructura de conjuntos disjuntos (unión-búsqueda) que el algoritmo de Kruskal sea eficiente?

Key concepts

• árbol de expansión
• propiedad de corte
• propiedad de ciclo
• algoritmo de Kruskal
• algoritmo de Prim
• conjuntos disjuntos (unión-búsqueda)
• arista segura voraz
• pesos de las aristas

Key theories

Propiedad de corte

Para cualquier partición de los vértices en dos conjuntos, la arista de peso mínimo que cruza la partición pertenece a algún árbol de expansión mínima; esta garantía de arista segura es la base de corrección para los algoritmos voraces de Kruskal y Prim.

Soporte de unión-búsqueda de conjuntos disjuntos

El algoritmo de Kruskal utiliza una estructura de unión-búsqueda con unión por rango y compresión de rutas para probar, en un tiempo amortizado casi constante, si la adición de una arista crearía un ciclo.

Clinical relevance

Los árboles de expansión mínima modelan el diseño de redes de menor costo: el trazado de redes de comunicación, eléctricas o de transporte que conectan todos los sitios de forma económica. También sirven como bloques de construcción en la agrupación (clustering), la segmentación de imágenes, los algoritmos de aproximación para el problema del viajante y el análisis de conjuntos de puntos.

History

El problema del árbol de expansión mínima fue resuelto por primera vez por Otakar Borůvka en 1926 para el diseño de redes eléctricas. Vojtěch Jarník (1930) y, posteriormente, Prim (1957) y Dijkstra desarrollaron el enfoque de crecimiento de árboles, mientras que Kruskal (1956) propuso el método voraz de ordenación de aristas, lo que lo convierte en uno de los problemas de optimización combinatoria más antiguos y mejor comprendidos.

Key figures

• Joseph Kruskal
• Robert Prim
• Otakar Borůvka
• Vojtěch Jarník

Seminal works

• kruskal1956
• cormen2009

Frequently asked questions

¿Cuál es la diferencia entre los algoritmos de Kruskal y Prim?

El algoritmo de Kruskal ordena todas las aristas y las añade en orden de peso creciente, omitiendo cualquiera que forme un ciclo, utilizando la unión-búsqueda para detectar ciclos. El algoritmo de Prim hace crecer un único árbol conectado desde un vértice inicial, añadiendo repetidamente la arista más barata que sale del árbol actual, utilizando una cola de prioridad. Ambos producen un árbol de expansión mínima.

¿Es único el árbol de expansión mínima?

Si todos los pesos de las aristas son distintos, el árbol de expansión mínima es único. Cuando algunos pesos son iguales, puede haber varios árboles de expansión mínima diferentes, todos con el mismo peso total mínimo.