Árboles Recubridores Minimales

Árboles recubridores minimales: algoritmos de Kruskal y Prim

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.

Un ejemplo de árbol recubridor mínimo. Cada punto representa un vértice, cada arista está etiquetada con su peso, que en este caso equivale a su longitud.

Aplicaciones

 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,.

Algoritmo de Prim para el árbol recubridor mínimo

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

Algoritmos de Prim.

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.

El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.

El algoritmo podría ser informalmente descrito siguiendo los siguientes pasos:

1. Inicializar un árbol con un único vértice, elegido arbitrariamente del grafo.
2. Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor distancia y unirlo al árbol.
3. Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)

Para hacerlo más en detalle, debe ser implementado el pseudocódigo siguiente.

1. Asociar con cada vértice v del grafo un número C[v] (el mínimo coste de conexión a v) y a un lado E[v] (el lado que provee esa conexión de mínimo coste). Para inicializar esos valores, se establecen todos los valores de C[v] a +∞ (o a cualquier número más grande que el máximo tamaño de lado) y establecemos cada E[v] a un valor "flag"(bandera) que indica que no hay ningún lado que conecte v a vértices más cercanos.
2. Inicializar un bosque vacío F y establecer Q vértices que aún no han sido incluidos en F (inicialmente, todos los vértices).
3. Repetir los siguientes pasos hasta que Q esté vacío:
   1. Encontrar y eliminar un vértice v de Q teniendo el mínimo valor de C[v]
   2. Añadir v a F y, si E[v] no tiene el valor especial de "flag", añadir también E[v] a F
   3. Hacer un bucle sobre los lados vw conectando v a otros vértices w. Para cada lado, si w todavía pertenece a Q y vw tiene tamaño más pequeño que C[w], realizar los siguientes pasos:
      1. Establecer C[w] al coste del lado vw
      2. Establecer E[w] apuntando al lado vw
4. Devolver F

Como se ha descrito arriba, el vértice inicial para el algoritmo será elegido arbitrariamente, porque la primera iteración del bucle principal del algoritmo tendrá un número de vértices en Q que tendrán todos el mismo tamaño, y el algoritmo empezará automáticamente un nuevo árbol en F cuando complete un árbol de expansión a partir de cada vértice conectado del grafo. El algoritmo debe ser modificado para empezar con cualquier vértice particular s para configurar C[s] para que sea un número más pequeño que los otros valores de C (por norma, cero), y debe ser modificado para sólo encontrar un único árbol de expansión y no un bosque entero de expansión, parando cuando encuentre otro vértice con "flag" que no tiene ningún lado asociado.

Hay diferentes variaciones del algoritmo que difieren unas de otras en cómo implementar Q: Como una única Lista enlazada o un vector de vértices, o como una estructura de datos organizada con una cola de prioridades, más compleja. Esta elección lidera las diferencias en complejidad de tiempo del algoritmo. En general, una cola de prioridades será más rápida encontrando el vértice v con el mínimo coste, pero ello conllevará actualizaciones más costosas cuando el valor de C[w] cambie.