Algorithme de Borůvka

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme de Borůvka (aussi appelé algorithme de Sollin) est un algorithme de recherche de l'arbre couvrant de poids minimal dans un graphe pondéré.

Problème de l'arbre couvrant minimal[modifier | modifier le code]

En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale.

Algorithme[modifier | modifier le code]

Principe[modifier | modifier le code]

Le principe est de réduire G en contractant des arêtes : on choisit peu à peu les arêtes qui seront dans l'arbre, et à chaque fois que l'on en choisit une, on fusionne les nœuds que cette arête relie. Ainsi, il ne reste plus qu'un sommet à la fin.

Pseudo-code[modifier | modifier le code]

On prend G le graphe et F l'ensemble des arêtes choisies (on le remplit peu à peu).

 1 F ← \varnothing
 2 Tant que G n'est pas réduit à un sommet faire
 3    Détruire les boucles de G (*) 
 4    Remplacer les arêtes multiples entre deux sommets par une seule dont le poids est le minimum
 5    Pour tout x, sommet de G faire
 6       Trouver l'arête e_x de poids minimum adjacente à x
 7       F ← F \cup{e_x}
 8       Contracter e_x (**)
 9    fin pour
10 fin tant que
11 renvoyer F;;

(*) i.e. les arêtes qui partent et arrivent au même sommet ; ce genre d'arête peut apparaitre après une itération.

(**) i.e. fusionner les sommets aux extrémités de e_x

Complexité[modifier | modifier le code]

L'algorithme de Borůvka a une complexité en O(A\ln(S)), où A est le nombre d'arêtes et S le nombre de sommets du graphe considéré[1].

Comparaison avec les autres algorithmes[modifier | modifier le code]

Il existe d'autres algorithmes pour le problème de l'arbre couvrant minimal, par exemple l'algorithme de Prim et l'algorithme de Kruskal.

Historique[modifier | modifier le code]

L'algorithme de Borůvka est le premier algorithme de recherche d'arbre couvrant de poids minimal découvert publié par Otakar Borůvka en 1926 dans l'article O jistém problému minimálním ('Sur un certain problème minimal')[2]. Au départ, il était destiné à rendre le réseau électrique de Moravie efficace. Il fut redécouvert à de nombreuses reprises par la suite[3].

Notes et références[modifier | modifier le code]

  1. Graham-Hell, On the History of Minimum Spanning Tree Problem p. 52.
  2. (Borůvka 1926)
  3. Graham-Hell, On the History of Minimum Spanning Tree Problem p. 47.

Bibliographie[modifier | modifier le code]

  • (cs) Otakar Borůvka, « O jistém problému minimálním (About a certain minimal problem) », Práce mor. přírodověd. spol. v Brně III, vol. 3,‎ 1926, p. 37–58
  • (en) R.L. Graham et Pavol Hell, « On the History of Minimum Spanning Tree Problem », Annals of the History of Computing, vol. 7, no 1,‎ janvier 1985, p. 43-57 (lire en ligne)