Algoritmo de eliminación inversa

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 ponderado de línea conectado dado . El algoritmo apareció por primera vez en el artículo de Kruskal [1] , pero no debe confundirse con el algoritmo de Kruskal , que apareció en el mismo artículo. Si el gráfico no está conectado, este algoritmo encontrará el árbol de expansión mínimo para cada parte 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.

El algoritmo es un algoritmo codicioso que da la mejor solución. Es lo opuesto al algoritmo de Kruskal , que es otro algoritmo de árbol de expansión mínimo codicioso. El algoritmo de Kruskal comienza desde un gráfico vacío y agrega bordes, mientras que el algoritmo de eliminación inversa comienza desde el gráfico original y elimina los bordes. El algoritmo funciona así:

Empezamos con el gráfico G, que contiene una lista de aristas E.
Pasamos por E en orden descendente de pesos de borde.
Para cada borde, verificamos si su eliminación no conduce a un gráfico desconectado.
Realizamos borrados que no conducen a la desconexión de la gráfica.

Pseudocódigo

1 función ReverseDelete (bordes [] E ) 2 ordenar E en orden descendente 3 Determinar el índice i ← 0 4 mientras i < tamaño ( E ) 5 Definir un borde ← E [ i ] 6 eliminar E [ i ] 7 si la gráfica no es conexa 8 E [ i ] ← arista 9 i ← i + 1 10 aristas de retorno [] E

Ejemplo

En el siguiente ejemplo, el algoritmo busca los bordes verdes y el algoritmo elimina los bordes rojos.

	Este es el gráfico original. Los números junto a los bordes reflejan el peso de los bordes.
	El algoritmo comienza con el borde con el peso máximo, en este caso el borde DE con peso 15. Dado que eliminar el borde DE no da como resultado un gráfico desconectado, se elimina el borde.
	El siguiente borde más pesado es FG , por lo que el algoritmo verificará si eliminar el borde conduciría a la desconexión. Dado que eliminar un borde no hace que el gráfico se desconecte, se elimina el borde.
	El siguiente borde más pesado es BD , por lo que el algoritmo verifica si eliminar el borde lo desconectaría y lo eliminaría.
	La siguiente arista a verificar es EG , que no se puede eliminar, ya que esto conducirá a la separación del vértice G del gráfico. Por lo tanto, la siguiente arista a eliminar es BC .
	El siguiente borde más pesado es EF , por lo que el algoritmo verificará este borde y lo eliminará.
	El algoritmo busca a través de los bordes restantes y no encuentra ninguno adecuado para eliminar, por lo que este es el gráfico final que devuelve el algoritmo.

Horario de apertura

Se puede demostrar que el algoritmo se ejecuta en el tiempo ( "O" es grande y "o" es pequeño ), donde E es el número de aristas y V es el número de vértices. Este límite se alcanza de la siguiente manera: $O(E\log V(\log \log V)^{3})$

Clasifique los bordes por peso utilizando la clasificación por comparación, que se ejecuta en el tiempo , que puede reducirse a usar el hecho de que el borde más pesado E está en V 2 . $O(E\log E)$ $O(E\log V)$
Hay E iteraciones del ciclo.
Las operaciones de eliminar un borde, verificar la conexión del gráfico resultante y (si el gráfico está desconectado) insertar un borde se pueden realizar en el tiempo de operación [2] . $O(\log V(\log \log V)^{3})$

Prueba de corrección

Se recomienda leer primero la prueba del algoritmo de Kruskal .

La prueba consta de dos partes. Primero, se prueba que las aristas que quedan después de ejecutar el algoritmo toman la forma de un árbol de expansión. Entonces se prueba que este árbol de expansión tiene un peso óptimo.

Árbol de expansión

El subgrafo restante (g) obtenido por el algoritmo es conexo, ya que el algoritmo verifica esto en la línea 7. El subgrafo no puede contener un ciclo, porque de lo contrario, moviéndose a lo largo del ciclo, puede encontrar el borde con el mayor peso y eliminarlo. Entonces g debe ser un árbol generador del grafo principal G.

Minimalidad

Mostraremos por inducción que el siguiente enunciado P es verdadero: si F es el conjunto de aristas que quedan al final del ciclo, entonces existe un árbol generador mínimo que (sus aristas) es un subconjunto de F .

Está claro que P se ejecuta antes del inicio del bucle 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 intermedias F y sea T el árbol de expansión mínimo que está contenido en F . Debemos demostrar que después de eliminar la arista e en el algoritmo, existe un árbol de expansión T' (posiblemente diferente) que es un subconjunto de F.
1. si la siguiente arista eliminada e no pertenece a T, entonces T=T' es un subconjunto de F y se satisface P.
2. de lo contrario, si el borde e pertenece a T: primero tenga en cuenta que el algoritmo elimina solo los bordes F.destrucciónno provocan laque Suponga que e descompone T en subgrafos t1 y t2. Dado que todo el gráfico permanece conectado después de eliminar e , debe haber un camino entre t1 y t2 (que no sea e ), por lo que debe haber un ciclo C en F (antes de eliminar e ). Ahora debemos tener otra arista en este ciclo (que sea f) que no pertenezca a T pero que esté en F (porque si todas las aristas del ciclo estuvieran en el árbol T, no sería un árbol). Ahora afirmamos que T' = T - e + f es un árbol generador mínimo que es un subconjunto de F.
3. Primero probamos que T' es un árbol de expansión . Sabemos que eliminar un borde en un árbol y agregar otro borde no crea un ciclo y 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 . Luego, agregar "f" no crea ningún ciclo, ya que se elimina "e" (observe que el árbol T contiene todos los vértices del gráfico).
4. Luego demostramos que T' es un árbol generador de mínimos . Tenemos tres casos para las aristas "e" y "f" definidas por la función de peso wt.
  1. El caso wt(f) < wt(e), que es imposible porque implica que el peso de T' es estrictamente menor que T. Dado que T es un árbol de expansión mínimo, esto simplemente no es posible.
  2. El caso es wt(f) > wt(e), lo cual es imposible porque cuando recorremos los bordes en orden descendente de pesos, deberíamos ver "f" primero. Dado que tenemos C, eliminar "f" no conduce a la desconexión en F, por lo que el algoritmo tendría que eliminar un borde de F antes. Es decir, "f" no pertenece a F, lo cual es imposible (probamos que f pertenece en el paso 4).
  3. Caso wt(f) = wt(e), por lo que T' es un árbol generador mínimo , por lo que nuevamente se satisface P.
Entonces, P se ejecuta después de que finaliza el bucle (es decir, después de que se han examinado todos los bordes) y hemos demostrado que al final F se convierte en un árbol de expansión y sabemos que F tiene un árbol de expansión mínimo como subconjunto, por lo que F debe ser en sí mismo un árbol de expansión mínima .

Véase también

Enlaces

Jon Kleinberg, Eva Tardós. Diseño de algoritmos. — Nueva York: Pearson Education, Inc., 2006.
José B. Kruskal. Sobre el subárbol de expansión más corto de un gráfico y el problema del vendedor ambulante // Actas de la Sociedad Matemática Estadounidense . - 1956. - T. 7 , núm. 1 . — S. 48–50 . -doi : 10.2307/ 2033241 . — .
Mikkel Thorup. Conectividad gráfica totalmente dinámica casi óptima // Proc. 32º Simposio ACM sobre Teoría de la Computación . - 2000. - S. 343-350. -doi : 10.1145/ 335305.335345 .