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.

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.