Arbre (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.

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 i<n, z_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 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 N^k et Z^k n'ont pas de structure d'arbre naturelle.

Sommaire 1 Exemples d'arbres infinis 1.1 Arbre de Stern-Brocot 1.2 Arbre homogène de degré n 1.3 Dessins de Escher 1.4 Arbre sur un alphabet 2 Frontière d'un arbre 2.1 Définition, topologie 2.2 Le lemme de König 2.3 Exemples 2.3.1 Ensemble de Cantor 3 En théorie des ensembles 3.1 Arbre bien fondé 3.2 Indice de Lusin-Sierpinski 4 En informatique 5 En probabilités et potentiel 6 En géométrie hyperbolique

[modifier] Exemples d'arbres infinis

[modifier] Arbre de Stern-Brocot

[modifier] Arbre homogène de degré n

[modifier] Dessins de Escher

[modifier] 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.

[modifier] Frontière d'un arbre

[modifier] Définition, topologie

[modifier] Le lemme de König

[modifier] Exemples

[modifier] Ensemble de Cantor

[modifier] En théorie des ensembles

[modifier] Arbre bien fondé

[modifier] Indice de Lusin-Sierpinski

[modifier] En informatique

[modifier] En probabilités et potentiel

[modifier] En géométrie hyperbolique

• Portail des mathématiques