En informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Il a été conçu en 1956 par Joseph Kruskal.
On considère un graphe connexe non-orienté et pondéré : chaque arête possède un poids qui est un nombre qui représente le coût de cette arête. Dans un tel graphe, un arbre couvrant est un sous-graphe connexe sans cycle qui contient tous les sommets du graphe. Le poids d'un tel arbre est la somme des poids des arêtes qui le compose. Un arbre couvrant minimum est un arbre couvrant dont le poids est inférieur ou égal à celui de tous les autres arbres couvrants du graphe. L'objectif de l'algorithme de Kruskal est de calculer un tel arbre couvrant minimum.
Ce problème a de nombreuses applications, par exemple simplifier un câblage ou supprimer les liaisons maritimes les moins rentables en préservant l'accessibilité aux différents ports.
L'algorithme construit un arbre couvrant minimum en sélectionnant des arêtes par poids croissant. Plus précisément, l'algorithme considère toutes les arêtes du graphe par poids croissant (en pratique, on trie d'abord les arêtes du graphe par poids croissant) et pour chacune d'elles, il la sélectionne si elle ne crée pas un cycle. Le tableau suivant donne un exemple d'exécution de l'algorithme de Kruskal.
On remarque que lors du déroulement de l'algorithme, les arêtes sélectionnées ne forment pas nécessairement un graphe connexe. Mais à la fin, les arêtes sélectionnées (en vert) forment un graphe connexe.
vignette|Execution de l’algorithme de Kruskal
Kruskal(G) :
1 A := ø
2 pour chaque sommet v de G :
3 créerEnsemble(v)
4 trier les arêtes de G par poids croissant
5 pour chaque arête (u, v) de G prise par poids croissant :
6 si find(u) ≠ find(v) :
7 ajouter l'arête (u, v) à l'ensemble A
8 union(u, v)
9 renvoyer A
Les fonctions créerEnsemble, find et union sont les trois opérations d'une structure de données Union-Find – qui, respectivement, ajoute une classe singleton à la structure, renvoie un représentant de la classe d'un élément et fusionne deux classes d'équivalence.
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.
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (
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
En informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Il a été conçu en 1956 par Joseph Kruskal. On considère un graphe connexe non-orienté et pondéré : chaque arête possède un poids qui est un nombre qui représente le coût de cette arête. Dans un tel graphe, un arbre couvrant est un sous-graphe connexe sans cycle qui contient tous les sommets du graphe.
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.
thumb|L'arbre couvrant de poids minimal d'un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. 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 (ACM), arbre couvrant minimum ou arbre sous-tendant minimum 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 (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe).
Explore l'optimisation avec des contraintes en utilisant les conditions KKT et l'algorithme de point intérieur sur deux exemples de programmation quadratique.