El algoritmo de eliminación inversa es un algoritmo en la teoría de grafos que se utiliza para obtener un árbol de expansión mínimo a partir de un gráfico de borde ponderado conectado dado . Apareció por primera vez en Kruskal (1956) , pero no debe confundirse con el algoritmo de Kruskal que aparece en el mismo artículo. Si el gráfico está desconectado, este algoritmo encontrará un árbol de expansión mínimo para cada parte desconectada del gráfico. El conjunto de estos árboles de expansión mínima se denomina bosque de expansión mínima, que contiene todos los vértices del gráfico.
Este algoritmo es un algoritmo codicioso , que elige la mejor opción dada cualquier situación. Es lo contrario del algoritmo de Kruskal , que es otro algoritmo codicioso para encontrar un árbol de expansión mínimo. El algoritmo de Kruskal comienza con un gráfico vacío y agrega bordes, mientras que el algoritmo Reverse-Delete comienza con el gráfico original y elimina los bordes de él. El algoritmo funciona de la siguiente manera:
- Comience con el gráfico G, que contiene una lista de aristas E.
- Pase por E en orden decreciente de pesos de borde.
- Para cada borde, verifique si eliminar el borde desconectará aún más el gráfico.
- Realice cualquier eliminación que no dé lugar a una desconexión adicional.
Pseudocódigo
función ReverseDelete (bordes [] E ) se clasifica E en orden decreciente Definir un índice i ← 0 mientras i < tamaño ( E ) no Definir borde ← E [ i ] de eliminación E [ i ] si el gráfico no está conectado entonces E [ i ] ← borde i ← i + 1 bordes de retorno [] E
En lo anterior, el gráfico es el conjunto de aristas E con cada arista que contiene un peso y vértices conectados v1 y v2 .
Ejemplo
En el siguiente ejemplo, el algoritmo evalúa los bordes verdes y los bordes rojos se han eliminado.
![]() | Este es nuestro gráfico original. Los números cerca de los bordes indican su peso de borde. |
![]() | El algoritmo comenzará con el borde ponderado máximo, que en este caso es DE con un peso de borde de 15. Dado que borrar el borde DE no desconecta más el gráfico, se borra. |
![]() | El siguiente borde más grande es FG, por lo que el algoritmo verificará si eliminar este borde desconectará aún más el gráfico. Dado que eliminar el borde no desconectará más el gráfico, el borde se elimina. |
![]() | El siguiente borde más grande es el borde BD, por lo que el algoritmo comprobará este borde y lo eliminará. |
![]() | El siguiente borde a verificar es el borde EG , que no se eliminará ya que desconectaría el nodo G del gráfico. Por lo tanto, el siguiente borde a eliminar es el borde BC . |
![]() | El siguiente borde más grande es el borde EF, por lo que el algoritmo comprobará este borde y lo eliminará. |
![]() | El algoritmo buscará los bordes restantes y no encontrará otro borde para eliminar; por lo tanto, este es el gráfico final devuelto por el algoritmo. |
Tiempo de ejecución
Se puede demostrar que el algoritmo se ejecuta en tiempo O ( E log V (log log V ) 3 ) (usando notación O grande ), donde E es el número de aristas y V es el número de vértices. Este límite se logra de la siguiente manera:
- La clasificación de los bordes por peso mediante una clasificación de comparación lleva un tiempo O ( E log E ), que se puede simplificar a O ( E log V ) utilizando el hecho de que la E más grande que puede ser es V 2 .
- Hay E iteraciones del bucle.
- Eliminar un borde, verificar la conectividad del gráfico resultante y (si está desconectado) volver a insertar el borde se puede hacer en O (log V (log log V ) 3 ) tiempo por operación ( Thorup 2000 ).
Prueba de corrección
Se recomienda leer primero la prueba del algoritmo de Kruskal .
La prueba consta de dos partes. Primero, se demuestra que los bordes que quedan después de aplicar el algoritmo forman un árbol de expansión. En segundo lugar, se demuestra que el árbol de expansión tiene un peso mínimo.
Árbol de expansión
El sub-gráfico restante (g) producido por el algoritmo no está desconectado ya que el algoritmo verifica eso en la línea 7. El sub-gráfico de resultado no puede contener un ciclo ya que si lo hace, entonces al movernos a lo largo de los bordes encontraríamos el borde máximo. en el ciclo y eliminaríamos ese borde. Por tanto, g debe ser un árbol de expansión del gráfico principal G.
Minimidad
Se demuestra que la siguiente proposición P es cierto por inducción: Si F es el conjunto de aristas mantenido al final del bucle while, entonces hay algún árbol de expansión mínima que (los bordes) son un subconjunto de F .
- Claramente, P se mantiene antes del inicio del ciclo while. dado que un gráfico conectado ponderado siempre tiene un árbol de expansión mínimo y dado que F contiene todos los bordes del gráfico, este árbol de expansión mínimo debe ser un subconjunto de F.
- Ahora suponga que P es cierto para algún conjunto de aristas no final F y sea T un árbol de expansión mínimo que está contenido en F.Debemos mostrar que después de eliminar la arista e en el algoritmo existe algún (posiblemente otro) árbol de expansión T 'que es un subconjunto de F.
- si el siguiente borde eliminado e no pertenece a T, entonces T = T 'es un subconjunto de F y P se mantiene. .
- de lo contrario, si e pertenece a T: primero tenga en cuenta que el algoritmo solo elimina los bordes que no causan una desconexión en la F., por lo que e no causa una desconexión. Pero eliminar e provoca una desconexión en el árbol T (ya que es un miembro de T). suponga que e separa T en los subgráficos t1 y t2. Dado que todo el gráfico está conectado después de eliminar e, entonces debe existir una ruta entre t1 y t2 (que no sea e), por lo que debe existir un ciclo C en F (antes de eliminar e). ahora debemos tener otra arista en este ciclo (llamémosla f) que no está en T pero está en F (ya que si todas las aristas del ciclo estuvieran en el árbol T entonces ya no sería un árbol). ahora afirmamos que T '= T - e + f es el árbol de expansión mínimo que es un subconjunto de F.
- en primer lugar, probamos que T 'es un árbol de expansión . sabemos que al eliminar una arista en un árbol y agregar otra arista que no causa un ciclo obtenemos otro árbol con los mismos vértices. dado que T era un árbol de expansión, T 'también debe ser un árbol de expansión . ya que agregar "f" no causa ningún ciclo ya que se elimina "e" (tenga en cuenta que el árbol T contiene todos los vértices del gráfico).
- en segundo lugar, probamos que T 'es un árbol de expansión mínimo . tenemos tres casos para los bordes "e" y "f". wt es la función de peso.
- wt (f)
dado que T es el árbol de expansión mínimo, esto es simplemente imposible. - wt (f)> wt (e) esto también es imposible. desde entonces, cuando atravesamos los bordes en orden decreciente de pesos de los bordes, debemos ver primero "f". dado que tenemos un ciclo C, eliminar "f" no causaría ninguna desconexión en F., por lo que el algoritmo la habría eliminado de F antes. por lo que "f" no existe en F, lo cual es imposible (hemos demostrado que f existe en el paso 4.
- entonces wt (f) = wt (e) entonces T 'es también un árbol de expansión mínimo . así que nuevamente P se sostiene.
- wt (f)
- entonces P se mantiene cuando el ciclo while está terminado (que es cuando hemos visto todos los bordes) y probamos al final que F se convierte en un árbol de expansión y sabemos que F tiene un árbol de expansión mínimo como su subconjunto. por lo que F debe ser el árbol de expansión mínimo en sí mismo.
Ver también
Referencias
- Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design , Nueva York: Pearson Education, Inc..
- Kruskal, Joseph B. (1956), "Sobre el subárbol de extensión más corto de un gráfico y el problema del viajante de comercio", Proceedings of the American Mathematical Society , 7 (1): 48–50, doi : 10.2307 / 2033241 , JSTOR 2033241.
- Thorup, Mikkel (2000), "Conectividad gráfica totalmente dinámica casi óptima", Proc. 32º Simposio ACM sobre Teoría de la Computación , págs. 343–350, doi : 10.1145 / 335305.335345.