Árbol recubridor mínimo

Dado un grafo conexo y no dirigido, un árbol recubridor, árbol de cobertura o árbol de expansión de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol de expansión mínimo es un árbol recubridor que pesa menos o igual que todos los otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo.

Un ejemplo sería una compañía de cable trazando cable a una nueva vecindad. Si está limitada a trazar el cable por ciertos caminos, entonces se hará un grafo que represente los puntos conectados por esos caminos. Algunos de estos caminos podrán ser más caros que otros, por ser más largos. Estos caminos serían representados por las aristas con mayores pesos. Un árbol recubridor para este grafo sería un subconjunto de estos caminos que no tenga ciclos pero que mantenga conectadas todas las casas. Puede haber más de un árbol recubridor posible. El árbol recubridor mínimo será el de menos coste.

En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá solo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer por inducción. Esto ocurre en muchas situaciones de la realidad, como con la compañía de cable en el ejemplo anterior, donde es extraño que dos caminos tengan exactamente el mismo coste. Esto también se generaliza para los bosques recubridores.

Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total.

Una de las aplicaciones más destacadas del árbol mínimo recubridor se encuentra en el ámbito de las telecomunicaciones, por ejemplo, en las redes de comunicación eléctrica, telefónica, etc. Los nodos representarían puntos de consumo eléctrico, teléfonos, aeropuertos o computadoras. Las aristas podrían ser cables de alta tensión, fibra óptica, rutas aéreas,... .

El Algoritmo de Prim consiste en incrementar el tamaño de un árbol, empezando por un vértice inicial al cual se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto quiere decir que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol. Por tanto, el árbol recubridor mínimo estará completamente construido cuando no queden más vértices por agregar. Los requisitos para proceder con el Algoritmo de Prim son:

• Grafo conexo
• Tener todos los arcos etiquetados

La idea fundamental consiste en añadir en cada paso una arista de peso mínimo a un árbol previamente construido. Para verlo de un modo más explícito, se definen los siguientes pasos:

1. Se elige un vértice U de G y se considera el árbol S={U}.
2. Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e .
3. Si el número de aristas de T es n-1, el algoritmo termina. En caso contrario, volveríamos al paso 2.

• Algoritmo de Prim
• Algoritmo de Kruskal
• Algoritmo de Dijkstra

• Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová (section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's)
• A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, Bernard Chazelle, 1999
• [1]
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 23: Minimum Spanning Trees, pp.561–579.
• Two Algorithms for Generating Weighted Spanning Trees in Order, Harold Gabow, 1977
• State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion, Jason Eisner, 1997

• Implementado en BGL, la "Boost Graph Library"