- Arbre (Mathématiques)
-
Arbre (mathématiques)
Pour les articles homonymes, voir Arbre (homonymie) .- 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 i<n, zn=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 la 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 Nk et Zk n'ont pas de structure d'arbre naturelle.
Sommaire
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
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
Portail des mathématiques
Catégories : Théorie des ensembles | Arbre
Wikimedia Foundation. 2010.
