Algorithme de Borůvka

Lalgorithme 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'. 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. 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. 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 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é. 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. 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'). Au départ, il était destiné à rendre le réseau électrique de Moravie efficace.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (8)

Cours associés (1)

Séances de cours associées (19)

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Algorithme de Borůvka

Component (graph theory)

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.

Algorithme de Prim

thumb|right|Arbre couvrant de poids minimum L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.

Union-Trouver et Minimum Spanning Arbres CS-250: Algorithms I

Couvre la structure de données Union-Find et Minimum Spanning Trees.

L'algorithme de Union-Find et de Prim CS-250: Algorithms I

Présente la structure de données Union-Find et l'algorithme de Prim pour un minimum d'arbres couvrants dans les graphiques, explorant les coupes et les origines historiques.

Minimum Spanning Trees CS-250: Algorithms I

Couvre la mise en œuvre et l'analyse de la structure des données des ensembles disjoints et introduit le concept d'arbres couvrants minimum.