Árbol generador mínimo (árbol de expansión mínima): definición y conceptos clave
Árbol generador mínimo (árbol de expansión mínima): definición clara y conceptos clave de teoría de grafos, algoritmos y aplicaciones prácticas para optimizar conexiones.
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.
El árbol mínimo de un gráfico plano. Cada arista está etiquetada con su peso, que aquí es aproximadamente proporcional a su longitud.
Encontrar el árbol de expansión mínimo
Un primer intento
Puede ser muy sencillo hacer un algoritmo que descubra un árbol de expansión mínimo:
función MST(G,W): T = {} mientras T no forme un árbol de expansión: encuentra la mínima arista ponderada en E que sea segura para T T = T unión {(u,v)} return TEn este caso, "seguro" significa que al incluir la arista no se forma un ciclo en el gráfico. Un ciclo significa empezar en un vértice, viajar a varios otros vértices y terminar de nuevo en el punto de partida sin utilizar la misma arista dos veces.
Historia
El científico checo Otakar Borůvka desarrolló en 1926 el primer algoritmo conocido para encontrar un árbol de extensión mínima. Quería resolver el problema de encontrar una cobertura eficiente de Moravia con electricidad. Hoy en día, este algoritmo se conoce como el algoritmo de Borůvka. Otros dos algoritmos se utilizan habitualmente en la actualidad. Uno de ellos fue desarrollado por Vojtěch Jarník en 1930, y puesto en práctica por Robert Clay Prim en 1957. Edsger Wybe Dijkstra lo redescubrió en 1959 y lo llamó algoritmo de Prim. El otro algoritmo se llama algoritmo de Kruskal, y fue pulido por Joseph Kruskal en 1956. Los tres algoritmos son codiciosos y se ejecutan en tiempo polinómico.
El algoritmo de árbol mínimo más rápido hasta la fecha fue desarrollado por Bernard Chazelle. El algoritmo se basa en el montón suave, una cola de prioridad aproximada. Su tiempo de ejecución es O(m α(m,n)), donde m es el número de aristas, n es el número de vértices y α es la función clásica inversa de la función de Ackermann. La función α crece muy lentamente, por lo que a efectos prácticos puede considerarse una constante no superior a 4; así, el algoritmo de Chazelle tarda un tiempo muy cercano a la linealidad.
¿Cuál es el algoritmo más rápido posible para este problema? Esta es una de las preguntas abiertas más antiguas de la informática. Está claro que hay un límite inferior lineal, ya que debemos examinar al menos todos los pesos. Si los pesos de las aristas son enteros con una longitud de bits limitada, se conocen algoritmos deterministas con un tiempo de ejecución lineal. Para pesos generales, existen algoritmos aleatorios cuyo tiempo de ejecución esperado es lineal.
El problema también puede plantearse de forma distribuida. Si se considera que cada nodo es un ordenador y que ningún nodo conoce nada más que sus propios enlaces conectados, se puede seguir calculando el árbol de expansión mínimo distribuido.
Preguntas y respuestas
P: ¿Qué es un árbol de extensión mínima en la teoría de grafos?
R: Un árbol de envergadura mínima es un árbol que minimiza los pesos totales asignados a las aristas en la teoría de grafos.
P: ¿Qué es un árbol en la teoría de grafos?
R: Un árbol es una forma de conectar todos los vértices entre sí en la teoría de grafos, de forma que sólo haya un camino desde cualquier vértice a cualquier otro vértice del árbol.
P: ¿Cuál es el propósito de seleccionar carreteras en un escenario de teoría de grafos que representa ciudades?
R: El propósito de seleccionar carreteras en un escenario de teoría de grafos que represente ciudades es permitir que se pueda llegar a cada ciudad desde cualquier otra ciudad, pero sin que haya más de un camino posible para viajar de una ciudad a otra.
P: ¿Puede un grafo tener más de un árbol de expansión?
R: Sí, un grafo puede tener más de un árbol de expansión.
P: ¿Cuál es la diferencia entre un árbol de expansión mínima y otros árboles de la teoría de grafos?
R: Un árbol de expansión mínima minimiza los pesos totales asignados a las aristas, mientras que otros árboles no tienen esta característica.
P: ¿Qué son las aristas en la teoría de grafos?
R: Las aristas son las conexiones entre dos vértices en la teoría de grafos.
P: ¿Puede haber más de un árbol de expansión mínima en un grafo con distintas aristas ponderadas?
R: Sí, dependiendo del aspecto del grafo, puede haber más de un árbol de expansión mínima.
Buscar dentro de la enciclopedia