next up previous
suivant: Démonstration de l'équivalence des monter: Notion d'arbre précédent: Notion d'arbre

Définitions fondamentales

La notion d'arbre est fondamentale en recherche opérationnelle. Après avoir donné une première définition, nous énumèrerons plusieurs propriétés équivalentes à cette définition. Notons immédiatement que la notion d'arbre est non orientée : elle s'applique aussi bien au cas orienté qu'au cas non orienté. Il est donc plus simple de l'illustrer sur des graphes non orientés.
\begin{defi}
Un arbre est un graphe connexe et sans cycle (propriété 0).
\end{defi}
Les propriétés suivantes (qui s'appliquent à un graphe comptant $ n$ sommets) sont équivalentes à la définition précédente :
  1. Un arbre est un graphe connexe qui compte exactement $ n-1$ arcs
  2. Un arbre est un graphe sans cycle qui compte exactement $ n-1$ arcs. On parle de graphe acyclique minimal
  3. Un arbre est un graphe sans cycle tel que si l'on rajoute un arc quelconque, on crée un cycle
  4. Un arbre est un graphe connexe tel que la suppression d'un arc quelconque engendre la séparation en 2 composantes connexes. On parle de graphe connexe minimal
  5. Dans un arbre, tout couple de sommets est relié par une et une seule chaîne.


Bruno Garcia 2000-12-17