Algoritmo de Boruvka
| ||||||
Algoritmo de Boruvka, es para encontrar el MST (Árbol de expansión mínima) en un grafo ponderado en el que todos sus arcos tienen distinto peso.
Sumario
Historia del Algoritmo de Boruvka
Fue formulado inicialmente por Otakar Boruvka en 1926 quien se dice tuvo que aprender de éste durante la construcción de la red eléctrica de del sur de Moravia.donde él proporcionó una solución para hallar la distribución más económica a través de una red de una línea de energía.
El algoritmo fue redescubierto por Choquet en 1938; de nuevo por Florek, Lukasiewicz, Perkal, Steinhaus y Zubrzycki en 1951; y de nuevo por Sollin a principio de la década de 1960. Debido a que Sollin fue el único de ellos que era científico en computación, este algoritmo es frecuentemente llamado Algoritmo de Sollin.
Otra denominación del Algoritmo de Boruvka
A este algoritmo también se le denomina "el algoritmo de las burbujas". El grafo se cubre por una colección de burbujas y en cada paso cada burbuja se adhiere a su burbuja más cercana.
Caracterización del Algoritmo de Boruvka
ES un algoritmo con una velocidad de convergência (o resolución) bastante rápida siendo ideal para implementación en ordenadores paralelos ya que la Minimum Spanning Tree de cada uno de los subgrafos puede ser calculada en una máquina diferente.
Este algoritmo es recursivo y sólo termina cuando existe sólo un vértice. El algoritmo de Boruvka obtiene un árbol recubridor mínimo en un grafo G ponderado y conexo (no se admiten ponderaciones negativas).
El algoritmo de Boruvka consiste en elegir desde cada vértice la arista de menor peso que sale de él, y así formar al inicio un conjunto de componentes de vértices unidos por dichas aristas.
A partir de entonces en cada paso se busca la arista de menor peso entre los vértices de cada componente y un vértice que no lo sea, es decir, cada componente se unirá a otra distinta. El algoritmo termina cuando todos los vértices del grafo pertenecen a la misma componente.
Pasos del Algoritmo de Baruvka
El Algoritmo de Baruvka comprende los siguientes pasos:
- -Para cada vértice escoger su arco con peso mínimo. De este paso podrán resultar varios subgrafos.
- -Caso el paso 1 dé origen la grafos no conectados, considérese cada subgrafo generado en el paso anterior como un vértice del grafo final. Estos vértices del grafo final contendrán los vértices de cada umdos subgrafos generados en el paso 1. Para cada uno de los subgrafos generados ejecútese de nuevo el paso 1 (recursividade). En este momento se puede, si existan varias máquinas diferentes, correr este algoritmo en las varias máquinas siendo que cada máquina irá a tener assignada a sí uno de los subgrafos generados en el paso 1 (este tipo de distribución de procesamiento es más conocido como Single Instruction Multiple Data ya que cada máquina va a ejecutar las mismas instrucciones pero sobre un conjunto de datos diferentes.
- - Cuando sea encontrada a Minimum Spanning Tree para cada uno de los grafos generar un nuevo grafo donde cada uno vértices de este grafo es uno de los subgrafos. El objetivo ahora será volver a ejecutar los pasos 1 a 3 hasta que existan sólo 2 vértices y un único arco.
Complejidad
Con el Algoritmo de Boruvka se puede obtener una Complejidad de O(log V) iteraciones en el bucle externo antes de terminar, y por lo tanto su Complejidad temporal es O(ElogV), donde E es el número de arcos, y V es el número de vértices de G. En Grafos planos puede implementarse para ejecutarse en tiempo lineal, eliminando los arcos de menor peso entre cada par de nodos después de cada etapa del algoritmo.
Otros Algoritmos
Entre otros Algoritmos para este problema se incluyen el Algoritmo de Prim (realmente descubierto por Vojtech Jarnik) y el Algoritmo de Kruskal. Algoritmos más rápidos pueden ser obtenidos combinando el Algoritmo de Prim con el Algoritmo de Boruvka.
El Algoritmo más rápido para hallar el árbol de recubrimiento mínimo aleatorio está basado en parte en el algoritmo de Boruvka gracias a Karger, Klein y Tarjan y se obtiene una complejidad O(E).
El mejor Algoritmo (determinista) conocido para encontrar el Árbol mínimo de recubrimiento de Bernard Chazelle está también basado en parte en el Algoritmo de Boruvka y tiene complejidad temporal O(Ealfa(V)), donde alfa es la inversa de la Función de Ackermann. Estos algoritmos aleatorios y deterministas combinan pasos del Algoritmo de Boruvka reduciendo el numero de nodos que quedan por conectar, con pasos de diferente tipo que reduzcan el numero de arcos entre cada par de nodos.
Referencia
