Qu'est-ce qu'un arbre couvrant minimal ?

C'est un sous-ensemble des arêtes d'un graphe qui connecte tous les nœuds entre eux, ne contient aucun cycle, et a le poids total minimal possible parmi tous ces sous-ensembles connectants.

Comment fonctionne l'algorithme de Kruskal ?

Il trie toutes les arêtes par poids du plus petit au plus grand, puis les traite dans l'ordre, ajoutant chaque arête à l'arbre seulement si elle connecte deux parties précédemment déconnectées du graphe (vérifié efficacement avec une structure union-find).

À quoi sert union-find ?

Union-find (aussi appelé ensemble disjoint) suit efficacement les nœuds déjà connectés, permettant à l'algorithme de Kruskal de détecter rapidement si l'ajout d'une arête créerait un cycle, sans réanalyser tout l'arbre à chaque fois.

Que se passe-t-il si mon graphe est déconnecté ?

La calculatrice signale alors une forêt couvrante minimale — le moyen le moins coûteux de connecter chaque composante déconnectée en interne, puisqu'aucun arbre unique ne peut couvrir des nœuds sans chemin entre eux.

L'arbre couvrant minimal est-il toujours unique ?

Pas nécessairement — si plusieurs arêtes partagent le même poids, il peut exister plus d'un arbre couvrant minimal valide avec le même poids total, bien que le poids total lui-même soit toujours unique.

En quoi cela diffère-t-il de l'algorithme de Dijkstra ?

Un arbre couvrant minimal minimise le coût total pour connecter tous les nœuds ensemble, tandis que l'algorithme de Dijkstra minimise le coût d'un chemin entre deux nœuds spécifiques — les deux problèmes résolvent des questions différentes même si les deux travaillent sur des graphes pondérés.

Combien de nœuds cette calculatrice peut-elle gérer ?

Cette calculatrice prend en charge jusqu'à 50 nœuds, largement suffisant pour des exemples de graphes saisis à la main tout en gardant instantané le calcul de tri et union-find.

Où les arbres couvrants minimaux sont-ils utilisés dans la vie réelle ?

Ils sont utilisés pour concevoir des réseaux rentables — tracer des câbles ou des pipelines, câbler des circuits imprimés, regrouper des points de données, et approximer des solutions à des problèmes de conception de réseau plus difficiles.

Calculatrice d'Arbre Couvrant Minimal — Trouvez le Moyen le Moins Coûteux de Connecter un Graphe

Notre Calculatrice d'Arbre Couvrant Minimal trouve l'ensemble d'arêtes qui connecte tous les nœuds d'un graphe pondéré au coût total le plus bas possible, en utilisant l'algorithme de Kruskal avec détection de cycles par union-find, votre graphe étant saisi sous forme de simple liste d'arêtes textuelle (par ex. A-B:4, B-C:2).

Réponse rapide

Saisissez votre graphe pondéré sous forme de liste d'arêtes pour trouver instantanément l'arbre couvrant minimal — l'ensemble le moins coûteux d'arêtes connectant tous les nœuds — via l'algorithme de Kruskal.

Arêtes (séparées par des virgules)

Saisissez des arêtes pondérées sous la forme NœudA-NœudB:poids, par ex. A-B:4, B-C:2.

Comment utiliser Calculatrice d'Arbre Couvrant Minimal — Algorithme de Kruskal en Ligne

1
Saisissez votre graphe sous forme de liste d'arêtes séparées par des virgules, par ex. A-B:4, B-C:2.
2
Cliquez sur 'Calculer' pour trouver l'arbre couvrant minimal.
3
Consultez les arêtes sélectionnées et le poids total minimal.

Pourquoi utiliser Calculatrice d'Arbre Couvrant Minimal — Algorithme de Kruskal en Ligne ?

Un arbre couvrant minimal connecte tous les nœuds d'un graphe en utilisant le moins d'arêtes possible, les moins coûteuses, sans cycles — exactement la structure que vous souhaiteriez lors de la conception d'un réseau (routes, pipelines, câblage de circuits) qui doit atteindre chaque point au moindre coût total. L'algorithme de Kruskal le trouve avec élégance : trier toutes les arêtes de la moins chère à la plus chère, et ajouter avidement chaque arête qui ne crée pas de cycle, en suivant la connectivité efficacement avec une structure de données union-find. Cette approche gloutonne est prouvée optimale, et cette calculatrice l'exécute directement sur un graphe que vous saisissez sous forme de liste d'arêtes pondérées.

Questions fréquentes

Outils similaires

Calculatrice du Plus Court Chemin de Dijkstra — Graphes Pondérés en Ligne

Trouvez le plus court chemin et la distance totale entre deux nœuds dans un graphe pondéré à l'aide de l'algorithme de Dijkstra. Calculatrice gratuite avec une simple saisie de liste d'arêtes.

Calculatrice de Matrice d'Adjacence — Construisez une Matrice de Graphe en Ligne

Construisez et affichez la matrice d'adjacence d'un graphe à partir d'une simple saisie de liste d'arêtes, avec sa séquence de degrés. Calculatrice gratuite, pondérée ou non pondérée.

Calculatrice de Coloration de Graphe — Algorithme de Welsh-Powell en Ligne

Coloriez les sommets d'un graphe pour qu'aucun nœud connecté ne partage une couleur, à l'aide de l'algorithme glouton de Welsh-Powell. Calculatrice gratuite avec une simple saisie de liste d'arêtes.

Calculateur de Flux Réseau — Flux Maximal via Edmonds-Karp en Ligne

Trouvez le flux maximal d'une source à un puits dans un graphe orienté à capacités à l'aide de l'algorithme d'Edmonds-Karp. Calculateur gratuit avec une simple liste d'arêtes.