suivant: Applications des ACM
monter: Le problème des arbres
précédent: Le problème des arbres
![\begin{defi}[Arbre Couvrant]
Soit $G$\ un graphe non orienté muni d'une fonctio...
...n{displaymath}
C(T)=\sum_{(i,\,j)\,\in\,T}c_{ij}
\end{displaymath}
\end{defi}](img372.png)
Par définition des arbres, un Arbre Couvrant est composé de 
arêtes.
![\begin{defi}[Arbre Couvrant de Poids Minimal]
On appelle Arbre Couvrant de poid...
...rant qui minimise la somme des coûts des arêtes qui le
constituent.
\end{defi}](img373.png)
Par exemple, l'arborescence des plus courts chemins depuis un sommet 
vers
tous les autres sommets constitue un arbre couvrant quand l'orientation est
supprimée.
Il est néanmoins important de bien différencier les deux problèmes. Les
éléments suivants peuvent vous y aider :
- Le problème de plus courts chemins est le plus souvent traité sur un
graphe orienté alors que la notion d'arbre couvrant est
fondamentalement non orientée. Vous retiendrez que rechercher les plus courts
chemins est une opération plus compliquée et plus coûteuse que la mise en
évidence d'un ACM.
- Les deux problèmes travaillent avec des fonctions objectif
différentes. Dans le cas des plus courts chemins, on recherche un chemin de
longueur minimale pour chaque couple
. Alors que dans le cadre de l'ACM on minimise le coût total de l'arbre (en
tant que somme des longueurs de ses arêtes) ce qui n'est absolument pas la
même chose !
Bruno Garcia
2000-12-17