« Arbre de longueur minimale » : différence entre les versions
m (Remplacement de texte — « [[:Catégorie:ISI | © Glossaire » par « [[:Catégorie:Statistiques | © Glossaire ») |
Aucun résumé des modifications |
||
| Ligne 1 : | Ligne 1 : | ||
== Définition == | == Définition == | ||
En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal (ACM) de ce graphe est un arbre couvrant et qui connecte tous les sommets ensemble | |||
et dont la somme des poids des arêtes est minimale | |||
L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’'''arbre couvrant minimum''' ou encore '''arbre sous-tendant minimum''' | |||
== Français == | == Français == | ||
''' arbre de longueur minimale''' | ''' arbre de longueur minimale''' | ||
'''ùrbre couvrant de poids minimal''' | |||
== Anglais == | == Anglais == | ||
| Ligne 7 : | Ligne 14 : | ||
<small> | <small> | ||
[https://fr.wikipedia.org/wiki/Arbre_couvrant_de_poids_minimal Source : wikipedia] | |||
[http://isi.cbs.nl/glossary/term2105.htm Source : ISI ] | [http://isi.cbs.nl/glossary/term2105.htm Source : ISI ] | ||
Version du 27 mars 2021 à 21:24
Définition
En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal (ACM) de ce graphe est un arbre couvrant et qui connecte tous les sommets ensemble et dont la somme des poids des arêtes est minimale
L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum
Français
arbre de longueur minimale
ùrbre couvrant de poids minimal
Anglais
minimum spanning tree
Contributeurs: Jean Benoît Morel, wiki
