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 (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe). L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum[réf. nécessaire].

Property Value
dbo:abstract
  • 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 (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe). L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum[réf. nécessaire]. L'arbre couvrant minimum peut s'interpréter de différentes manières selon ce que représente le graphe. De manière générale si on considère un réseau où un ensemble d'objets doivent être reliés entre eux (par exemple un réseau électrique et des habitations), l'arbre couvrant minimum est la façon de construire un tel réseau en minimisant un coût représenté par le poids des arêtes (par exemple la longueur totale de câble utilisée pour construire un réseau électrique). (fr)
  • 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 (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe). L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum[réf. nécessaire]. L'arbre couvrant minimum peut s'interpréter de différentes manières selon ce que représente le graphe. De manière générale si on considère un réseau où un ensemble d'objets doivent être reliés entre eux (par exemple un réseau électrique et des habitations), l'arbre couvrant minimum est la façon de construire un tel réseau en minimisant un coût représenté par le poids des arêtes (par exemple la longueur totale de câble utilisée pour construire un réseau électrique). (fr)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 1079530 (xsd:integer)
dbo:wikiPageLength
  • 7720 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 182558006 (xsd:integer)
dbo:wikiPageWikiLink
prop-fr:auteur
  • Jason Eisner (fr)
  • Jason Eisner (fr)
prop-fr:date
  • 1997 (xsd:integer)
prop-fr:note
  • Manuscript available online (fr)
  • Manuscript available online (fr)
prop-fr:site
  • Université de Pennsylvanie (fr)
  • Université de Pennsylvanie (fr)
prop-fr:titre
  • State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion (fr)
  • State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion (fr)
prop-fr:url
  • cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf (fr)
  • cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf (fr)
prop-fr:wikiPageUsesTemplate
dct:subject
rdfs:comment
  • 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 (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe). L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum[réf. nécessaire]. (fr)
  • 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 (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe). L'arbre couvrant de poids minimal est aussi connu sous certains autres noms, tel qu’arbre couvrant minimum ou encore arbre sous-tendant minimum[réf. nécessaire]. (fr)
rdfs:label
  • Минимальное остовное дерево (ru)
  • Albero ricoprente minimo (it)
  • Arbre couvrant de poids minimal (fr)
  • Cây bao trùm nhỏ nhất (vi)
  • Minimaal opspannende boom (nl)
  • Minimalt uppspännande träd (sv)
  • Minimum spanning tree (en)
  • Мінімальне кістякове дерево (uk)
  • Árvore de extensão mínima (pt)
rdfs:seeAlso
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is oa:hasTarget of
is foaf:primaryTopic of