Algorithme reverse-delete

En informatique, l'algorithme reverse-delete[1] (litt. « inverse-supprime ») est un algorithme de recherche d'arbre couvrant minimum dans un graphe connexe non-orienté et pondéré. Il a été introduit en 1956 par Joseph Kruskal[2] en même temps que l'algorithme de Kruskal qui résout le même problème.

L'algorithme reverse-delete est en quelque sorte l'inverse de l'algorithme de Kruskal : le second part d'un graphe vide et ajoute des arêtes par poids croissant, tandis que le premier part du graphe original et en supprime des arêtes par poids décroissant. Les deux algorithmes sont des algorithmes gloutons qui choisissent la meilleure solution à chaque étape.

Description

L'algorithme reverse-delete est un algorithme glouton qui parcourt toutes les arêtes par poids décroissant. Pour chacune d'elles, l'algorithme la supprime si cela ne déconnecte pas le graphe[1].

Exemple

Le tableau suivant donne un exemple d'exécution de l'algorithme reverse-delete.

Graphe de départ. Le nombre à côté d'une arête indique son poids.
L'algorithme commence par examiner l'arête de poids maximal qui est DE, de poids 15. Cette arête est supprimée puisque cela ne déconnecte pas le graphe.
L'arête suivante est FG de poids 11. De nouveau, elle est supprimée car cela ne déconnecte pas le graphe.
L'algorithme examine ensuite l'arête BD, de poids 9. Pour la même raison, elle est supprimée.
L'algorithme examine ensuite l'arête EG. La supprimer déconnecterait le graphe en créant deux composantes connexes, comprenant G d'une part, et les autres sommets d'autre part. EG n'est donc pas supprimée et l'arête suivante à être examinée est BC, qui est supprimée.
L'arête suivante est EF, qui est supprimée.
L'algorithme examine ensuite les arêtes restantes sans les supprimer, puis retourne ce graphe final qui est bien un arbre couvrant minimum du graphe initial.

Références

  1. ↑ a et b (en) Jon Kleinberg et Éva Tardos, Algorithm Design, Pearson/Addison-Wesley, (ISBN 978-0-321-29535-4), chap. 4.5 (« The Minimum Spanning Tree Problem »), p. 144
  2. ↑ (en) Joseph B. Kruskal, « On the shortest spanning subtree of a graph and the traveling salesman problem », Proceedings of the American Mathematical Society, vol. 7, no 1,‎ , p. 48–50 (ISSN 0002-9939 et 1088-6826, DOI 10.1090/S0002-9939-1956-0078686-7, lire en ligne, consulté le )
v · m
Recherche
Plus court chemin
Arbre couvrant minimum
Flot maximum
Coupe minimum
Composantes fortement connexes
Coloration

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.