Définitions liées aux arbres de recouvrement minimaux
Environnement du problème de recherche de l'arbre de coût minimal
Pour ce problème, on considère des graphes non orientés constitués d'un ensemble de points X et d'un ensemble d'arêtes E qui lient entre eux certains de ces points. En outre, on suppose qu'à chaque arête est associée une valeur numérique. On peut alors noter le graphe (X, E, V) où V est l'ensemble des valeurs associées à chaque arête de E.
On s'intéresse aux graphes partiels du graphe (X, E, V). Les graphes partiels sont obtenus à partir d'un graphe donné en retirant 0 ou plusieurs arêtes. Le graphe de départ fait partie de ses graphes partiels.
Animation montrant des exemples de graphes partiels de graphes non orientés
Cliquer sur les boutons "précédents" ou "suivants" de l'animation ci-dessus pour visualiser des représentations graphiques de graphes et de graphes partiels de ces graphes.
Définition : Poids d'un graphe non orienté valué
Le poids d'un graphe non orienté valué est égal à la somme des valeurs de ses arêtes.
Définition : Définition d'un arbre de recouvrement d'un graphe
Un arbre de recouvrement d'un graphe est un graphe partiel de ce graphe qui est un arbre.
Ceci implique que le graphe de départ était connexe.
Le poids de l'arbre est la somme des valeurs de ces arêtes.
Définition de l'arbre de recouvrement minimal
Rechercher un arbre de recouvrement minimal consiste à chercher un arbre de recouvrement dont le poids est minimal. Il n'y a pas nécessairement unicité de l'arbre de recouvrement minimal.
Animation montrant des exemples d'arbres de recouvrement minimaux
Cliquer sur les boutons "suivant" ou "précédent" pour visualiser des graphes non orientés connexes ainsi qu'un de leur arbre de recouvrement minimal.
