Algorithme de Borůvka

Algorithme de Borůvka
Animation représentant l'algorithme de Borůvka, dans la version sans contraction.
Découvreur ou inventeur
Date de publication
Problèmes liés
Algorithme de la théorie des graphes (d), concept mathématique (en)Voir et modifier les données sur Wikidata

L'algorithme de Borůvka, est un algorithme de recherche de l'arbre couvrant de poids minimal dans un graphe pondéré. Il est aussi appelé algorithme de Sollin[1].

Problème de l'arbre couvrant minimal modifier

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

Principe modifier

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.

On peut aussi décrire l'algorithme sans parler de contraction : on construit une forêt dont les arbres fusionnent peu à peu pour former un arbre couvrant de poids minimum.

Pseudo-code modifier

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

 1 F ← vide
 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 union 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  

Complexité modifier

L'algorithme de Borůvka a une complexité en  , où   est le nombre d'arêtes et   le nombre de sommets du graphe considéré[2].

Comparaison avec les autres algorithmes modifier

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

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')[3]. Au départ, il était destiné à rendre le réseau électrique de Moravie efficace. Il fut redécouvert à de nombreuses reprises par la suite[4].

Notes et références modifier

  1. Ivan Lavallée, « Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe », RAIRO-Operations Research, vol. 19, no 1,‎ , p. 57-69
  2. Graham-Hell, On the History of Minimum Spanning Tree Problem p. 52.
  3. (Borůvka 1926)
  4. Graham-Hell, On the History of Minimum Spanning Tree Problem p. 47.

Bibliographie modifier

  • (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,‎ , 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,‎ , p. 43-57 (lire en ligne)

Lien externe modifier