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.
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 . 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 à
.
Un arbre orienté possède un et un seul sommet dont le degré
entrant est
, alors que tous les autres sommets sont de degré
.
Nous appelons ce sommet
la racine de l'arbre.