Mise à jour d'un Minimum spanning tree lorsqu'un nouveau edge est inséré

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

Laisser G = (V, E) une (non-orienté) graphique avec des coûts ce >= 0 sur les bords eE. Supposons que vous vous êtes donné un coût minimum spanning tree T dans G. Supposons maintenant qu'un nouveau edge est ajouté à G, reliant deux nœuds v, tvV avec des coûts c.

  1. Donner un algorithme efficace pour tester si T reste le coût minimum spanning tree avec la nouvelle arête ajoutée à G (mais pas à l'arbre T). Faire de votre algorithme exécuté en temps O(|E|). Vous pouvez le faire en O(|V|) de temps? Veuillez noter que toutes les hypothèses que vous avez faites sur quelle structure de données est utilisée pour représenter l'arbre T et le graphique G.
  2. Supposons que T n'est plus le coût minimum spanning tree. Donner un linéaire en temps de l'algorithme en temps O(|E|)) pour mettre à jour l'arbre T de la nouvelle de coût minimum spanning tree.

C'est la solution que j'ai trouvé:

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|), tandis que le problème de la demande O(|E|) de temps. Ai-je raté quelque chose?

Par la façon dont nous sommes autorisés à demander l'aide de quelqu'un donc je ne suis pas de la triche 😀

  • Peut-être que je manque quelque chose, sûrement G est connecté, de sorte que |V| <= |E| + 1? Si votre O(|V|) l'algorithme est automatiquement O(|E|) aussi, alors où est le problème? Ou êtes-vous en disant: "je suis surpris, j'ai été en mesure de le résoudre encore mieux que la question m'a demandé"?
  • Oui, quelque chose comme ça! Je suis surpris c'est tellement simple à faire en O(|V|), mais il demande qu'il soit en O(|E|) dans les deux questions. J'ai peur il y a quelque chose que je ne suis pas voyant. J'ai également de donner une preuve de ma solution, et il est évident que si e1 est le plus cher de pointe sur un cycle, alors il ne peut pas être dans le MST, et que si e2 est plus cher de e1 puis e2 ne peut pas être dans le graphique, mais ne peut pas la possibilité d'un nouveau chemin à travers e1 créer une MST avec des bords qui étaient dans G, mais pas dans le précédent MST T?
  • Sauf si vous avez été dit, je ne pense pas que la propriété qu'aucune MST bord peut être le côté le plus long dans un cycle est "évidente". Donc, je ne pense pas que le problème est "trop facile". Re votre preuve question: supposons qu'une telle MST contenant e1 existé. Puis en supprimant e1 laisse 2 composants connectés. Parce que e1 est à l'origine partie d'un cycle, il doit y avoir un autre avantage dans ce cycle qui relie ces 2 composants (prouvant cette partie est laissée en exercice :-P) et qui a du poids < w(e1). Ajouter cette arête à produire une plus petite MST et donc une contradiction. Donc pas de MST contenant e1 peut exister.
  • Mon commentaire précédent ne concerne que le cas où le cycle contient un unique, plus lourde bord. Il s'applique même s'il a été ou sera plusieurs MSTs-pas de MST peut jamais contenir de cette arête. Mais je me rends compte maintenant qu'il n'y a plus de travail à faire si le cycle n'a pas un unique, plus lourde bord... je ne suis pas sûr, que vous ne pouvez pas écarter tous les bords pour sûr. Hmmm.
  • Je suis venu avec la même preuve que vous j_random_hacker et je ne vois pas de problème avec lui, même si il y a plusieurs arêtes de même poids. Ce qui me confond, c'est que je pense que je peux prouver que dans le 2. tout ce que vous devez faire est d'ajouter le nouveau bord et retirer le plus lourd de bord (que ce soit si il y a plusieurs) qui s'exécute en O(|V|).
  • Got maintenant! De mon point de friction est qu'il n'est pas sûr de supprimer un la plus lourde-l'égalité de bord (dans le sens qu'il peut être MSTs contenant que edge) puisque nous ne savons pas pour sûr qu'un avantage peut relier les 2 composants. MAIS: Toutes les MST exige, c'est que, pour tout dédoublement de sommets, nous sélectionnons 1 du minimum-poids des arêtes de découpage qui bip. Donc, étant donné un bip. et un cycle couvrant deux fois, même si les deux couvrant les bords sont plus lourds-l'égalité, soit peuvent être choisis -- les deux vont produire de MSTs. Ainsi, la suppression d'un plus lourd-égalité de bord, vous obtiendrez une MST, mais pas nécessairement tous.
  • Ouais c'est ça. Je me demande encore à propos de la partie 2 si.
  • c'est exactement ce qui a été m'énerve trop... je suis totalement d'accord avec votre solution de la 2ème partie et il semble totalement au travail après un échantillon de quelques essais (aussi, je pense que je peux le démontrer, mais je me trompe peut-être)! @j_random_hacker: merci pour tous vos efforts! Donc, je pense que nous sommes d'accord qu'il doit travailler?
  • Depuis la partie 2 de la question demande une seule MST, alors oui, je crois qu'il devrait travailler. Peut-être que la personne qui pose la question de la pensée, il serait nécessaire de considérer à nouveau chaque bord couvrant les 2 composants que vous obtenez à partir de la suppression d'un plus lourd bord? Cela impliquerait O(E) de temps. Mais ce n'est pas nécessaire, étant donné que nous avons déjà dit que nous sommes à partir d'une MST. Cela signifie que nous savons déjà que tous ceux pré-existants couvrant les bords sont au moins aussi lourd que le bord, nous allons supprimer. Donc, la seule à bord, nous avons besoin à considérer est le nouvellement ajoutée.
  • N'est-ce pas O(V) \O(E)? |E| est borné par |V|^2, donc si il est en O(|V|), il est certainement en O(|E|).

InformationsquelleAutor Lynette | 2010-04-20