Pourquoi un graphe complet — dans les applications n’est-il pas plutôt creux ?

Le graphe **euclidien complet** est un modèle clair : en théorie on peut relier n’importe quelle paire, et l’ACM choisit les **n−1** liaisons les moins chères sans cycle. Dans les réseaux réels il y a moins d’arêtes ; les mêmes algorithmes s’y appliquent, mais le cas dense montre bien le tri de **Kruskal** et le balayage des candidats de **Prim**.

L’ACM change-t-elle si l’on change la racine de Prim ?

Si les poids **ne sont pas uniques**, il peut exister **plusieurs** ensembles d’arêtes distincts de même poids minimal. Alors des racines différentes (et un autre ordre) peuvent donner des **ACM distinctes** comme ensembles d’arêtes, mais le **poids total** reste le même : on le confronte à **Kruskal**.

Que signifie le trait rouge pointillé en mode Kruskal ?

C’est l’arête courante de la liste triée qu’on **ne peut pas** ajouter : les deux extrémités sont déjà dans la **même** composante des ensembles disjoints ; l’ajouter fermerait un **cycle**, et l’algorithme la **saute**.

Arbre couvrant de poids minimal (Prim et Kruskal)

Points aléatoires dans le plan, graphe complet à poids euclidiens : Prim pas à pas depuis une racine, ou Kruskal avec ensembles disjoints ; on compare le poids total.

À propos du modèle

L’arbre couvrant de poids minimal relie tous les sommets sans cycle et avec la plus petite somme de poids. n points pseudo-aléatoires dans le plan (reproductibles à partir de la graine de disposition). Le graphe est pris complet : le poids d’une arête est la distance euclidienne entre sommets ; tout arbre couvrant a n−1 arêtes. Prim part d’une racine choisie et, à chaque pas, ajoute l’arête minimale qui traverse la coupe « déjà dans l’arbre / dehors » (règle gloutonne par la propriété de coupe). Kruskal trie toutes les arêtes par poids (en cas d’égalité, ordre lexicographique des extrémités, pour le déterminisme) et parcourt la liste avec des ensembles disjoints : l’arête est acceptée si elle joint des composantes distinctes, et rejetée (trait rouge pointillé) si elle fermerait un cycle. Les poids totaux de l’ACM des deux algorithmes coïncident.

Public : Mathématiques discrètes et algorithmes : constructions gloutonnes de l’ACM, propriétés de coupe et de cycle, ensembles disjoints.

Notions clés

arbre couvrant de poids minimal (ACM)
algorithme de Prim
algorithme de Kruskal
propriété de coupe
propriété de cycle
ensembles disjoints (union-find)
graphe complet
poids euclidiens

Comment ça marche

Graphe complet de n points dans le plan, poids = distances euclidiennes : Prim fait croître l’arbre depuis la racine par l’arête minimale qui traverse la coupe ; Kruskal parcourt les arêtes par poids croissant et les ensembles disjoints écartent l’arête si elle fermerait un cycle ; le poids total de l’ACM coïncide pour les deux.

Questions fréquentes

Pourquoi un graphe complet — dans les applications n’est-il pas plutôt creux ?: Le graphe euclidien complet est un modèle clair : en théorie on peut relier n’importe quelle paire, et l’ACM choisit les n−1 liaisons les moins chères sans cycle. Dans les réseaux réels il y a moins d’arêtes ; les mêmes algorithmes s’y appliquent, mais le cas dense montre bien le tri de Kruskal et le balayage des candidats de Prim.
L’ACM change-t-elle si l’on change la racine de Prim ?: Si les poids ne sont pas uniques, il peut exister plusieurs ensembles d’arêtes distincts de même poids minimal. Alors des racines différentes (et un autre ordre) peuvent donner des ACM distinctes comme ensembles d’arêtes, mais le poids total reste le même : on le confronte à Kruskal.
Que signifie le trait rouge pointillé en mode Kruskal ?: C’est l’arête courante de la liste triée qu’on ne peut pas ajouter : les deux extrémités sont déjà dans la même composante des ensembles disjoints ; l’ajouter fermerait un cycle, et l’algorithme la saute.

Poursuivez avec des thèmes proches de cette catégorie — ou les 48 de «Ingénierie».

Toute la catégorie →

NouveauCollège–lycée

Labyrinthes et A*

Lancer la simulation

Labyrinthes parfaits sur une grille 40×28 : parcours récursif, Wilson, Eller ou Prim aléatoire ; résolution par A* (Manhattan, 4-voisinage). On peut dessiner des murs et déplacer le départ et le but.

NouveauCollège–lycée

A* et Dijkstra (grille)

Lancer la simulation

Grille 40×28 : A*, Dijkstra ou recherche gloutonne ; heuristiques, 4- et 8-connexité, murs et cellules coûteuses ; coloration des ensembles ouvert et fermé.

NouveauCollège–lycée

Automate fini

Lancer la simulation

Automate de Moore pour un feu tricolore : cycle vert–orange–rouge sur temporisation, ou bascule manuelle ; graphe d’états.

NouveauCollège–lycée

Planificateur RRT (grille)

Lancer la simulation

La même carte de murs 40×28 : échantillons aléatoires, nœud le plus proche, pas avec test de collision, biais d’échantillonnage vers le but ; bouton pour comparer à A*.

NouveauCollège–lycée

Cinématique inverse d’un manipulateur à deux segments

Lancer la simulation

Bras plan à deux segments : cible à l’écran, deux solutions — coude haut et coude bas, angles θ₁ et θ₂.

NouveauCollège–lycée

Flèche d’une poutre : méthode de la force unité

Lancer la simulation

Poutre d’Euler–Bernoulli sur appuis simples, force P et charge w : flèche analytique contre l’intégrale des travaux virtuels ∫Mm/EI dx.

Arbre couvrant de poids minimal (Prim et Kruskal)

À propos du modèle

Comment ça marche

Questions fréquentes

Simulations voisines

Labyrinthes et A*

A* et Dijkstra (grille)

Automate fini

Planificateur RRT (grille)

Cinématique inverse d’un manipulateur à deux segments

Flèche d’une poutre : méthode de la force unité

Arbre couvrant de poids minimal (Prim et Kruskal)

À propos du modèle

Comment ça marche

Questions fréquentes