El algoritmo MST de tiempo lineal esperado es un algoritmo aleatorio para calcular el bosque de expansión mínimo de un grafo ponderado sin vértices aislados . Fue desarrollado por David Karger , Philip Klein y Robert Tarjan . [1] El algoritmo se basa en técnicas del algoritmo de Borůvka junto con un algoritmo para verificar un árbol de expansión mínimo en tiempo lineal. [2] [3] Combina los paradigmas de diseño de algoritmos de divide y vencerás , algoritmos codiciosos y algoritmos aleatorios para lograr el rendimiento lineal esperado .
Los algoritmos deterministas que encuentran el árbol de expansión mínimo incluyen el algoritmo de Prim , el algoritmo de Kruskal , el algoritmo de eliminación inversa y el algoritmo de Borůvka .
La idea clave del algoritmo es un paso de muestreo aleatorio que divide un gráfico en dos subgráficos mediante la selección aleatoria de aristas para incluir en cada subgráfico. El algoritmo encuentra de forma recursiva el bosque de expansión 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 gráfico que no pueden estar en el árbol de expansión mínimo. También se utiliza un procedimiento tomado del algoritmo de Borůvka para reducir el tamaño del gráfico en cada recursión .
Cada iteración del algoritmo se basa en una adaptación del algoritmo de Borůvka denominada paso de Borůvka :
Entrada: Un gráfico G sin vértices aislados 1 Para cada vértice v , seleccione el borde más claro incidente en v 2 Cree un gráfico contraído G' reemplazando cada componente de G conectado por los bordes seleccionados en el paso 1 con un solo vértice 3 Elimine todos los vértices aislados, bucles propios y aristas repetitivas no mínimas de G' Salida: Las aristas seleccionadas en el paso 1 y el gráfico 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 se puede seleccionar como máximo dos veces (una por cada vértice incidente) la cantidad máxima de componentes desconectados después del paso 1 es igual a la mitad de la cantidad de vértices. Por lo tanto, un paso de Borůvka reduce la cantidad de vértices en el grafo en al menos un factor de dos y elimina al menos n /2 aristas donde n es la cantidad 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ínimo . 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 , v cuyo peso es estrictamente mayor que el peso de la arista más pesada en la ruta de u a v en F. (Si una ruta no existe en F, se considera que tiene peso infinito). Cualquier arista que no sea F-pesada es F-liviana . Si F es un subgrafo de G , entonces cualquier arista F-pesada en G no puede estar en el árbol de expansión mínimo de G por la propiedad de ciclo . Dado un bosque, las aristas F-pesadas se pueden calcular en tiempo lineal utilizando un algoritmo de verificación de árbol de expansión mínimo. [2] [3]
Entrada: Un gráfico G sin vértices aislados
Resultado: El bosque de expansión mínimo de G' y los bordes contraídos de los pasos de Borůvka
La corrección se demuestra por inducción sobre el número de vértices en el grafo. El caso base es trivialmente verdadero. Sea T* el árbol de expansión mínimo de G . Cada arista seleccionada en un paso de Borůvka está en T* por la propiedad de corte y ninguna de las aristas eliminadas para formar el grafo contraído está en T* por la propiedad de corte (para aristas redundantes) y la propiedad de ciclo (para bucles propios). Las aristas restantes de T* no seleccionadas en el paso 2 forman el árbol de expansión mínimo del grafo contraído por la propiedad de corte (sea cada corte un supernodo). Cada arista F-pesada eliminada no está en el árbol de expansión mínimo por la propiedad de ciclo . Finalmente, F' es el árbol de expansión mínimo del grafo contraído por la hipótesis inductiva. Por lo tanto, F' y las aristas contraídas de los pasos de Borůvka forman el árbol de expansión mínimo.
El rendimiento esperado es el resultado del paso de muestreo aleatorio. La eficacia del paso de muestreo aleatorio se describe mediante el siguiente lema, que establece un límite en la cantidad de aristas F-light en G, lo que restringe el tamaño del segundo subproblema.
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ínimo de H. El número esperado de aristas F-light en G es como máximo n /p donde n es el número de vértices en G.
Para probar el lema, examine las aristas de G a medida que se agregan a H. El número de aristas F-livianas en G es independiente del orden en que se seleccionan las aristas de H, ya que el bosque de expansión mínimo de H es el mismo para todos los órdenes de selección. Para el bien de la prueba, considere seleccionar aristas para H tomando las aristas de G una a la vez en orden de peso de arista desde la más liviana hasta la más pesada. Sea e la arista actual que se está considerando. Si los puntos finales de e están en dos componentes desconectados de H, entonces e es la arista más liviana que conecta esos componentes y, si se agrega a H, estará en F por la propiedad de corte . Esto también significa que e es F-liviana independientemente de si se agrega o no a H, ya que solo se consideran posteriormente las aristas más pesadas. Si ambos puntos finales de e están en el mismo componente de H, entonces es (y siempre será) F-pesada por la propiedad de ciclo . Luego, la arista e se agrega a H con probabilidad p .
El número máximo de aristas F-light agregadas a H es n -1 ya que cualquier árbol de expansión mínimo de H tiene n -1 aristas. Una vez que se han agregado n -1 aristas F-light a H, ninguna de las aristas posteriores consideradas es F-light por la propiedad de ciclo . Por lo tanto, el número de aristas F-light en G está limitado por el número de aristas F-light consideradas para H antes de que se agreguen realmente n -1 aristas F-light a H. Dado que cualquier arista F-light se agrega 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-light en G. La distribución del número de lanzamientos de moneda está 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 un tiempo constante. Los pasos de Borůvka se pueden ejecutar en un tiempo lineal en el número de aristas como se mencionó 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ínimo 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 (incluyendo todas las llamadas recursivas) está limitado 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 en al menos un factor de dos, por lo que después de dos pasos de Borůvka el número de vértices se ha reducido en un factor de cuatro. Por lo tanto, si el grafo original tiene n vértices y m aristas, entonces en la profundidad d del árbol cada subproblema está en un grafo de como máximo n /4 d vértices. Además, el árbol tiene como máximo log 4 n niveles.
Para razonar sobre el árbol de recursión, supongamos que el problema del hijo izquierdo es el subproblema en la llamada recursiva del paso 3 y el problema del hijo derecho es el subproblema en la llamada recursiva del paso 5. Cuente el número total de aristas del problema original y de todos los subproblemas contando el número de aristas de cada ruta izquierda del árbol. Una ruta izquierda comienza en un hijo derecho o en la raíz e incluye todos los nodos a los que se puede llegar a través de una ruta de hijos izquierdos. Las rutas izquierdas de un árbol binario se muestran en un círculo azul en el diagrama de la derecha.
Cada arista en un problema de 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 expectativa, 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 (ver Series geométricas ). 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-light en el problema padre donde F es el árbol de expansión mínimo del subproblema izquierdo. El número de aristas F-light es menor o igual al doble del número de vértices en el subproblema por el lema de muestreo. El número de vértices en un subproblema a una profundidad d es n /4 d por lo que el número total de vértices en todos los subproblemas derechos está dado por . 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 el tiempo esperado O ( m ).
El tiempo de ejecución del peor caso es equivalente al tiempo de ejecución del algoritmo de Borůvka . Esto ocurre si se agregan todos los bordes al subproblema izquierdo o derecho en cada invocación. En este caso, el algoritmo es idéntico al algoritmo de Borůvka , que se ejecuta en O (min{ n 2 , m log n }) en un gráfico con n vértices y m bordes.
![{\displaystyle E[Y]\leq E[X]/2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc0dc807a5d4830ced01f9dd10946a0f56cd9f82)
