Arbre réel

Pour les articles homonymes, voir Arbre (homonymie).

Deux représentations (en rouge) d'un arbre réel défini à partir de l'excursion e (en noir).

En mathématiques, un arbre réel, ou arbre continu ou $\scriptstyle \mathbb R$-arbre, est un espace métrique particulier possédant une propriété d'arbre : il existe un « chemin » entre chaque couple de points de l'espace métrique, de plus ce « chemin » est unique pour un couple de points donné.

Intuitivement, un arbre réel peut être vu comme un arbre discret composé de nœuds et d'arêtes à longueur variable. Toutefois, tout point intérieur d'une arête est considéré comme un nœud de l'arbre (de degré 2). L'ensemble des points de branchement (nœuds de degré au moins 3) peut être dense dans l'arbre, ce qui en fait un objet fractal.

Plusieurs définitions équivalentes existent, on peut également « construire » certains arbres réels comme les objets limites de suites d'arbres discrets en faisant tendre leurs longueurs d'arête vers 0.

L'arbre brownien (ou CRT brownien) est un exemple important d'arbre continu en probabilités. C'est un objet fractal dont les arêtes sont de longueur infinitésimale et dont les nœuds sont denses dans l'arbre. En théorie géométrique des groupes, il existe une théorie des actions de groupe sur les $\scriptstyle \mathbb R$-arbres.

Définitions formelles

Partie d'un arbre réel.

Un arbre réel est un espace métrique $\scriptstyle (X,d)$ tel que pour tout couple de points $\scriptstyle x,y\,\in X$, il existe un unique segment de points de X dont les extrémités sont x et y. Ce segment, que l'on note $\scriptstyle [\![ x,y ]\!]$, est aussi appelé chemin de x à y (ou de x à y), c'est l'unique géodésique de x à y. On dit que c'est un espace métrique géodésiquement linéaire. On ne traitera ici que du cas ou l'espace $\scriptstyle X$ est compact.

Soit x un point de X. Le degré de x, noté deg(x), est le nombre de parties disjointes de l'ensemble $\scriptstyle X\setminus\{x\}$. Si deg(x) = 1, alors x est une extrémité de X (feuille ou racine) ; si deg(x) = 2, alors x est un point du squelette de X ; si $\scriptstyle deg(x)\ge 3$, alors x est un point de branchement^[1] de X.

Si on distingue un point, notons-le ρ, de X, l'espace métrique est alors appelé espace métrique pointé. Pour un vocabulaire plus proche des arbres, on dit que l'arbre est enraciné (en la racine ρ).

Il est alors possible de définir une relation généalogique. L'ancêtre commun le plus récent de deux points x et y de X est l'unique point $\scriptstyle w\in X$ tel que $\scriptstyle [\![ \rho,x ]\!]\cap [\![ \rho,y ]\!] = [\![ \rho,w ]\!]$. Utilisons la notation $\scriptstyle x \wedge y$. La distance de la racine ρ à $\scriptstyle x \wedge y$ est donnée par^[2] :

$d(\rho, x \wedge y):=(x.y)_\rho := \frac{1}{2} \left( d(\rho,x)+d(\rho,y)-d(x,y) \right).$

L'espace des arbres réels est un sous-espace de l'espace $\scriptstyle T$ des espaces métriques. L'espace $\scriptstyle (T,d_{GH})$, muni de la distance de Gromov-Hausorff, est un espace polonais^[2] (métrique, séparable, complet). On peut alors comparer les arbres réels en donnant une distance entre eux et ainsi construire une convergence.

Caractérisations

Visualisation de la condition des quatre points et de la 0-hyperbolicité. En vert : $\scriptstyle (x,y)_t=(y,z)_t$ ; en bleu : $\scriptstyle (x,z)_t$.

Voici plusieurs caractérisations équivalentes d'un arbre réel qui peuvent être considérées comme des définitions.

1. (similaire aux arbres en tant que graphes) Un arbre réel est un espace métrique qui ne contient pas de sous-ensemble homéomorphe à un cercle^[1].
   
   
2. Un arbre réel est un espace métrique $\scriptstyle (X,d)$ qui vérifie la condition des quatre points^[3] (voir figure ci-contre) :
      pour tous $x,y,z,t\in X,$    $d(x,y)+d(z,t)\leq max[d(x,z)+d(y,t)\,;\, d(x,t)+d(y,z)]$.
   
   
3. Un arbre réel est isomorphe à un espace métrique 0-hyperbolique^[2](voir figure ci-contre). C'est-à-dire,
      pour tous $x,y,z,t\in X,$    $(x,y)_t\geq min [ (x,z)_t\, ; \, (y,z)_t ]$.
   
   
4. (similaire à la caractérisation des arbres de Galton-Watson par le processus de contour) Considérons une excursion positive d'une fonction continue e. C'est-à-dire, une fonction e telle que, $\scriptstyle e(0)=0$, $\scriptstyle e(t)>0$ pour tout $\scriptstyle t\in ]0,\zeta(e)[$ où $\scriptstyle \zeta(e)=\inf\{t>0, e(t)=0\}$ est la fin de l'excursion et $\scriptstyle e(t)=0$ pour tout $\scriptstyle t\geq \zeta(e)$. Pour $\scriptstyle x, y\in [0,\zeta(e)]$, $\scriptstyle x\leq y$, on définit une semi-distance et une relation d'équivalence par :
      $d_e( x, y) := e(x)+e(y)-min(e(z)\, ;z\in[x,y]),$
      $x\sim_e y \Leftrightarrow d_e(x,y)=0.$
   Ainsi, l'espace métrique quotienté $\scriptstyle ([0,\zeta(e)]/\sim_e\, ,\, d_e)$ est un arbre réel^[2].
   Intuitivement, les minima locaux de l'excursion e sont les pères des maxima locaux. Une autre manière visuelle de construire l'arbre réel à partir d'une excursion est d'appliquer de la colle sous la courbe de e et de « plier » cette courbe, ainsi les points d'une même classe d'équivalence sont identifiés (voir animation ci-dessous).

Partant d'une excursion e (en noir), la déformation (en vert) représente le « pliage » de la courbe jusqu'au « collage » des points d'une même classe d'équivalence, l'état final est l'arbre réel associé à e.

Exemples

Arbre réel aléatoire

Un arbre réel aléatoire est une variable aléatoire sur l'espace des arbres réel.

Il peut être également défini, grâce à la caractérisation n°4 ci-dessus, en utilisant l'excursion d'un processus stochastique.

Arbre réel binaire

Un arbre réel binaire est un arbre réel dont les nœuds sont de degré 1 (pour les feuilles et la racine), de degré 2 (pour les points de squelette) ou degré 3 (pour les points de branchement binaires).

Les arbres binaires (discrets) en sont un exemple particulier ou chaque arête est de longueur 1.

Arbre brownien

Articles détaillés : Arbre brownien et Arbre de Galton-Watson#Convergence des arbres de Galton-Watson.

L'arbre brownien ou CRT brownien (CRT sont les initiales de continuum random tree en anglais^[4]) est un arbre réel binaire aléatoire engendré par un mouvement brownien. Plus précisément, l'arbre brownien est l'arbre réel défini à partir d'une excursion brownienne et en utilisant la caractérisation 4 (voir ci-dessus).

Construction par la séparation poissonienne d'une droite

Une des premières construction de l'arbre brownien a été donnée par Aldous^[4] en 1991, en utilisant la séparation poissonienne d'une droite (Poisson line-breacking en anglais). On considère un processus de Poisson non homogène N d'intensité r(t)=t (c'est-à-dire que $\scriptstyle N_t$ est une variable de Poisson de paramètre $\scriptstyle t^2$) et $\scriptstyle C_1,C_2,...$ les points générés par ce processus de Poisson. On sépare la droite réelle suivant les intervalles $\scriptstyle [C_i,C_{i+1}[$. Le segment $\scriptstyle [0,C_1[$ est l'arbre de départ, on attache le segment suivant $\scriptstyle [C_1,C_2[$ en un point choisi uniformément sur l'arbre en cours ; on itère cette opération pour la suite de points $\scriptstyle (C_i)_i$. La fermeture de l'objet limite est l'arbre brownien^[4].

Construction comme limite d'arbres de Galton-Watson

Rappelons que l'arbre brownien peut être défini à partir d'une excursion brownienne en utilisant la caractérisation n°4 (voir ci-dessus). De même un arbre de Galton-Watson, ou une forêt de Galton-Waltson, peut être définie à partir d'une excursion (discrète) d'une marche de Łukasiewicz.

Un théorème de convergence de type Donsker permet d'obtenir la convergence des excursions discrètes vers les excursions continues et ainsi permet de définir l'arbre brownien comme limite d'échelle d'arbres de Galton-Watson.

Une autre manière de voir cette convergence est d'utiliser la définition de l'arbre brownien comme espace métrique géodésiquement linéaire. En normalisant convenablement la distance de cet espace métrique, on obtient une limite de l'espace métrique discret vers le CRT brownien. Cette convergence est la convergence de Gromov-Hausdorff dans l'espace des espaces métriques muni de la distance de Gromov-Hausdorff.

Notes et références

1. ↑ ^{a et b} Ian Chiswell, Introduction to Lambda-trees, World Scientific Publishing, 2001, ISBN 981-02-4386-3
2. ↑ ^{a, b, c et d} Steven N. Evans, Probability and Real Trees, Ecole d’Eté de Probabilités de Saint-Flour XXXV, 2005.
3. ↑ Peter Buneman, A Note on the Metric Properties of Trees, Journal of combinatorial theory, B (17), p 48-50, 1974.
4. ↑ ^{a, b et c} David Aldous, The continuum random tree. I, The annals of probability, Vol. 19, (1), p1-28, 1991.

Annexes

Liens internes

• Arbre brownien
• Les arbres en mathématique

Bibliographie

• {Charles Semple et Mike Steel, Phylogenetics, Oxford University Press., 2003, ISBN 0 19 850942 1}