∑
MathTCG
#054 / 100•Space, Chance & Computation•MathTCG #454 / 500•★★Peu commune•⊦Maths Discrètes•Méthode & Idée

Algorithme de Kruskal

Période historique : 1956

Algorithme glouton construisant l'arbre couvrant de poids minimal d'un graphe par tri croissant des arêtes.

Contenu & Formulation mathématique

Principe de la démarche
Algorithme glouton construisant l'arbre couvrant de poids minimal d'un graphe par tri croissant des arêtes.
Champs d'application canoniques
Démonstration mathématique
T=∅,ei=arg⁡min⁡e∈E∖Tw(e):si T∪{ei} sans cycle alors T←T∪{ei}T = \emptyset, \quad e_i = \arg\min_{e \in E \setminus T} w(e) : \text{si } T \cup \{e_i\} \text{ sans cycle alors } T \leftarrow T \cup \{e_i\}

Genèse & Portée historique

Publié par Joseph Kruskal en 1956, cet algorithme examine les arêtes d'un graphe connexe pondéré par ordre croissant de poids et ajoute chaque arête à l'arbre si et seulement si elle ne forme pas de cycle avec les arêtes déjà sélectionnées. Implémenté avec la structure de données Union-Find (ensembles disjoints), il s'exécute en O(E log E).

Kruskal a conçu cet algorithme en réaction à la publication d'un article de Joseph Borůvka de 1926 sur la conception optimale des réseaux électriques en Moravie.

« Relier tous les sommets au moindre coût sans jamais refermer le moindre cercle. »

Filiations & Relations conceptuelles (1)

Établi / Formulé par#460

Joseph Kruskal

Algorithme d'arbre couvrant minimal publié par Joseph Kruskal en 1956.

Objet de collection MathTCG

#454
★★Peu commune
⊦

Algorithme de Kruskal

Maths Discrètes•MÉTHODE

Principe : Algorithme glouton construisant l'arbre couvrant de poids minimal d'un graphe par tri croissant des arêtes.

T=∅,ei=arg⁡min⁡e∈E∖Tw(e):si T∪{ei} sans cycle alors T←T∪{ei}T = \emptyset, \quad e_i = \arg\min_{e \in E \setminus T} w(e) : \text{si } T \cup \{e_i\} \text{ sans cycle alors } T \leftarrow T \cup \{e_i\}
1956

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.

Extension : Space, Chance & Computation (#054 / 100)
Numéro global MathTCG : MathTCG #454 / 500
Rareté officielle : Peu commune (★★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : algorithme-de-kruskal
Consulter mon classeurExplorer tout le recueil