# Calculateur d'arbre couvrant minimal (Kruskal / Prim)

Calcule l'arbre couvrant minimal d'un graphe non orienté pondéré (1–30 arêtes, une par ligne : nœud1, nœud2, poids) avec deux algorithmes : Kruskal trie par poids et applique une union-find, en journalisant chaque arête acceptée ou rejetée comme cycle ; Prim part d'un nœud initial et prend à chaque pas l'arête la moins chère sortant de la composante, en montrant sa croissance. Les boucles sont ignorées ; un graphe non connexe est rejeté avec son nombre de composantes ; le poids total des deux algorithmes doit coïncider (contrôle interne). Classique : A-B 4, A-C 2, B-C 5, B-D 10, C-E 3, D-E 4, D-F 11, E-F 8 → poids de l'ACM 21 (A—C, C—E, A—B, D—E, E—F), B—C rejetée comme cycle.

> Page canonique: https://elysiatools.com/fr/tools/minimum-spanning-tree

- **Catégorie:** Math & Numbers

- **Mots-clés:** arbre couvrant minimal, acm, kruskal, prim, union-find, algorithme glouton, graphe, conception de réseaux, arbre couvrant, mathématiques discrètes

## Présentation

Ce calculateur détermine l'arbre couvrant minimal (ACM) d'un graphe non orienté pondéré à l'aide des algorithmes classiques de Kruskal et de Prim. Il détaille chaque étape du calcul en consignant l'acceptation ou le rejet des arêtes formant un cycle (Kruskal) ou la croissance progressive de la composante connexe (Prim), tout en effectuant un contrôle interne de cohérence sur le poids total.

## Entrées

- **Arêtes (une par ligne : nœud1, nœud2, poids)** (textarea): One undirected edge per line: two node names (1–8 letters/digits) and a weight (negatives allowed).
- **Algorithme** (select)
- **Nœud de départ (Prim uniquement, facultatif)** (text): e.g. D
- **Décimales** (number)

## Quand l'utiliser

- Résoudre des exercices de théorie des graphes ou de mathématiques discrètes nécessitant le détail pas à pas de Kruskal ou de Prim.
- Optimiser le coût de raccordement d'un réseau physique (câblage réseau, canalisations, distribution électrique) sans former de cycle.
- Vérifier la connexité d'un graphe pondéré et contrôler la validité d'un arbre couvrant minimal.

## Fonctionnement

- Saisissez la liste des arêtes non orientées (1 à 30 lignes), chaque ligne contenant le nom des deux nœuds et le poids associé.
- Sélectionnez l'algorithme souhaité (Kruskal avec union-find ou Prim avec croissance par nœud) et précisez éventuellement le nœud de départ pour Prim.
- Définissez le nombre de décimales souhaité pour l'affichage des poids.
- Le calculateur vérifie la connexité du graphe, élimine les boucles et affiche la liste des arêtes retenues ainsi que le poids total minimal.

## Cas d'usage

- Conception de schémas de câblage à coût minimal reliant plusieurs baies de serveurs ou commutateurs.
- Vérification pédagogique pour étudiants et enseignants lors de travaux dirigés d'algorithmique des graphes.
- Calcul de l'infrastructure minimale de raccordement routier ou de canalisations entre différents sites géographiques.

## Questions fréquentes

### Quelle est la différence entre Kruskal et Prim dans cet outil ?

Kruskal trie globalement les arêtes par ordre croissant et les ajoute si elles ne créent pas de cycle, tandis que Prim étend progressivement un arbre à partir d'un nœud source en choisissant l'arête sortante la moins coûteuse.

### Que se passe-t-il si le graphe n'est pas connexe ?

L'outil rejette le graphe et indique le nombre de composantes connexes détectées, car un arbre couvrant minimal ne peut exister que sur un graphe connexe.

### Les arêtes avec des poids négatifs sont-elles autorisées ?

Oui, les algorithmes de Kruskal et de Prim supportent parfaitement les arêtes à poids négatifs pour la construction de l'arbre couvrant minimal.

### Comment sont gérées les boucles (arête d'un nœud vers lui-même) ?

Les boucles sur un même nœud sont automatiquement ignorées lors du calcul car elles forment un cycle immédiat non admissible dans un arbre.

### Le choix du nœud de départ modifie-t-il le résultat de Prim ?

Le nœud de départ modifie l'ordre d'exploration des arêtes, mais le poids total de l'arbre couvrant minimal obtenu reste rigoureusement identique.

## Outils associés

- [Calculateur de Densité (ρ = m/V)](https://elysiatools.com/fr/tools/density-calculator): Calcule la densité, la masse ou le volume à partir des deux autres, avec gravité spécifique et flottaison
- [Calculateur de NPSH de Pompe (Hauteur Nette Positive d'Aspiration) et Vérification de Cavitation](https://elysiatools.com/fr/tools/pump-npsh-calculator): Calcule la hauteur nette positive d'aspiration disponible de la pompe : NPSH_a = (p_surface - p_vapor)/(ρ·g) + H_static - h_friction (en m). Les pressions de surface et de vapeur sont absolues ; H_static est positif pour aspiration noyée (liquide au-dessus de la pompe) et négatif pour aspiration en charge (liquide sous la pompe). Comparaison au NPSH_r de la courbe de la pompe : marge margin = NPSH_a - NPSH_r et rapport ratio = NPSH_a/NPSH_r ; classification safe (sûr), marginal (marge < 0,5 m) ou cavitation likely (cavitation probable). Si NPSH_r = 0, seul NPSH_a est renvoyé. Pressions en Pa/kPa/bar/atm/psi, longueur en m/ft, masse volumique en kg/m³/g/cm³/lb/ft³.
- [Mots en Nombre](https://elysiatools.com/fr/tools/words-to-number): Convertit les mots-nombres anglais en chiffres. Gère les ordres de grandeur, « and », les décimales via « point » et les traits d'union, en remplaçant le segment numérique sur place.
- [Filigrane discret adaptatif à 12 points](https://elysiatools.com/fr/tools/adaptive-12-point-hidden-watermark): Ajoute un filigrane textuel discret à une image ou à chaque image prise en charge dans un ZIP, à toutes, certaines au hasard ou des positions choisies du périmètre, avec contraste clair/foncé automatique selon le fond local.
- [Calculateur de l'Excrétion Fractionnelle du Sodium FENa](https://elysiatools.com/fr/tools/fractional-excretion-sodium): Excrétion fractionnelle du sodium FENa = (Na-urinaire×SCr)/(Na-sérique×UCr)×100%. Différencie l'IRA oligurique : <1% évoque une azotémie prérénale (hypovolémie, IC, syndrome hépatorénal, états économes en sodium) ; ≥1% évoque une atteinte intrinsèque (typiquement NTA, les tubules lésés ne réabsorbent pas le sodium) ; >4% parfois en post-obstructif. Les diurétiques faussent le résultat (utiliser FEUrea<35%) ; la NTA au contraste/sepsis peut donner une FENa basse ; l'IRC chronique et la glucosurie élèvent la FENa. À interpréter avec la clinique. Non un avis médical.
- [Découpeur de thread Twitter / X](https://elysiatools.com/fr/tools/twitter-thread-splitter): Collez un long texte et découpez-le en un thread X numéroté qui respecte la limite de 280 caractères. Découpe aux frontières mot/phrase/paragraphe, ajoute la numérotation 1/N, pèse correctement CJK et caractères pleine chasse, compte les URL comme 23 caractères et affiche une carte de style X avec un compteur.
- [Calculateur de Puissance CTA (refroidir / chauffer)](https://elysiatools.com/fr/tools/ahu-capacity-calculator): Calcule la puissance de la batterie d'une CTA à partir des états entrée/sortie et du débit massique d'air sec ṁ_da : puissance totale Qt=ṁ_da·(h1−h2), sensible Qs=ṁ_da·cp_ma·(T1−T2) (cp_ma≈1,006+1,86·W), latente Ql=Qt−Qs, SHR=Qs/Qt. États décrits par bulbe sec T et un paramètre d'humidité (HR φ ou rapport W) ; W obtenu via Magnus, enthalpie h=1,006·T+W·(2501+1,86·T). Résultat signé, pour refroidir ou chauffer.
- [Calculateur de Poussée d'Archimède (F = ρ·V·g)](https://elysiatools.com/fr/tools/buoyancy-calculator): Calcule poussée, densité de fluide ou volume déplacé à partir de deux d'entre eux, avec analyse de flottaison

## Exemples

- [Exemples de Traitement d'Images Web Python](https://elysiatools.com/fr/samples/web-image-processing-python): Exemples de traitement d'images Web Python utilisant PIL/Pillow incluant la lecture, l'enregistrement, le redimensionnement et la conversion de format
- [Exemples SVG](https://elysiatools.com/fr/samples/svg-samples): Exemples de graphiques vectoriels évolutifs (SVG) démontrant diverses fonctionnalités et techniques SVG
- [Exemples de Traitement d'Images Android Java](https://elysiatools.com/fr/samples/android-image-processing-java): Exemples de traitement d'images Android Java incluant lecture/écriture, mise à l'échelle et conversion de format
- [Exemples de Traitement d'Images Android Kotlin](https://elysiatools.com/fr/samples/android-image-processing-kotlin): Exemples de traitement d'images Android Kotlin incluant lecture/écriture, mise à l'échelle et conversion de format