Arbre réel

Partie d'un arbre réel.

Un arbre réel est un espace métrique ${\displaystyle (X,d)}$ tel que pour tout couple de points ${\displaystyle x,y\,\in X}$, il existe un unique chemin dans ${\displaystyle X}$ dont les extrémités sont ${\displaystyle x}$ et ${\displaystyle y}$.

Plus formellement, pour tout couple de points ${\displaystyle x,y\,\in X}$, il existe une unique isométrie ${\displaystyle \varphi _{x,y}:[0,d(x,y)]\rightarrow X}$ telle que ${\displaystyle \varphi _{x,y}(0)=x}$, ${\displaystyle \varphi _{x,y}\left(d(x,y)\right)=y}$ et tout chemin injectif ${\displaystyle \omega _{x,y}}$ de X partant de x et finissant en y est l'image de ${\displaystyle \varphi _{x,y}}$ : ${\displaystyle \varphi _{x,y}([0,d(x,y)])=\omega _{x,y}}$.

Ce chemin, que l'on peut noter ${\displaystyle [\![x,y]\!]}$, est l'unique géodésique de ${\displaystyle x}$ à ${\displaystyle y}$. On dit que c'est un espace métrique géodésiquement linéaire. On ne traitera ici que du cas où l'espace ${\displaystyle X}$ est compact.

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

Si on distingue un point, notons-le ${\displaystyle \rho }$, de ${\displaystyle 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 ${\displaystyle \rho }$).

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

${\displaystyle 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 ${\displaystyle T}$ des espaces métriques. L'espace ${\displaystyle (T,d_{GH})}$, muni de la distance de Gromov-Hausdorff, 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.

Visualisation de la condition des quatre points et de la 0-hyperbolicité. En vert : ${\displaystyle (x,y)_{t}=(y,z)_{t}}$ ; en bleu : ${\displaystyle (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 connexe qui ne contient pas de sous-ensemble homéomorphe à un cercle[1].
   
   
2. Un arbre réel est un espace métrique connexe ${\displaystyle (X,d)}$ qui vérifie la condition des quatre points[3] (voir figure ci-contre) :
   pour tous ${\displaystyle x,y,z,t\in X,}$ ${\displaystyle 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 connexe 0-hyperbolique[2](voir figure ci-contre). C'est-à-dire,
   pour tous ${\displaystyle x,y,z,t\in X,}$ ${\displaystyle (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 ${\displaystyle e}$. C'est-à-dire, une fonction ${\displaystyle e}$ telle que, ${\displaystyle e(0)=0}$, ${\displaystyle e(t)>0}$ pour tout ${\displaystyle t\in ]0,\zeta (e)[}$ où ${\displaystyle \zeta (e)=\inf\{t>0,e(t)=0\}}$ est la fin de l'excursion et ${\displaystyle e(t)=0}$ pour tout ${\displaystyle t\geq \zeta (e)}$. Pour ${\displaystyle x,y\in [0,\zeta (e)]}$, ${\displaystyle x\leq y}$, on définit une pseudodistance et une relation d'équivalence par :
   ${\displaystyle d_{e}(x,y):=e(x)+e(y)-2\min(e(z)\,;z\in [x,y]),}$
   ${\displaystyle x\sim _{e}y\Leftrightarrow d_{e}(x,y)=0.}$
   Ainsi, l'espace métrique quotienté ${\displaystyle ([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).