Algoritmo MST de tiempo lineal esperado

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 , seleccione la arista más ligera incidente en v. 2 Cree un grafo contraído G' reemplazando cada componente de G conectado por las aristas seleccionadas en el paso 1 con un solo vértice. 3. Eliminar 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 ser seleccionada 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

En cada iteración, el algoritmo elimina las aristas con propiedades particulares que las excluyen del árbol de expansión mínima . Estas se denominan aristas F-pesadas y se definen de la siguiente manera: Sea F un bosque 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 expansión mínima de G debido a la propiedad de ciclo . Dado un bosque, las aristas F-pesadas se pueden calcular en tiempo lineal utilizando un algoritmo de verificación del árbol de expansión mínima. ^{[ 2 ] [ 3 ]}

Lema - Sea H un subgrafo de G formado al incluir cada arista de G independientemente con probabilidad p y sea F el bosque de expansión mínima 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, examinemos las aristas de G a medida que se agregan 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 bosque de expansión mínima de H es el mismo para todos los órdenes de selección. Para efectos de la demostración, consideremos seleccionar aristas para H tomando las aristas de G una por una en orden de peso de arista de la más ligera a la más pesada. Sea e la arista que se está considerando actualmente. 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 agrega a H, estará en F por la propiedad de corte . Esto también significa que e es F-ligera independientemente de si se agrega o no a H, ya que solo se consideran posteriormente las aristas más pesadas. Si ambos extremos de e están en la misma componente de H , entonces es (y siempre será) F-pesada por la propiedad de ciclo . La arista e se agrega entonces a H con probabilidad p .

El número máximo de aristas F-ligeras añadidas a H es n -1 ya que cualquier árbol de expansión mínima de H tiene n -1 aristas. Una vez que se han añadido n -1 aristas F-ligeras a H, ninguna de las aristas subsiguientes consideradas es F-ligera por la propiedad de ciclo . 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 se añadan realmente n -1 aristas F-ligeras a H. Dado que cualquier arista F-ligera se añade con probabilidad p, esto es equivalente a lanzar una moneda con probabilidad p de que salga cara hasta que hayan aparecido 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 la 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 .

Ignorando el trabajo realizado en subproblemas recursivos, la cantidad total de trabajo realizado en una sola invocación del algoritmo es lineal en el número de aristas en el grafo de entrada. El paso 1 toma tiempo constante. Los pasos de Borůvka se pueden ejecutar en tiempo lineal en el número de aristas como se menciona en la sección de pasos de Borůvka . El paso 3 itera a través de las aristas y lanza una sola moneda para cada una, por lo que es lineal en el número de aristas. El paso 4 se puede ejecutar en tiempo lineal utilizando un algoritmo de verificación de árbol de expansión mínima de tiempo lineal modificado. ^{[ 2 ] [ 3 ]} Dado que el trabajo realizado en una iteración del algoritmo es lineal en el número de aristas, el trabajo realizado en una ejecución completa del algoritmo (incluidas todas las llamadas recursivas) está acotado por un factor constante multiplicado por el número total de aristas en el 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, de modo que después de dos pasos de Borůvka el número de vértices se ha reducido a la cuarta parte. Por lo tanto, 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 log₄n _niveles .

Para analizar el árbol de recursión, consideremos el problema del hijo izquierdo como el subproblema en la llamada recursiva del paso 3 y el problema del hijo derecho como el subproblema en la llamada recursiva del paso 5. Contemos el número total de aristas en el problema original y en todos los subproblemas, contando el número de aristas en cada ruta izquierda del árbol. Una ruta izquierda comienza en un hijo derecho o en la raíz e incluye todos los nodos alcanzables a través de una ruta de hijos izquierdos. Las rutas izquierdas de un árbol binario se muestran rodeadas con un círculo 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 esperanza el número esperado de aristas en el problema hijo izquierdo Y viene dado por${\displaystyle E[Y]\leq E[X]/2}$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${\displaystyle \sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k}$(véase la serie geométrica ). La raíz tiene m aristas, por lo que el número esperado de aristas es igual a 2 m 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 expansió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 /4 ^d , por lo que el número total de vértices en todos los subproblemas derechos viene dado por${\displaystyle \sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2}$. Por lo tanto, el número esperado de aristas en el problema original y todos los subproblemas es como máximo 2 m + n . Dado que n como máximo 2 m para un grafo sin vértices aislados, el algoritmo se ejecuta en un tiempo esperado O ( m ).

El tiempo de ejecución en el peor de los casos es equivalente al del algoritmo de Borůvka . Esto ocurre si se añaden todas las aristas al subproblema izquierdo o derecho en cada invocación. En este caso, el algoritmo es idéntico al ^de Borůvka , que se ejecuta en O (min{ n² , m log n }) en un grafo con n vértices y m aristas.