Arbre (mathématiques) - Définition

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 z₀,...,z_n de E vérifiant x=z₀, z_iRz_i+1 pour iz_n=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^k et Z^k n'ont pas de structure d'arbre naturelle.

Exemples d'arbres infinis

Arbre de Stern-Brocot

Arbre homogène de degré n

Dessins de Escher

Arbre sur un alphabet

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. == Frontière d'un arbre ==iopipipiiii

Définition, topologie

Le lemme de König

Exemples

Ensemble de Cantor

En théorie des ensembles

Arbre bien fondé

Indice de Lusin-Sierpinski

En informatique

En probabilités et potentiel

En géométrie hyperbolique