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é.

Histoire[modifier | modifier le code]

L'algorithme de Borůvka est le premier algorithme de recherche d'arbre couvrant 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')[1]. Au départ, il était destiné à rendre le réseau électrique de Moravie efficace. Il fut redécouvert à de nombreuses reprises par la suite[2].

L'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

Preuve de l'algorithme[modifier | modifier le code]

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é[3].

Algorithmes améliorés[modifier | modifier le code]

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

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

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)

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Deux algorithmes ayant la même fonction mais procédant autrement :

Lien externe[modifier | modifier le code]

Page INRIA sur le sujet, avec un exemple.