Arbres

La notion d'arbre est fondamentale en informatique. Un grand nombre d'algorithmes efficaces utilisent des arbres. Dans cette section, nous allons définir cette notion principalement dans le cas des graphes orientés, car la plupart des arbres utilisés en informatiques sont des arbres orientés.

Définition 7.6   Un arbre orienté est un graphe orienté connexe sans circuit $G = (V, A)$ dans lequel tout sommet $s$ a un degré entrant (nombre de brins d'arête ayant $s$ comme extrémité) inférieur ou égal à $1$.

Cette définition nous apprend d'abord qu'un arbre orienté est un graphe orienté connexe sans circuit. Mais il y a une restriction supplémentaire, à savoir que le degré entrant d'un sommet du graphe ne peut pas dépasser $1$. Le graphe comme de la figure 7.3 n'est donc pas un arbre, car il possède deux sommets dont le degré entrant est égal à $2$.

Un arbre orienté possède un et un seul sommet $R$ dont le degré entrant est $0$, alors que tous les autres sommets sont de degré $1$. Nous appelons ce sommet $R$ la racine de l'arbre.