un arbre couvrant minimum lorsqu'un nouveau bord est inséré

Question

J'ai présenté le problème suivant à l'Université:

Soit G = (V, E) un graphe (non orienté) avec des coûts c _e> = 0 sur les bords e ∈ E. Supposons que vous obtenez un arbre recouvrant un coût minimal T dans G. Supposons maintenant qu'un nouveau bord est ajouté à G, reliant deux noeuds v, t _v ∈ V avec coût c.

1. Donnez un algorithme efficace pour tester si T reste l'arbre de recouvrement minimum coût avec le nouveau bord ajouté à G (mais pas à l'arbre T). Faites fonctionner votre algorithme dans le temps O (| E |). Pouvez-vous le faire en temps O (| V |)? Veuillez noter toutes les hypothèses que vous faites sur la structure de données utilisée pour représenter l'arbre T et le graphique G.
2. Supposons que T ne soit plus l'arbre recouvrant le coût minimal. Donner un algorithme linéaire (temps O (| E |)) pour mettre à jour l'arbre T vers le nouvel arbre recouvrant le coût minimum.

Ceci est la solution que je trouve:

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 

Il semble fonctionner, mais je peux facilement faire cette course en O (| V |) temps, alors que le problème demande O (| E |) temps. Est-ce que je manque quelque chose?

Par ailleurs, nous sommes autorisés à demander de l'aide de quelqu'un donc je ne triche pas: D

Answer 1

Je crois que votre étape Find in T the shortest path from a to b est une opération E de commande.

Answer 2

Je pense qu'un BFS suffirait. Et sa complexité est O (| V | + | E |) mais dans un arbre | E | est inférieur à | V | C'est O (2 | V |) qui est O (| V |)

Answer 3

Vous avez la bonne idée, même si vous pouvez faire mieux que BFS pour la recherche du plus court chemin si vous stockez l'arbre correctement .

Say un noeud r dans T est la racine (on peut choisir n'importe quel noeud et BFS à partir de là pour générer cette structure si vous avez marqué les bords de l'arbre dans une matrice ou une structure de graphe liste d'adjacence), et chaque autre noeud a un pointeur parent et un compte de profondeur. Pour trouver le chemin le plus court entre un et b dans T:

1. Laissez un le nœud 'plus profond'; échanger si nécessaire.
2. Traverse les liens parent de un jusqu'à ce que soit b ou r est atteinte, le stockage du chemin parcouru, le marquage des noeuds visités.
3. Si vous atteignez b, le chemin le plus court est tel que traversé.
4. Si vous atteignez r, passez également de b à la racine; si vous atteignez le noeud atteint dans la traversée de un à r, arrêtez. Joignez-vous aux deux où ils se rencontrent et vous avez le plus court chemin dans T.

La preuve de la validité de cet algorithme est laissée au lecteur en tant qu'exercice. C'est O (| V |) comme BFS, mais sera aussi généralement plus rapide. Seules quelques configurations MST nécessiteraient en fait O (| V |) temps en pratique. Bien sûr, la génération de l'arbre parent-lien prend l'heure O (| V |), donc cela ne sert que dans certaines circonstances, comme si vous utilisiez un algorithme de construction MST qui crée naturellement cette structure dans le processus de détermination de MST. Comme un autre commentateur l'a dit, notez que s'il y a un MST pour un graphe, il est connecté, alors | V | < = | E | et donc O (| V |) < O (| E |).

De même, pour fixer l'arbre en temps O (| V |), si nécessaire, trouvez simplement le plus long bord du cycle et retirez-le en le remplaçant par le nouveau bord. Faire cela efficacement avec un MST parent-lien est aussi un exercice pour le lecteur.