next up previous
suivant: Applications des ACM monter: Le problème des arbres précédent: Le problème des arbres

Définitions


\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}
Par définition des arbres, un Arbre Couvrant est composé de $ n-1$ 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}
Par exemple, l'arborescence des plus courts chemins depuis un sommet $ s$ 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 :
  1. 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.
  2. 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 $ (s,\, i)\; \forall \; i \,\in\,
G$. 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