Algorithme de Boruvka

recherche d’arbre couvrant de poids minimum

Histoire

Otakar Borůvka (né le 10 mai 1899 à Uherský Ostroh – mort le 22 juillet 1995 à Brno en Tchécoslovaquie) était ingénieur en télécommunication.

En 1926, il écrit un premier article “O jistém problému minimálním” dans lequel il décrit un algorithme permettant de trouver un arbre couvrant de poids minimum dans un réseau de distribution électrique.

Son premier article, jamais publié, est redécouvert par Gustave Choquet en 1938 puis par George Sollin en 1961.

Les algorithmes de Prim et Kruskal seront proposés en 1956 et citeront l’algorithme de Boruvka.

Dorian vous conseille de lire l’article de R. L. Graham et Pavol Hell intitulé “On the history on the MST problem“.

Algorithme

L’algorithme de Borůvka s’applique sur des graphes valués dont les poids des arêtes sont tous différents.

Le graphe de départ

1) Modification des poids des arêtes adjacentes afin qu’ils soient tous différents

2) Chaque sommet choisi l’arête, dont il est extrémité, de poids le plus faible. Deux sommets peuvent choisir la même arête, comme ci-contre, a et d ont choisi l’arête (a,d)

3) Une fois que chaque sommet a choisi une arête, on fusionne tous les sommets joints par une arête choisie

4) On recommence l’étape 2. L’arête choisie ici est l’arête (b,e)

L’arbre couvrant de poids minimum

Note

L’algorithme de Bernard Chazelle (2000) utilise celui de Borůvka, tout comme pour celui de Kroeger, Klein et Tarjan.

Bibliographie conseillée

R.L. Graham, Pavol Hell, “On the History of the Minimum Spanning Tree Problem,” IEEE Annals of the History of Computing, vol. 7, no. 1, pp. 43-57, Jan.-Mar. 1985, doi:10.1109/MAHC.1985.10011

Comments are closed