Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Arbre couvrant de poids minimal
Résumé
thumb|L'arbre couvrant de poids minimal d'un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur.
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), arbre couvrant minimum ou arbre sous-tendant minimum 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 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).
vignette|Un graphe connexe (en haut) et le dessin deux arbres couvrants minimums (en bas).
Comme le montre la figure ci-contre, un graphe connexe peut comporter plusieurs arbres couvrants minimum différents, mais si tous les poids sont différents, alors il est unique. Un graphe non orienté et général possède une forêt couvrante de poids minimal.
Pour tout cycle dans le graphe, si une arête est de poids strictement plus grand que les autres, alors cette arête n'est pas dans l'arbre couvrant de poids minimal. Autrement dit, toute arête (u,v) du graphe est de poids supérieur ou égal à l'arête de poids maximum sur le chemin reliant u à v dans l'arbre.
Pour toute coupe du graphe, si une arête est de poids strictement inférieur aux autres, alors elle appartient à l'arbre couvrant de poids minimal.
Un problème classique est de savoir, étant donné un ensemble de points dans avec la norme euclidienne, quel est le poids de l'arbre couvrant minimal. Il est de l'ordre de en moyenne et avec probabilité 1.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique