Introduction
Pour tout ce qui concerne les arbres en théorie des graphes voir ici.
Un arbre est la donnée d'un ensemble E et d'une relation symétrique R sur E telle que deux points distincts quelconques x et y de E soient reliés par une seule géodésique finie : il existe un unique plus court chemin de x à y, un chemin de longueur n de x à y étant une suite de n+1 points z0,...,zn de E vérifiant x=z0, ziRzi+1 pour izn=y. L'arbre (E,R) est dit fini ou infini selon que R est fini ou non. Par exemple si E est la réunion du bord d'un disque et de son centre c et si xRy est la relation x=c ou y=c, alors (E,R) est un arbre infini ; cependant la plupart des arbres infinis que l'on rencontre sont dénombrables. Pour les arbres finis, notre définition est équivalente à celle de Théorie des graphes dont nous utiliserons la terminologie. On distingue souvent dans un arbre un sommet particulier appelé racine ; par exemple N, muni de la relation xRy ssi x=Sy ou y=Sx où S est la fonction successeur, est un arbre infini admettant 0 comme racine naturelle, et cela s'étend à Z. Par contre, pour k>1, les treillis N et Z n'ont pas de structure d'arbre naturelle.