Actualización de un árbol de expansión mínima cuando se inserta un nuevo borde

Question

he estado presentó el siguiente problema en la Universidad:

Deje G = (V, E) haber un gráfico (no dirigida) con los costos c _e> = 0 en los bordes e ∈ E. Suponga que tiene un árbol de expansión de costo mínimo T en G. Supongamos ahora que un nuevo borde se añade a G, que conecta dos nodos v, t _v ∈ V con coste c.

1. Dale un algoritmo eficiente para probar si T sigue siendo el mínimo costo árbol de expansión con la nueva ventaja añadida a G (pero no al árbol T). Haga que su algoritmo se ejecute en el tiempo O (| E |). ¿Puedes hacerlo en O (| V |) vez? Tenga en cuenta las suposiciones que realice sobre qué estructura de datos se utiliza para representar el árbol T y el gráfico G.
2. Supongamos que T ya no es el árbol de expansión de costo mínimo. Proporcione un algoritmo de tiempo lineal (tiempo O (| E |)) para actualizar el árbol T al nuevo árbol de expansión de costo mínimo.

Esta es la solución que encontré:

Let e1=(a,b) the new edge added 
Find in T the shortest path from a to b (BFS) 
if e1 is the most expensive edge in the cycle then T remains the MST 
else T is not the MST 

Parece que funciona pero puede fácilmente hacer esta carrera en O (| V |) tiempo, mientras que el problema pide O (| E |) hora. ¿Me estoy perdiendo de algo?

Por cierto estamos autorizados a pedir ayuda a nadie, así que no estoy haciendo trampa: D

Answer 1

Creo que su paso Find in T the shortest path from a to b es una operación para E.

Answer 2

Creo que una BFS sería suficiente. Y su complejidad es O (| V | + | E |) pero en un árbol | E | es menor que | V | entonces es O (2 | V |) que es O (| V |)

Answer 3

Tiene la idea correcta, aunque puede hacer mejor que BFS para la búsqueda de ruta más corta si almacena el árbol de la manera correcta .

Di un nodo r en T es la raíz (se puede escoger cualquier nodo y BFS a partir de ahí para generar esta estructura si ha marcado los bordes de árboles en una estructura de matriz gráfica o adyacencia-lista), y cada otro nodo tiene un puntero principal y un recuento de profundidad. Para encontrar el camino más corto entre un y b en T:

1. Deja un ser el nodo 'más profundo'; cambiar si es necesario.
2. Traverse los enlaces de padres de un hasta que se alcanza ya sea b o r, almacenando el camino recorrido, marcando los nodos visitados.
3. Si llega a b, la ruta más corta se atraviesa.
4. Si llega a r, también atraviesa desde b hasta la raíz; si llega al nodo alcanzado en el recorrido desde a a r, deténgase. Únase a los dos donde se encuentran y tiene el camino más corto en T.

La prueba de la validez de este algoritmo se deja como un ejercicio para el lector. Esto es O (| V |) como BFS, pero también generalmente será más rápido. Solo unas pocas configuraciones MST requerirían realmente O (| V |) tiempo en la práctica. Por supuesto, la generación del árbol de enlace padre toma el tiempo O (| V |) para comenzar, por lo que esto solo ayuda en algunas circunstancias, como si usa un algoritmo de construcción de MST que naturalmente crea esta estructura en el proceso de determinar el MST.

Como dijo otro comentarista, tenga en cuenta que si hay un MST para un gráfico, está conectado, entonces | V | < = | E | y por lo tanto O (| V |) < O (| E |).

Además, para arreglar el árbol en el tiempo O (| V |), si es necesario, simplemente busque el borde más largo del ciclo y extráigalo, reemplazándolo con el nuevo borde. Hacer esto de manera eficiente con un MST de enlace para padres también es un ejercicio para el lector.