Algorithme de Kruskal

Algorithme de Kruskal
Arbre couvrant de poids minimum

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 valué et non-orienté. Il a été conçu en 1956 par Joseph Kruskal.

Sommaire

Description du problème

Quand on travaille sur un graphe connexe, certains problèmes obligent à transformer ce graphe en un arbre (graphe sans cycle élémentaire) qui contient tous les sommets du graphe et quelques arêtes. On dit alors qu'on a un arbre couvrant du graphe.

Exemples :
Simplifier un câblage

Parfois, lorsque le graphe est valué, il s'agit de chercher un arbre recouvrant de poids minimum, c'est-à-dire dont la somme des poids est minimale.

Exemples :
Supprimer les liaisons maritimes les moins rentables en préservant l'accessibilité aux différents ports.

L'ARPM contient tous les sommets du graphe qu'il recouvre et uniquement les arêtes qui assurent son acyclicité et le poids minimum possible.

Principe

L'algorithme consiste à d'abord ranger par ordre de poids croissant les arêtes d'un graphe, puis à retirer une à une les arêtes selon cet ordre et à les ajouter à l'ACM cherché tant que cet ajout ne fait pas apparaître un cycle dans l'ACM.

Algorithme

KRUSKAL (G,w)
1 E := ø
2 pour chaque sommet v de G
3   faire CRÉER-ENSEMBLE (v)
4 trier les arêtes de G par ordre croissant de poids w
5 pour chaque arête (u,v) de G prise par ordre de poids croissant
6   faire si ENSEMBLE-REPRÉSENTATIF (u)  ENSEMBLE-REPRÉSENTATIF (v)
7           alors ajouter l'arête (u,v) à l'ensemble E
8                 UNION (u,v)
9 retourner E

w est une fonction qui associe à chaque arête du graphe G une valeur qui est son poids.

Les fonctions ENSEMBLE-REPRÉSENTATIF et UNION sont les deux opérations d'une structure Union-Find (qui, respectivement, renvoie un élément représentatif d'un ensemble et fusionne deux ensembles).

La complexité de l'algorithme est Θ(A log S) avec A le nombre d'arêtes et S le nombre de sommets du graphe G. On remarquera que lors du déroulement de l'algorithme, l'ACM n'est pas nécessairement connexe, il ne le sera qu'à la fin.

Références

Cormen, Leiserson, Rivest, Stein : Introduction à l'algorithmique

Liens internes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Kruskal de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Algorithme De Kruskal — Arbre couvrant de poids minimum 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 valué et non orienté. Sommaire …   Wikipédia en Français

  • Algorithme de kruskal — Arbre couvrant de poids minimum 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 valué et non orienté. Sommaire …   Wikipédia en Français

  • Algorithme Glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… …   Wikipédia en Français

  • Algorithme De Prim — Arbre couvrant de poids minimum L algorithme de Prim est un algorithme glouton déterminant un arbre couvrant minimal d un graphe connexe valué et non orienté. C est à dire qu il trouve un sous ensemble d arêtes formant un arbre incluant tous les… …   Wikipédia en Français

  • Algorithme de prim — Arbre couvrant de poids minimum L algorithme de Prim est un algorithme glouton déterminant un arbre couvrant minimal d un graphe connexe valué et non orienté. C est à dire qu il trouve un sous ensemble d arêtes formant un arbre incluant tous les… …   Wikipédia en Français

  • Algorithme glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… …   Wikipédia en Français

  • Kruskal —  Cette page d’homonymie répertorie des personnes (réelles ou fictives) partageant un même patronyme. Kruskal est un nom de famille notamment porté (ou ayant été porté) par : les frères Kruskal (de nationalité américaine), connu tous les …   Wikipédia en Français

  • Algorithme de Prim — Pour les articles homonymes, voir Prim. Arbre couvrant de poids minimum L algorithme de Prim est un algorithme glouton qui permet de trouver un arbre couvrant …   Wikipédia en Français

  • Joseph Kruskal — Pour les articles homonymes, voir Kruskal. Joseph Kruskal (né le 29 janvier 1928, mort le 19 septembre 2010) est un mathématicien, statisticien, chercheur en informatique et psychométricien américain. Articles connexes Algorithme de Kruskal… …   Wikipédia en Français

  • Méthode gloutonne — Algorithme glouton Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”