El algoritmo MST de tiempo lineal esperado (la abreviatura MST procede de la expresión inglesa "minimum spanning tree", "árbol recubridor mínimo" en español) es un algoritmo probabilista para calcular el árbol recubridor mínimo de un grafo ponderado sin vértices aislados. Fue desarrollado por David Karger, Philip Klein y Robert Tarjan. Se basa en técnicas relacionadas con el algoritmo de Borůvka, junto con un algoritmo para verificar un árbol de extensión mínima en tiempo lineal. Combina los paradigmas de diseño del algoritmo divide y vencerás, de un algoritmo voraz y de un algoritmo probabilista para lograr un rendimiento lineal esperado.

Entre los algoritmos deterministas que encuentran el árbol de extensión mínima se incluyen el algoritmo de Prim, el algoritmo de Kruskal, el algoritmo de eliminación inversa y el algoritmo de Borůvka.

Descripción general La clave del algoritmo reside en un paso de muestreo aleatorio que divide un grafo en dos subgrafos seleccionando aleatoriamente aristas para incluir en cada subgrafo. El algoritmo encuentra recursivamente el árbol recubridor mínimo del primer subproblema y utiliza la solución junto con un algoritmo de verificación de tiempo lineal para descartar las aristas del grafo que no pueden formar parte del árbol de extensión mínima. También se utiliza un procedimiento derivado del algoritmo de Borůvka para reducir el tamaño del grafo en cada recursión.

Paso de Borůvka Cada iteración del algoritmo se basa en una adaptación del algoritmo de Borůvka, denominada paso de Borůvka:

Entrada: Un grafo G sin vértices aislados. 1. Para cada vértice v, se selecciona la arista de menor peso incidente en v. 2. Se crea un grafo contraído G´ reemplazando cada componente de G conectado por las aristas seleccionadas en el paso 1 con un único vértice. 3. Se eliminan todos los vértices aislados, bucles y aristas repetitivas no mínimas de G´. Salida: Las aristas seleccionadas en el paso 1 y el grafo contraído G´.

Un paso de Borůvka es equivalente al bucle interno del algoritmo de Borůvka, que se ejecuta en tiempo O(m), donde m es el número de aristas en G. Además, dado que cada arista puede seleccionarse como máximo dos veces (una vez por cada vértice incidente), el número máximo de componentes desconectadas después del paso 1 es igual a la mitad del número de vértices. Por lo tanto, un paso de Borůvka reduce el número de vértices en el grafo al menos a la mitad y elimina al menos n/2 aristas, donde n es el número de vértices en G.

Ejemplo de ejecución de un paso de Borůvka: Imagen DescripciónLa arista más ligera (de menor longitud) que incide en cada vértice se resalta en verde.El grafo se contrae y cada componente conectado por las aristas seleccionadas en el paso 1 se reemplaza por un único vértice. Esto crea dos supernodos. Todas las aristas del grafo original permanecen. Se eliminan las aristas que forman bucles hacia los supernodos.Se eliminan las aristas redundantes no mínimas entre supernodos.El resultado de un paso de Borůvka en el grafo de muestra es un grafo con dos supernodos conectados por una sola arista.

Aristas F-pesadas y F-ligeras En cada iteración, el algoritmo elimina las aristas con propiedades particulares que las excluyen del árbol recubridor mínimo. Estas se denominan aristas F-pesadas y se definen de la siguiente manera. Sea F un árbol en el grafo H. Una arista F-pesada es una arista e que conecta los vértices u y v cuyo peso es estrictamente mayor que el peso de la arista más pesada en el camino de u a v en F (si un camino no existe en F, se considera que tiene peso infinito). Cualquier arista que no sea F-pesada es F-ligera. Si F es un subgrafo de G, entonces ninguna arista F-pesada en G puede estar en el árbol de extensión mínima de G según la propiedad cíclica. Dado un árbol, las aristas F-pesadas se pueden calcular en tiempo linela utilizando un algoritmo de verificación del árbol de extensión mínima.

Algoritmo Entrada: Un grafo G sin vértices aislados. Si G está vacío, devuelve un árbol vacío. Crea un grafo contraído G ejecutando dos pasos sucesivos de Borůvka sobre G. Crea un subgrafo H seleccionando cada arista de G con probabilidad 1/2. Aplica recursivamente el algoritmo a H para obtener su bosque de extensión mínima F.

Elimina de G todas las aristas con alta densidad de F (donde F es el árbol del paso 3) utilizando un algoritmo de verificación de árboles de extensión mínima de tiempo lineal. Aplica recursivamente el algoritmo a G para obtener su árbol de extensión mínima.

Salida: El árbol de extensión mínima de G y las aristas contraídas de los pasos de Borůvka.

Corrección La corrección se demuestra por inducción sobre el número de vértices del grafo. El caso base es trivialmente cierto. Sea T* el árbol de extensión mínima de G. Cada arista seleccionada en un paso de Borůvka pertenece a T* según la propiedad de corte, y ninguna de las aristas eliminadas para formar el grafo contraído pertenece a T* según la propiedad de corte (para aristas redundantes) y la propiedad cíclica (para bucles propios). Las aristas restantes de T* no seleccionadas en el paso 2 forman el árbol recubridor mínimo del grafo contraído según la propiedad de corte (considerando cada corte como un supernodo). Cada condición de arista F-pesada eliminada no pertenece al árbol de extensión mínima según la propiedad cíclica. Finalmente, F' es el árbol de extensión mínima del grafo contraído según la hipótesis inductiva. Por lo tanto, F' y las aristas contraídas de los pasos de Borůvka forman el árbol de extensión mínima.

Rendimiento El rendimiento esperado es resultado del paso de muestreo aleatorio. La efectividad de este paso se describe mediante el siguiente lema, que establece un límite para el número de aristas F-ligeras en G, restringiendo así el tamaño del segundo subproblema.

Lema de muestreo aleatorio Lema'''- Sea H un subgrafo de G formado al incluir cada arista de G de forma independiente con probabilidad p, y sea F el bosque generador mínimo de H. El número esperado de aristas F-ligeras en G es como máximo n/p, donde n es el número de vértices en G.

Para demostrar el lema, se examinan las aristas de G a medida que se añaden a H. El número de aristas F-ligeras en G es independiente del orden en que se seleccionan las aristas de H, ya que el árbol de extensión mínima de H es el mismo para todos los órdenes de selección. Para la demostración, considérese la selección de aristas para H tomando las aristas de G una a una en orden de peso, de la más ligera a la más pesada. Sea e la arista que se está considerando. Si los extremos de e están en dos componentes desconectadas de H, entonces e es la arista más ligera que conecta esas componentes y, si se añade a H, estará en F por la propiedad de corte. Esto también significa que e es una arista F-ligera independientemente de si se agrega o no a H, ya que solo se consideran las aristas más pesadas. Si ambos extremos de e están en el mismo componente de H, entonces es (y siempre será) una arista F-pesada según la propiedad cíclica. La arista e se agrega entonces a H con probabilidad p.

El número máximo de aristas F-ligeras agregadas a H es n-1, ya que cualquier árbol de extensión mínima de H tiene n-1 aristas. Una vez que se han agregado n-1 aristas F-ligeras a H, ninguna de las aristas subsiguientes consideradas es F-ligera según la propiedad cíclica. Por lo tanto, el número de aristas F-ligeras en G está limitado por el número de aristas F-ligeras consideradas para H antes de que n-1 aristas F-ligeras se agreguen realmente a H. Dado que cualquier arista F-ligera se agrega con probabilidad p, esto es equivalente a lanzar una moneda con probabilidad p de que salga. Se lanzan caras hasta que aparezcan n-1 caras. El número total de lanzamientos de moneda es igual al número de aristas F-ligeras en G. La distribución del número de lanzamientos de moneda viene dada por una distribución binomial inversa con parámetros n-1 y p. Para estos parámetros, el valor esperado de esta distribución es (n-1)/p.

Análisis esperado Ignorando el trabajo realizado en subproblemas recursivos, el trabajo total realizado en una sola invocación del algoritmo es lineal en función del número de aristas en el grafo de entrada. El paso 1 requiere tiempo constante. Los pasos de Borůvka se pueden ejecutar en tiempo lineal con respecto al número de aristas, como se menciona en la sección del paso de Borůvka. El paso 3 itera a través de las aristas y lanza una moneda por cada una, por lo que su tiempo es lineal con respecto al número de aristas. El paso 4 se puede ejecutar en tiempo lineal utilizando un algoritmo de verificación de árbol de extensión mínima modificado y lineal. Dado que el trabajo realizado en una iteración del algoritmo es lineal con respecto al número de aristas, el trabajo realizado en una ejecución completa del algoritmo (incluidas todas las llamadas recursivas) está limitado por un factor constante multiplicado por el número total de aristas del problema original y todos los subproblemas recursivos.

Cada invocación del algoritmo produce como máximo dos subproblemas, por lo que el conjunto de subproblemas forma un árbol binario. Cada paso de Borůvka reduce el número de vértices al menos a la mitad, por lo que después de dos pasos de Borůvka el número de vértices se ha reducido a la cuarta parte. Así, si el grafo original tiene n vértices y m aristas, entonces a una profundidad d del árbol, cada subproblema se encuentra en un grafo de como máximo n/4d vértices. Además, el árbol tiene como máximo log4n niveles.

Para analizar el árbol de recursión, sea el problema hijo izquierdo el subproblema en la llamada recursiva del paso 3 y el problema del hijo derecho el subproblema en la llamada recursiva del paso 5. Cuéntese el número total de aristas en el problema original y en todos los subproblemas contando el número de aristas en cada camino izquierdo del árbol. Un camino izquierdo comienza en un hijo derecho o en la raíz e incluye todos los nodos alcanzables a través de un camino de hijos izquierdos. Los caminos izquierdos de un árbol binario se muestran rodeados en azul en el diagrama de la derecha.

Cada arista en un problema hijo izquierdo se selecciona de las aristas de su problema padre (menos las aristas contraídas en los pasos de Borůvka) con probabilidad 1/2. Si un problema padre tiene x aristas, entonces el número esperado de aristas en el problema hijo izquierdo es como máximo x/2. Si x se reemplaza por una variable aleatoria X, entonces por la linealidad de la media, el número esperado de aristas en el problema hijo izquierdo Y viene dado por . Por lo tanto, si el número esperado de aristas en un problema en la parte superior de un camino izquierdo es k, entonces la suma del número esperado de aristas en cada subproblema en el camino izquierdo es como máximo (véase serie geométrica). La raíz tiene m aristas, por lo que el número esperado de aristas es igual a 2m más el doble del número esperado de aristas en cada subproblema derecho.

El número esperado de aristas en cada subproblema derecho es igual al número de aristas F-ligeras en el problema padre, donde F es el árbol de extensión mínima del subproblema izquierdo. El número de aristas F-ligeras es menor o igual al doble del número de vértices en el subproblema, según el lema de muestreo. El número de vértices en un subproblema a profundidad d es n/4d, por lo que el número total de vértices en todos los subproblemas derechos viene dado por . Por lo tanto, el número esperado de aristas en el problema original y en todos los subproblemas es como máximo 2m+n. Dado que n es como máximo 2m para un grafo sin vértices aislados, el algoritmo se ejecuta en un tiempo esperado O(m).

Análisis del peor caso