Arbre (mathématiques)

Représentation (finie) de l'arbre de Stern-Brocot.

L'arbre de Stern-Brocot est une représentation de tous les rationnels strictement positifs, sous forme de fractions irréductibles.

Chaque nœud est de degré 3, excepté les trois nœuds 0/1 = 0, 1/1 = 1 et 1/0 = ∞. Considérons que 1 est la racine de l'arbre. L'arbre est défini par l'itération : deux nœuds ${\displaystyle \scriptstyle {\frac {m}{n}}}$ et ${\displaystyle \scriptstyle {\frac {m'}{n'}}}$ ont pour père ${\displaystyle \scriptstyle {\frac {m+m'}{n+n'}}}$ ; où ${\displaystyle \scriptstyle m,\,m',\,n}$ et ${\displaystyle \scriptstyle n'}$ sont des entiers strictement positifs.

L'arbre de Calkin-Wilf est une alternative pour représenter sous forme d'arbre infini les rationnels strictement positifs, sous forme de fractions irréductibles : le nœud correspondant au rationnel ${\displaystyle \scriptstyle {\frac {a}{b}}}$ a pour fils gauche ${\displaystyle \scriptstyle {\frac {a}{a+b}}}$ et pour fils droit ${\displaystyle \scriptstyle {\frac {a+b}{b}}}$, la racine ${\displaystyle \scriptstyle {\frac {0}{1}}=0}$ a pour unique fils ${\displaystyle \scriptstyle {\frac {1}{1}}=1}$. Chaque rationnel est ainsi représenté une seule fois dans l'arbre.

Un arbre homogène de degré n est un arbre dont chaque nœud est de degré n, c'est-à-dire qu'il est relié à n autres sommets. Cet arbre est alors infini.

Soit A un alphabet non nécessairement fini et A* l'ensemble des mots (finis) écrits à partir de A (mot vide ε compris), qui est un monoïde pour la concaténation. Définissons des relations P (pour prédécesseur) et S (pour successeur) entre mots par xSy, ou yPx, ssi x est obtenu à partir de y en lui ajoutant une lettre à droite ; alors (A*,T), où T est la symétrisée de P ou S, est un arbre. Nous appellerons arbre sur A tout arbre (E,R) où E est une partie de A* stable par prise de prédécesseur (propriété voisine de celle d'un ensemble transitif) et où R est évidemment la restriction de T; un tel arbre a une racine naturelle, le mot vide. Cet exemple, lorsque A est égal à N ou NxN, sera développé ci-dessous en théorie des ensembles.

On en trouve cas particulier en probabilités appliquées à la dynamique des populations, plus précisément lors de l'étude des processus de Galton-Watson, sous le nom de notation de Neveu. Les arbres associés aux processus de Galton-Watson sont alors appelés arbres de Galton-Watson.

L'ensemble de Cantor est un sous-ensemble remarquable de la droite réelle construit de manière itérative à partir du segment [0, 1] en enlevant le tiers central ; puis on réitère l'opération sur les deux segments restants, et ainsi de suite. On peut voir les six premières itérations du procédé sur le schéma suivant :

On dénote par ${\displaystyle {\mathcal {T}}}$ l'opérateur « enlever le tiers central » :

${\displaystyle {\mathcal {T}}:[a,b]\mapsto \left[a,a+{\frac {b-a}{3}}\right]\cup \left[b-{\frac {b-a}{3}},b\right].}$

On peut alors représenter chaque intervalle par les nœuds d'un arbre binaire. L'intervalle [0, 1] est la racine et les deux intervalles ${\displaystyle \scriptstyle \left[a,a+{\frac {b-a}{3}}\right]}$ et ${\displaystyle \scriptstyle \left[b-{\frac {b-a}{3}},b\right]}$ sont les deux fils de l'intervalle [a, b]. Chaque intervalle ainsi obtenu au bout de n itérations peut être étiqueté par un mot de n lettres sur l'alphabet A = {0,1}, la i-ème lettre du mot indiquant si, lors de la i-ème itération, on a choisi l'intervalle de gauche ou de droite. L'ensemble des intervalles forme un arbre infini en bijection avec l'ensemble A* de tous les mots finis sur l'alphabet A. Complétons cet arbre en lui rajoutant l'espace de Cantor, formé des mots constitués d'une suite infinie de 0 ou de 1. Définissons sur cet ensemble la relation x < y si et seulement si x est un préfixe de y. On obtient alors l'arbre de Cantor, dont l'ensemble des feuilles est exactement l'ensemble des mots infinis, en bijection avec l'ensemble de Cantor. Ci-dessous une représentation des six générations de cet arbre. Les nœuds (ou ensembles) sont représentés par des lignes horizontales et les arêtes de l'arbre par des lignes verticales.

On dit que (E, <) est un arbre bien fondé s'il n'existe pas de suite infinie ${\displaystyle x_{0}<x_{1}<\cdots <x_{n}<\cdots }$. L'arbre de Cantor n'est pas bien fondé.