Arbres et forêts en théorie des graphes
Un arbre est un graphe non-orienté, connexe, et sans cycle. Il est dénommé ainsi car, représenté dans le plan, sa forme évoque les ramifications d'une branche. On appelle alors forêt un ensemble d'arbres.
Pour un graphe non-orienté fini $G = (V, E)$, les propriétés suivantes sont équivalentes :
- $G$ est un arbre ;
- $G$ est connexe, sans cycle ;
- $G$ est connexe et $|E| = |V| - 1$ ;
- $G$ est sans cycle et $|E| = |V| -1$ ;
- $G$ est connexe minimal, c'est à dire cesse d'être connexe dès qu'il perd une arête ;
- $G$ est sans cycle maximal, c'est à dire qu'un cycle apparaît nécessairement si on lui ajoute une arête ;
- Pour tout couple de sommets $u, v\in V$, $G$ contient un unique chemin reliant $u$ et $v$.
Un arbre est dit fini s'il possède un nombre fini de sommets. Dans ce cas, il possède $|V| - 1$ arêtes.
Étant donné un arbre $G$, on peut désigner un sommet $x_0$ de $G$ comme étant la racine de l'arbre. On dit alors que $G$ est un arbre enraciné. La distance d'un sommet à la racine est appelée profondeur du sommet, et la profondeur maximale d'un sommet est appelée hauteur de l'arbre.
Pour un sommet $u$ de profondeur $p$, on appelle :
- enfant (ou fils) tout sommet adjacent à $u$ et de profondeur $p+1$
- parent (ou père) tout sommet adjacent à $u$ et de profondeur $p-1$. La racine ne possède aucun parent et tout autre sommet de l'arbre possède exactement un parent.
Les sommets qui n'ont pas d'enfants sont appelés feuilles, les autres sont appelés nœuds internes. Si $|V| \geq 2$, les feuilles sont de degré $1$.
Par extension, on parle d'ancêtres pour désigner les sommets qui relient $u$ à la racine, et de descendants ceux qui relient $u$ aux feuilles sans remonter dans l'arbre.
Un arbre est dit binaire si chaque sommet possède au plus deux enfants. Plus généralement, un arbre est dit $n$-aire avec $n \geq 2$ si chaque sommet possède au plus $n$ enfants.
Un sous-arbre d'un arbre enraciné $G$ est un arbre formé d'un sommet de $G$ et de tous ses descendants.
Un arbre est généralement représenté de haut en bas (ou de gauche à droite), de la racine aux feuilles et par tranche de profondeur.
