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
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]- (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
- (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 )
